二叉树的各种操作
1 #include<stdio.h>
2 #include "stdlib.h"
3 #include<iostream>
4 #include<stack>
5 #include<queue>
6 using namespace std;
7
8 //節點定義
9 typedef struct biNode{
10 char val;
11 biNode* left;
12 biNode* right;
13 }biNode;
14
15 //創建一棵樹
16 void createBiTree(biNode* &root){
17 char c;
18 cin >> c;
19 if(c == '#'){
20 root = NULL;
21 }else{
22 if( !(root = (biNode*)malloc(sizeof(biNode))) ) exit(OVERFLOW); //分配存儲空間
23 root->val = c;
24 //生成根節點
25 createBiTree(root->left); //生成左子樹
26 createBiTree(root->right); //生成右子樹
27 }
28 }
29
30 //前序遍歷（根左右）遞歸
31 void preSeqOrderRec(biNode *root){
32 if(root == NULL){
33 return ;
34 }
35 printf("%c ",root->val);
36 preSeqOrderRec(root->left);
37 preSeqOrderRec(root->right);
38 }
39
40 //前序遍歷（根左右）非遞歸
41 void preSeqOrderNoRec(biNode *root){
42 if(root == NULL)
43 return;
44 stack<biNode*> st;
45 while(root || !st.empty()){
46 while(root){
47 st.push(root);
48 printf("%c ",root->val);
49 root = root->left;
50 }
51 root = st.top();
52 st.pop();
53 root = root->right;
54 }
55 }
56
57 //中序遍歷（左根右）遞歸
58 void inSeqOrderRec(biNode *root){
59 if(root == NULL){
60 return ;
61 }
62 inSeqOrderRec(root->left);
63 printf("%c ",root->val);
64 inSeqOrderRec(root->right);
65 }
66
67 //中序遍歷（左根右）非遞歸
68 void intSeqOrderNoRec(biNode *root){
69 if(root == NULL)
70 return;
71 stack<biNode*> st;
72 while(root || !st.empty()){
73 while(root){
74 st.push(root);
75 root = root->left;
76 }
77 root = st.top();
78 st.pop();
79 printf("%c ",root->val);
80 root = root->right;
81 }
82 }
83
84 //后序遍歷（左右根）遞歸
85 void postSeqOrderRec(biNode *root){
86 if(root == NULL){
87 return ;
88 }
89 postSeqOrderRec(root->left);
90 postSeqOrderRec(root->right);
91 printf("%c ",root->val);
92 }
93
94 //后序遍歷（左右根）非遞歸
95 void postSeqOrderNoRec(biNode *root){
96 if(root == NULL){
97 return ;
98 }
99 stack<biNode*> st;
100 biNode* p;
101 p = root;
102 do
103 {
104 while (p){//左子樹進棧
105 st.push(p);
106 p = p->left;
107 }
108 while (!st.empty() && st.top()->right == p){
109 p = st.top(); //棧頂結點出棧
110 st.pop();
111 printf("%c ",p->val);
112 }
113 if (!st.empty())
114 p = st.top()->right; //開始遍歷右子樹
115 }while(!st.empty());
116 }
117
118 //層序遍歷
119 void levelSeqVisit(biNode *root){
120 if(root == NULL)
121 return ;
122 queue<biNode*> que;
123 que.push(root);
124 biNode *p;
125 while(!que.empty()){
126 p = que.front();
127 que.pop();
128 printf("%c ",p->val);
129 if(p->left)
130 que.push(p->left);
131 if(p->right)
132 que.push(p->right);
133 }
134 }
135
136 //所有節點個數
137 int getNodeCount(biNode* root){
138 if(root == NULL)
139 return 0;
140 int count = 1;
141 count += getNodeCount(root->left);
142 count += getNodeCount(root->right);
143 return count;
144 }
145
146 //得到葉子節點個數
147 int getLeafCount(biNode* root){
148 if(root == NULL)
149 return 0;
150 int count = 0;
151 if(root->left == NULL && root->right == NULL){
152 count ++;
153 }else{
154 count += getLeafCount(root->left);
155 count += getLeafCount(root->right);
156 }
157 return count;
158 }
159
160 //樹的高度
161 int getDepth(biNode *root){
162 if(root == NULL)
163 return 0;
164 int leftDepth = getDepth(root->left);
165 int rightDepth = getDepth(root->right);
166 return leftDepth>rightDepth ? (leftDepth+1) : (rightDepth+1);
167 }
168
169 //某節點所在層次
170 int getLevelByNode(biNode *root,char toFind,int &count){
171
172 if(root==NULL || toFind==NULL)
173 return 0;
174 if(root->val == toFind ){
175 count++;
176 return 1;
177 }
178 if(getLevelByNode(root->left,toFind,count) || getLevelByNode(root->right,toFind,count)){
179 count++;
180 return 1;
181 }
182
183 return 0;
184 }
185
186 //是否為平衡樹
187 bool isBalanceTree(biNode* root){
188 if(root == NULL)
189 return false;
190 int leftDepth = getDepth(root->left);
191 int rightDepth = getDepth(root->right);
192 if(leftDepth-rightDepth>1 || rightDepth-leftDepth<-1)
193 return false;
194 return true;
195 }
196
197 //是否為平衡樹（優化版）
198 bool isBalanceTreeOptimize(biNode* root, int* Depth){
199 if(root == NULL){
200 *Depth = 0;
201 return true;
202 }
203 int left=0,right=0;
204 if(isBalanceTreeOptimize(root->left,&left) && isBalanceTreeOptimize(root->right,&right)){
205 int diff = left - right;
206 if(diff<=1 && diff>=-1){
207 *Depth = 1 + (left>right ? left : right);
208 return true;
209 }
210 }
211 return false;
212 }
213
214 //是否為完全二叉樹
215 bool isCompleteTree(biNode *root){
216 queue<biNode*> que;
217 que.push(root);
218 biNode* p;
219 bool isFirstLeaf = false;
220 while(!que.empty()){
221 p = que.front();
222 que.pop();
223 //第一個葉子節點
224 if(p->left==NULL && p->right==NULL){
225 isFirstLeaf = true;
226 }
227 bool LOrR = p->left != NULL || p->right != NULL;
228 bool LAndR = p->left != NULL && p->right != NULL;
229 //第一個葉子節點之后的節點，都是葉子節點
230 if(isFirstLeaf && LOrR){
231 return false;
232 }
233 //第一個葉子之前的節點，都有兩個孩子
234 if(!isFirstLeaf && !LAndR){
235 return false;
236 }
237 if(p->left != NULL)
238 que.push(p->left);
239 if(p->right != NULL)
240 que.push(p->right);
241 }
242 return true;
243 }
244
245 //是否滿二叉樹
246 bool isFullTree(biNode* root){
247 if(root==NULL){
248 return true;
249 }
250 int lDepth = getDepth(root->left);
251 int rDepth = getDepth(root->right);
252 int diff = lDepth - rDepth;
253 if(diff==0 && isFullTree(root->left) && isFullTree(root->right)){
254 return true;
255 }
256 return false;
257 }
258
259 int main(){
260 biNode* T;
261
262 //ab#c##d##
263 printf("\n創建樹:\n");
264 createBiTree(T);
265
266 printf("\n前序遍歷（遞歸）：\n");
267 preSeqOrderRec(T);
268 printf("\n前序遍歷（非遞歸）：\n");
269 preSeqOrderNoRec(T);
270
271 printf("\n中序遍歷（遞歸）：\n");
272 inSeqOrderRec(T);
273 printf("\n中序遍歷（非遞歸）：\n");
274 intSeqOrderNoRec(T);
275
276 printf("\n后序遍歷（遞歸）：\n");
277 postSeqOrderRec(T);
278 printf("\n后序遍歷（非遞歸）：\n");
279 postSeqOrderNoRec(T);
280
281
282 printf("\n節點數為：\n%d",getNodeCount(T));
283 printf("\n葉子節點數為：\n%d",getLeafCount(T));
284
285 printf("\n樹的高度為：\n%d",getDepth(T));
286
287 printf("\n層序遍歷：\n");
288 levelSeqVisit(T);
289
290 int level = 0 ;
291 getLevelByNode(T,'d',level);
292 printf("\n某個節點所在層次：\n%d",level);
293
294 printf("\n是否為平衡數：%d\n",isBalanceTree(T));
295
296 int depth = 0;
297 bool isBanlance = isBalanceTreeOptimize(T,&depth);
298 printf("\n是否為平衡樹優化版：%d,且高度為：%d\n",isBanlance,depth);
299
300 printf("\n是否為完全二叉樹：%d\n",isCompleteTree(T));
301
302 printf("\n是否為滿二叉樹：%d\n",isFullTree(T));
303
304 printf("\n");
305 }
?
總結
- 上一篇： [Z]从铁道部12306.cn网站漫谈电
- 下一篇： myeclips/eclipse配置总结