二叉树代码，在里面我做了大量的注释！有兴趣的
/*二叉查找树片段,二叉查找树中定义左子树的数据必须要小于根的数据,右子树的数据必须是大于或等于根的数据
在遍历中...如果是先根后左最后右子树---则称为前序遍历也称为先根遍历
如果是先左后根最后右子树---则称为中序遍历也称为中根遍历
如果是先左后右最后根树-----则称为后序遍历也称为后根遍历
在这三种中中根遍历是最常用的(因为中根遍历完成后数据的
顺序是从小到大排列出来的(注意看上面对于二叉查找树的定义)
*/
#include <iostream>
using namespace std;
typedef int T;
Node* Root=NULL;//定义一个根struct Node
{
T Data;
Node* Left; //指向左子树的根节点
Node* Right;//指向右子树的根节点
Node(const T& t) : Data(t),Left(NULL),Right(NULL){}//构造函数初始化数据
};
void Travel(Node* tree) //遍历函数中根遍历
{
if (tree==NULL) return;
Travel(tree->Left);
cout<<tree->Data<<' ';
Travel(tree->Left);
}
void Clear(Node*& tree)//删除所有的根节点
{
if(tree==NULL) return;
Clear(tree->Left);
Clear(tree->Right);
delete tree;
tree=NULL;
}
int Size(Node* tree)//算出一共有多少个节点
{
if(tree==NULL) return 0;
return Size(tree->Left)+Size(tree->Right)+1 //左子树的节点加右子树的节点加根的一个节点
}
void Insert(Node*& tree,Node* p)//插入节点
{
if(tree==NULL) tree=p;
else if(p==NULL) return;
else if(p->Data<tree->Data)//插入的数据如果小于根的数据
Insert(tree->Left,p);//向左子树插入
else Insert(tree->Right,p);//否则向右子树插入
}
Node*& Find(Node*& tree,const T& t) //查找数据
{
if(tree==NULL || tree->Data==t) return tree;
if(t<tree->Data) return Find(tree->Left,t); //如果要查找的数据小于根的数据那进入左子树查找
else return Find(tree->Right,t) //否则进入右子树查找
}
void Erase(Node*& tree,const T& t) //删除一个对应数据的节点
{
Node*& p=Find(tree,t);//先查找
if(p==NULL) return;//表示未找到
Insert(p->Right,p->Left);//找到后把要删除节点下的子树移动到相对应的右子树后面
Node* q=p;//保存一份，为了删除因为P指针经过下面的指向后改变
p=p->Right; //把根的指针重新指向
delete q; //最后删除这个节点
}
void Updata(const T& old,const T& new)//修改数据
{
Node* p=Find(Root,old);//从根开始查找
if(p==NULL) return;
Erase(Root,old);//找到后把这个节点删除
p=new Node(new);
Insert(Root,p);//重新插入
}
页:
[1]