数据结构实验五

源代码

1. #include  
2. using namespace std;  
3.   
4. typedef struct node  
5. {  
6.     struct node *leftChild;  
7.     struct node *rightChild;  
8.     char data;  
9. }BiTreeNode, *BiTree;  
10.   
11.   
12. BiTreeNode *createnode(char c)  
13. {  
14.     BiTreeNode *q=new BiTreeNode;  
15.     q->leftChild=NULL;  
16.     q->rightChild=NULL;  
17.     q->data=c;  
18.     return q;  
19. }  
20.   
21. void createBiTree(BiTree &T)  
22. {  
23.     char c;  
24.     cin >> c;  
25.     if(c == '#')  
26.         T = NULL;  
27.     else  
28.     {  
29.         T = new BiTreeNode;  
30.         T->data = c;  
31.         createBiTree(T->leftChild);  
32.         createBiTree(T->rightChild);  
33.     }  
34. }  
35.   
36.   
37. int max(int a, int b )  
38. {  
39.     return a < b ? b : a;  
40. }  
41.   
42.   
43. int Depth(BiTree T)  
44. {  
45.     if ( T== NULL)  
46.         return 0;  
47.    
48.     int leftDepth = Depth(T->leftChild);  
49.     int rightDepth = Depth(T->rightChild);  
50.   
51.     return 1+ max(leftDepth, rightDepth);  
52. }  
53.   
54.   
55. void PrintNodeatlevel(BiTree T,int level)  
56. {  
57.     if(T==NULL || level<1)  
58.         return;  
59.     if(level==1)  
60.     {  
61.         cout<data<<" ";  
62.         return;  
63.     }  
64.     PrintNodeatlevel(T->leftChild,level-1);  
65.     PrintNodeatlevel(T->rightChild,level-1);  
66. }  
67.   
68.   
69. void LevelTraverse(BiTree T)  
70. {  
71.     if(T==NULL)  
72.         return;  
73.     int depth=Depth(T);  
74.     for(int i=1;i<=depth;i++)  
75.     {  
76.         PrintNodeatlevel(T,i);  
77.         cout<leftChild==NULL && T->rightChild==NULL)  
78.         {  
79.             cout<data<<" ";  
80.         }  
81.         LeavesTraverse(T->leftChild);  
82.         LeavesTraverse(T->rightChild);  
83. }  
84.   
85.   
86. int getleafnode(BiTree T)  
87. {  
88.     if(T==NULL)  
89.         return 0;  
90.     if(T->leftChild==NULL && T->rightChild==NULL)  
91.         return 1;  
92.     return getleafnode(T->leftChild)+getleafnode(T->rightChild);  
93. }  
94.   
95.   
96. int getallnode(BiTree T)  
97. {  
98.     if(T==NULL)  
99.         return 0;  
100.     return 1+getallnode(T->leftChild)+getallnode(T->rightChild);  
101. }  
102.   
103.       
104. BiTreeNode *parent(BiTreeNode *T,char c)  
105. {  
106.     if(T==NULL)  
107.         return NULL;  
108.     if(T->leftChild!=NULL && T->leftChild->data==c)  
109.     {  
110.         return T;  
111.     }  
112.     if(T->rightChild!=NULL && T->rightChild->data==c)  
113.     {  
114.         return T;  
115.     }  
116.     BiTreeNode *p=parent(T->leftChild,c);  
117.     if(p!=NULL)  
118.     {  
119.         return p;  
120.     }  
121.     p=parent(T->rightChild,c);  
122.     return p;  
123. }  
124.   
125.   
126. BiTreeNode *children(BiTreeNode *T,char c)  
127. {  
128.     if(T==NULL)  
129.         return NULL;  
130.     if(T->data==c)  
131.     {  
132.         if(T->leftChild!=NULL && T->rightChild!=NULL)  
133.             cout<<"左孩子:"<leftChild->data<rightChild->data<leftChild==NULL && T->rightChild!=NULL)  
134.             cout<<"左孩子为空！"<rightChild->data<leftChild!=NULL && T->rightChild==NULL)  
135.             cout<<"左孩子:"<leftChild->data<leftChild==NULL && T->rightChild==NULL)  
136.             cout<<"没有孩子!"<leftChild,c);  
137.     if(p!=NULL)  
138.     {  
139.         return p;  
140.     }  
141.     p=children(T->rightChild,c);  
142.     return p;  
143. }  
144.   
145.   
146. void preorder(BiTree T)  
147. {  
148.     if(T==NULL)return;  
149.     if(T!=NULL)  
150.     {  
151.         cout<data<<" ";  
152.         preorder(T->leftChild);  
153.         preorder(T->rightChild);  
154.     }  
155. }  
156.   
157. void inorder(BiTree T)  
158. {  
159.     if(T==NULL)return;  
160.     if(T!=NULL)  
161.     {  
162.         inorder(T->leftChild);  
163.         cout<data<<" ";  
164.         inorder(T->rightChild);  
165.     }  
166. }  
167.   
168. void postorder(BiTree T)  
169. {  
170.     if(T==NULL)return;  
171.     if(T!=NULL)  
172.     {  
173.         postorder(T->leftChild);  
174.         postorder(T->rightChild);  
175.         cout<data<<" ";  
176.     }  
177. }  
178. // -----------------------------------------------------------------------------------------------  
179.   
180.   
181. int main()  
182. {  
183.     BiTree T;  
184.     char x;  
185.     BiTreeNode *p;  
186.       
187.     cout<<"输入一棵树:";  
188.     createBiTree(T);  
189.     cout<>x;  
190.     p=parent(T,x);  
191.     if(p!=NULL)  
192.     {  
193.     cout<<"双亲:"<data;  
194.     }  
195.     else cout<<"找不到双亲!";  
196.     cout<>x;  
197.     p=children(T,x);  
198.     cout<

运行结果