二叉树代码，在里面我做了大量的注释！有兴趣的

David902

/*二叉查找树片段,二叉查找树中定义左子树的数据必须要小于根的数据,
                     右子树的数据必须是大于或等于根的数据

  在遍历中...如果是先根后左最后右子树---则称为前序遍历也称为先根遍历
             如果是先左后根最后右子树---则称为中序遍历也称为中根遍历
                     如果是先左后右最后根树-----则称为后序遍历也称为后根遍历
                     在这三种中中根遍历是最常用的(因为中根遍历完成后数据的
                     顺序是从小到大排列出来的(注意看上面对于二叉查找树的定义)
*/
#include <iostream>
using namespace std;
typedef int T;
Node* Root=NULL;//定义一个根

1. struct Node
   
2. {
   
3.         T Data;
   
4.         Node* Left; //指向左子树的根节点
   
5.         Node* Right;//指向右子树的根节点
   
6.         Node(const T& t) : Data(t),Left(NULL),Right(NULL){}//构造函数初始化数据
   
7. };
   
8. void Travel(Node* tree) //遍历函数中根遍历
   
9. {
   
10.         if (tree==NULL) return;
    
11.         Travel(tree->Left);
    
12.         cout<<tree->Data<<' ';
    
13.         Travel(tree->Left);
    
14. }
    
15. 
    
16. void Clear(Node*& tree)//删除所有的根节点
    
17. {      
    
18.         if(tree==NULL) return;
    
19.         Clear(tree->Left);
    
20.         Clear(tree->Right);
    
21.         delete tree;
    
22.         tree=NULL;
    
23. }
    
24. 
    
25. int Size(Node* tree)//算出一共有多少个节点
    
26. {
    
27.         if(tree==NULL) return 0;
    
28.         return Size(tree->Left)+Size(tree->Right)+1 //左子树的节点加右子树的节点加根的一个节点
    
29. }
    
30. 
    
31. void Insert(Node*& tree,Node* p)//插入节点
    
32. {
    
33.         if(tree==NULL) tree=p;
    
34.         else if(p==NULL) return;
    
35.         else if(p->Data<tree->Data)//插入的数据如果小于根的数据
    
36.                 Insert(tree->Left,p);//向左子树插入
    
37.         else Insert(tree->Right,p);//否则向右子树插入
    
38. }
    
39. 
    
40. Node*& Find(Node*& tree,const T& t) //查找数据
    
41. {
    
42.         if(tree==NULL || tree->Data==t) return tree;
    
43.         if(t<tree->Data) return Find(tree->Left,t); //如果要查找的数据小于根的数据那进入左子树查找
    
44.         else return Find(tree->Right,t) //否则进入右子树查找
    
45. }
    
46. 
    
47. void Erase(Node*& tree,const T& t) //删除一个对应数据的节点
    
48. {
    
49.         Node*& p=Find(tree,t);//先查找
    
50.         if(p==NULL) return;//表示未找到
    
51.         Insert(p->Right,p->Left);//找到后把要删除节点下的子树移动到相对应的右子树后面
    
52.         Node* q=p;//保存一份，为了删除因为P指针经过下面的指向后改变
    
53.         p=p->Right; //把根的指针重新指向
    
54.         delete q; //最后删除这个节点
    
55. }
    
56. 
    
57. void Updata(const T& old,const T& new)//修改数据
    
58. {
    
59.         Node* p=Find(Root,old);//从根开始查找
    
60.         if(p==NULL) return;
    
61.         Erase(Root,old);//找到后把这个节点删除
    
62.         p=new Node(new);
    
63.         Insert(Root,p);//重新插入
    
64. }

复制代码