首页 / 算法 / 二叉树的实现(c++实现)
二叉树的实现(c++实现)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的实现(c++实现),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2669字,纯文字阅读大概需要4分钟。
内容图文
![二叉树的实现(c++实现)](/upload/InfoBanner/zyjiaocheng/595/af9ce6f65c204a3dbc756905e6eb66d6.jpg)
先上代码:
头文件
//delete操作暂时还没完全实现 有时间再补上
//
// Created by Hasee on 2021/4/4.
//
#ifndef C__CODE_BASEBINARYTREE_H
#define C__CODE_BASEBINARYTREE_H
using std::cout;
template<class T>
struct BTNode{
T data;
BTNode<T>* left;
BTNode<T>* right;
BTNode(){
left= nullptr;
right= nullptr;
}
BTNode(T &item,BTNode<T>*l= nullptr,BTNode<T>*r= nullptr){
left=l;
right=r;
data=item;
}
};
template<class T>
class Tree{
private:
BTNode<T>* root;
protected:
void makeempty(BTNode<T>*ptr);
BTNode<T>* rlLocate(T node_value,BTNode<T>*ptr);//递归定位要插入的节点
bool rlDelete(BTNode<T>* ptr,T x=0);
void rprint(BTNode<T>*ptr);//递归打印
public:
Tree(){
root=new BTNode<T>;
}
Tree(T item){
root=new BTNode<T>(item);
}
~Tree(){
makeempty(root);
}
bool Insert(T x,int lr=0,T value=0);
bool Delete(T del_node_value);
BTNode<T>* Locate(T value);
void output();
};
template<class T>
void Tree<T>::makeempty(BTNode<T>*ptr) {
if(!ptr)return;
if(ptr->left)makeempty(ptr->left);
if(ptr->right)makeempty(ptr->right);
delete ptr;
}
template<class T>
bool Tree<T>::Insert(T x, int lr, T value) {
if(!Locate(value))return false;
BTNode<T>* current=rlLocate(value,root);
if(lr==0){
if(!current->left)
{
current->left=new BTNode<T>(x);return true;
}
else return false;
} else if(lr==1){
if(!current->right){
current->right=new BTNode<T>(x);
return true;
} else return false;
}
return false;
}
template<class T>
bool Tree<T>::Delete(T del_node_value) {
if(!rlLocate(del_node_value,root))return false;
if(rlDelete(root,del_node_value))return true;
else return false;
}
template<class T>
BTNode<T> *Tree<T>::Locate(T value) {
return rlLocate(value,root);
}
template<class T>
BTNode<T> *Tree<T>::rlLocate(T node_vaule,BTNode<T> *ptr) {
if(!ptr)return nullptr;
if(ptr->data==node_vaule)return ptr;
BTNode<T>*locate=rlLocate(node_vaule,ptr->left);
return locate ? locate:rlLocate(node_vaule,ptr->right);
}
template<class T>
bool Tree<T>::rlDelete(BTNode<T> *ptr,T x) {
if(!ptr)return false;
if(ptr->data==x) return true;
if(ptr->left)rlDelete(ptr->left,x);
if(ptr->right)rlDelete(ptr->right,x);
return false;
}
template<class T>
void Tree<T>::output() {
rprint(root);
}
template<class T>
void Tree<T>::rprint(BTNode<T> *ptr) {
if(!ptr)return;
if(ptr->left)rprint(ptr->left);
if(ptr->right)rprint(ptr->right);
cout<<ptr->data<<"-> "<<" ";
}
#endif //C__CODE_BASEBINARYTREE_H
main函数调用实现插入与输出
#include <iostream>
#include "BaseBinaryTree.h"
int main(){
Tree<int>test(1);
test.Insert(2,0,1);
test.Insert(3,1,1);
test.Insert(4,0,2);
test.Insert(5,1,2);
test.Insert(6,0,3);
test.Insert(7,1,3);
test.Insert(7,1,3);//插入不进去
test.output();
}
实现思想:
使用结构体实现结点的三个基本结构:左右指针域以及数据域;
通过root指针对树进行遍历;
递归的查找节点。
图片显示更直观:
内容总结
以上是互联网集市为您收集整理的二叉树的实现(c++实现)全部内容,希望文章能够帮你解决二叉树的实现(c++实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。