二叉树类的实现

powerwind

学习数据结构,我的体会到它有三个基础内容:链表,二叉树,排序查找算法
前些天写了一个链表类,开始数据结构学习之路，到现在终于写了二叉树类。个人感觉学习数据结构常常会觉得理解了，却无法用语言来实现，幸好借了本好书，它基本上帮我做了。通过整理，我把它们合成一个类，希望对有些人有帮助。
这是一个精简的二叉树类

1. 
   
2. //二叉树的实现(精简版)
   
3. #include<iostream>
   
4. using namespace std;
   
5. 
   
6. typedef char ElemType;//为了简单,定义为char
   
7. //定义结构体
   
8. typedef struct node
   
9. {
   
10.         ElemType data;
    
11.         struct node*lchild;
    
12.         struct node*rchild;
    
13. }BTNode;
    
14. //类定义
    
15. class BinaryTree
    
16. {
    
17. private:
    
18.         BTNode*root;                       //根
    
19.         void preOrder(BTNode*b);
    
20.         void clearTree(BTNode*b);
    
21.        
    
22. public:
    
23.         BinaryTree(char str[]);//输入如"A(B(D(,G)),C(E,F))"构造
    
24.         ~BinaryTree();
    
25.         void display();
    
26. };
    
27. 
    
28. BinaryTree::BinaryTree(char* str)
    
29. {
    
30.         const int MaxSize=100;
    
31.         root=NULL;                //初始化为NULL
    
32.         BTNode *St[MaxSize],*p=NULL;//St指针数组作栈用
    
33.         int top=-1;           //栈顶
    
34.         int i=0;          //str的下标
    
35.         int j;                 //j=1表示左子树,j=2表示右子树
    
36.         char ch=str[i];
    
37. 
    
38.         while (ch!='\0')
    
39.         {
    
40.                 switch (ch)
    
41.                 {
    
42.                 case '(':top++;St[top]=p;j=1;break;//遇'('入栈
    
43.                 case ',':j=2;break;                                  //遇','j=2右子树
    
44.                 case ')':top--;break;                     //遇')'出栈
    
45.                 default:
    
46.                         p=new BTNode;
    
47.                         p->data=ch;
    
48.                         p->lchild=p->rchild=NULL;
    
49. 
    
50.                         if(root==NULL)root=p;//只调用一次,使root指向树根
    
51.                         else
    
52.                         {
    
53.                                 switch(j)
    
54.                                 {
    
55.                                 case 1:St[top]->lchild=p;break;
    
56.                                 case 2:St[top]->rchild=p;break;
    
57.                                 }
    
58.                         }
    
59.                 }
    
60.                 i++;
    
61.                 ch=str[i];
    
62.         }
    
63. }
    
64. 
    
65. BinaryTree::~BinaryTree()
    
66. {
    
67.         if(root!=NULL)clearTree(root);
    
68. }
    
69. 
    
70. //删除树,由析构函数调用
    
71. void BinaryTree::clearTree(BTNode*b)
    
72. {
    
73.         if (b!=NULL)
    
74.         {
    
75.                 clearTree(b->lchild);
    
76.                 clearTree(b->rchild);
    
77.                 delete b;
    
78.         }                     
    
79. }
    
80. //先序遍历
    
81. void BinaryTree::preOrder(BTNode*b)
    
82. {
    
83.         if (b!=NULL)
    
84.         {
    
85.                 cout<<b->data;
    
86.                 preOrder(b->lchild);
    
87.                 preOrder(b->rchild);     
    
88.         }
    
89. }
    
90. //打印树
    
91. void BinaryTree::display()
    
92. {
    
93.         preOrder(root);
    
94. }
    
95. //测试一下
    
96. int main()
    
97. {
    
98.         BinaryTree bt("A(B(D(,G)),C(E,F))");
    
99.         bt.display();
    
100. }
     

复制代码

这个也很简，只是用到的方法不同。

1. 
   
2. //二叉树的实现
   
3. #include<iostream>
   
4. using namespace std;
   
5. 
   
6. typedef char ElemType;//为了简单,定义为char
   
7. //定义结构体
   
8. typedef struct node
   
9. {
   
10.         ElemType data;
    
11.         struct node*lchild;
    
12.         struct node*rchild;
    
13. }BTNode;
    
14. //类定义
    
15. class BinaryTree
    
16. {
    
17. private:
    
18.         BTNode*root;                       //根
    
19. 
    
20.         void printTree(BTNode*b);          //递归输出
    
21.         int treeDepth(BTNode*b);
    
22.         BTNode*PreInCreate(char* pre,char*in,int n);//由先序和中序序列构造树的递归
    
23.         void clearTree(BTNode*b);
    
24. 
    
25. public:
    
26.         BinaryTree(char *pre,char*in,int n);//由先序和中序序列构造
    
27.         BinaryTree(BTNode*b);
    
28.         ~BinaryTree();
    
29.         BTNode* getRoot();               //取得根元素
    
30.         void display();               //以A(B(D(,G)),C(E,F))格式输出
    
31. 
    
32. };
    
33. 
    
34. BinaryTree::BinaryTree(BTNode*b)
    
35. {
    
36.         root=b;
    
37. }
    
38. 
    
39. //pre为先序字符串,in为中序字符串,n是串长
    
40. BinaryTree::BinaryTree(char* pre,char*in,int n)
    
41. {
    
42.         root=PreInCreate(pre,in,n);
    
43. }
    
44. 
    
45. BTNode* BinaryTree::PreInCreate(char* pre,char*in,int n)
    
46. {
    
47.         BTNode*b;
    
48.         char*p;
    
49.         int k;
    
50.         if(n<=0)return NULL;
    
51.         b=new BTNode;
    
52.         b->data=*pre;
    
53.         for(p=in;p<in+n;p++)
    
54.                 if(*p==*pre)break;
    
55.         k=p-in;
    
56.         b->lchild=PreInCreate(pre+1,in,k);
    
57.         b->rchild=PreInCreate(pre+k+1,p+1,n-k-1);
    
58.         return b;
    
59. }
    
60. //析构函数
    
61. BinaryTree::~BinaryTree()
    
62. {
    
63.         if(root!=NULL)clearTree(root);
    
64. }
    
65. //删除树,由析构函数调用
    
66. void BinaryTree::clearTree(BTNode*b)
    
67. {
    
68.         if (b!=NULL)
    
69.         {
    
70.                 clearTree(b->lchild);
    
71.                 clearTree(b->rchild);
    
72.                 delete b;
    
73.         }                     
    
74. }
    
75. 
    
76. inline BTNode* BinaryTree::getRoot()
    
77. {
    
78.         return root;
    
79. }
    
80. //求树的深度的递归
    
81. int BinaryTree::treeDepth(BTNode*b)
    
82. {
    
83.         int l,r;
    
84.         if(b==NULL)return 0;
    
85.         else
    
86.         {
    
87.                 l=treeDepth(b->lchild);
    
88.                 r=treeDepth(b->rchild);
    
89.                 return (l>r)?(l+1):(r+1);
    
90.         }
    
91. }
    
92. 
    
93. //打印树的递归
    
94. void BinaryTree::printTree(BTNode*b)
    
95. {
    
96.         if (b!=NULL)
    
97.         {
    
98.                 cout<<b->data;
    
99.                 if (b->lchild!=NULL||b->rchild!=NULL)
    
100.                 {
     
101.                         cout<<"(";
     
102.                         printTree(b->lchild);
     
103.                         if(b->rchild!=NULL)cout<<",";
     
104.                         printTree(b->rchild);
     
105.                         cout<<")";
     
106.                 }
     
107.         }
     
108. }
     
109. //打印树
     
110. void BinaryTree::display()
     
111. {
     
112.         printTree(root);
     
113. }
     
114. //测试下
     
115. int main()
     
116. {
     
117.         char a[]="ABDGCEF";
     
118.         char b[]="DGBAECF";
     
119.         BinaryTree bt(a,b,7);
     
120.         bt.display();
     
121. }
     

复制代码

感觉数据结构的学习很多东西是用来理解的，而很难去创新。比如树的构造，书上说到的方法就去看，去理解，很难自己想到新方法来实现。这个帖子就当自己笔记本吧。
你学习数据结构的理解和体会也分享一下，交流交流！

黯然销魂

用栈写的那个不错.

dekend

支持一下～