二叉树的各种操作

  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 }