二叉树

 

1. #include <iostream>
2. using namespace std;
3. struct BinaryTree
4. {
5.     string data;
6.     BinaryTree *Lchild;
7.     BinaryTree *Rchild;
8. };
9. void creat(BinaryTree *&T, string k) //先序遍历顺序建立二叉链表
10. {
11.     string ch;
12.     cin >> ch;
13.     if (ch == k)
14.         T = NULL;
15.     else
16.     {
17.         T = new BinaryTree;
18.         T->data = ch;
19.         creat(T->Lchild, k);
20.         creat(T->Rchild, k);
21.     }
22. }
23. int m1 = 0,m2=0,m3=0;
24. void PerOrder(BinaryTree *T) //先序遍历(递归)
25. {
26.     if (T)
27.     {
28.         if (m1 == 1)
29.             cout << ',';
30.         cout << T->data;
31.         m1 = 1;
32.         PerOrder(T->Lchild);
33.         PerOrder(T->Rchild);
34.     }
35.     else return;
36. }
37. void InOrder(BinaryTree *T) //中序遍历(递归)
38. {
39.     if (T)
40.     {
41.         InOrder(T->Lchild);
42.         if (m2 == 1)
43.             cout << ',';
44.         cout << T->data;
45.         m2 = 1;
46.         InOrder(T->Rchild);
47.     }
48.     else return;
49. }
50. void PostOrder(BinaryTree *T) //后序遍历(递归)
51. {
52.     if (T)
53.     {
54.         PostOrder(T->Lchild);
55.         PostOrder(T->Rchild);
56.         if (m3 == 1)
57.             cout << ',';
58.         cout << T->data;
59.         m3 = 1;
60.     }
61. }
62. int Depth(BinaryTree *T)//求二叉树深度
63. {
64.     int m,n;
65.     if(T)
66.     {
67.         m=Depth(T->Lchild); //递归计算左子树深度为m
68.         n=Depth(T->Rchild); //递归计算右子树深度为n
69.         return m>n? m+1 : n+1;
70.     }
71.     else return 0;
72. }
73. int Depthx(BinaryTree *T,string x)//求二叉树中以值为x的结点为根的子树深度
74. {
75.     int m,n;
76.     if(T)
77.     {
78.         if(T->data==x)
79.           return Depth(T);
80.         else
81.         {
82.             m=Depthx(T->Lchild,x);
83.             n=Depthx(T->Rchild,x);
84.             return m>n ? m:n;
85.         }
86.     }
87.     else return 0;
88. }
89. int CountLeaf(BinaryTree *T, int &count) //二叉树叶子结点个数
90. {
91.     if (T != NULL && T->Lchild == NULL && T->Rchild == NULL) {
92.         count++;
93.     }
94.     if (T != NULL) {
95.         CountLeaf(T->Lchild, count);
96.         CountLeaf(T->Rchild, count);
97.     }
98.     return count;
99. }
100. void change(BinaryTree *T)//交换左右子树（所有）
101. {
102.     if(T==NULL) return ;
103.     else {
104.         BinaryTree *p=T->Lchild;
105.         T->Lchild=T->Rchild;
106.         T->Rchild=p;
107.         change(T->Lchild);
108.         change(T->Rchild);
109.     }
110. }
111. void DestroyTree(BinaryTree *T)
112. {
113.     if(T==NULL) return;
114.     DestroyTree(T->Lchild);
115.     DestroyTree(T->Rchild);
116.     free(T);
117. }
118. int main()
119. {
120.     BinaryTree *Tree;
121.     string k;
122.     cin >> k;
123.     creat(Tree, k);//创建
126.     //需要什么加什么
127.    
128.     return 0;
129. }

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！