澳门网络娱乐游戏平台-澳门电子游戏娱乐网址-官方直营

python 平衡二叉树实今世码示例

意气风发、左枝有最右节点

2、二叉树

二叉树是逐步树,有5中着力造型。(度不超过2的树不必然是二叉树,因为二叉树还必要左右子树有序不能够颠倒)

n个节点可以营造卡特兰数 f(n卡塔尔国= (k=1~nState of QatarΣ(f(k-1卡塔尔(قطر‎f(n-k卡塔尔(قطر‎卡塔尔(قطر‎ = (C2n nState of Qatar/(n+1卡塔尔国,f(0State of Qatar=f(1卡塔尔=1种造型的二叉树。对于有n个节点的有序体系,其BST树也是Carter兰数种。

图片 1

直接将左枝节点做父级节点,父级节点做其右枝

遍历

应用链式存储:深度优先(前序、中序、后序)、广度优先(档期的顺序)遍历。(递归、非递归)

使用顺序存款和储蓄:深度优先(前序、中序、后序)、广度优先(档次)遍历。(递归、非递归),输入为以完全二叉树补空的档期的顺序遍历连串,由此遍历方法与运用链式存款和储蓄的同等,只是改为依附节点编号来呈现节点间的老爹和儿子关系。

复杂度:

深度优先:时间复杂度O(nState of Qatar、空间复杂度O(hState of Qatar

广度优先:时间复杂度O(nState of Qatar、空间复杂度O(n卡塔尔国

1、链式存款和储蓄的遍历:(输入的是树的头结点指针)

1)、递归遍历:

前序、中序、后序遍历(千篇一律):

图片 2图片 3

 1 void searchPrefix(BTREE T)
 2 {
 3     if(T!=NULL)
 4     {
 5         printf("%c",T->data);
 6         
 7         searchPrefix(T->lchild);
 8 
 9         searchPrefix(T->rchild);
10     }
11 }

View Code

能够加以改正,以打字与印刷括号音讯或补空音信。

图片 4图片 5

 1 void searchPrefix(BTREE T)
 2 {//方式1补空:所有的空指针域用特殊字符替代
 3     if(T!=NULL)
 4     {
 5         printf("%c",T->data);
 6         
 7         searchPrefix(T->lchild);
 8         
 9         searchPrefix(T->rchild);
10     }    else
11     {
12          printf("#");
13     }
14 }
15 
16 void searchPrefix(BTREE T)
17 {//方式2补空:内部节点的空指针域用特殊字符替代
18     if(T!=NULL)
19     { 
20         printf("%c",T->data);
21         
22         searchPrefix(T->lchild);
23         if((T->lchild!=NULL || T->rchild!=NULL) && (T->lchild==NULL)){   printf("#");   }//内部节点的空孩子用特殊符号代替 
24         
25         searchPrefix(T->rchild);
26         if((T->lchild!=NULL || T->rchild!=NULL) && (T->rchild==NULL)){   printf("#");   }//内部节点的空孩子用特殊符号代替 
27     }
28 }
29 
30 void searchPrefix(BTREE T)
31 {//打印括号
32     if(T!=NULL)
33     { 
34         if(T->lchild!=NULL || T->rchild!=NULL){   printf("( ");   }
35         printf("%c",T->data);
36         
37         searchPrefix(T->lchild);
38         
39         searchPrefix(T->rchild);
40         if(T->lchild!=NULL || T->rchild!=NULL){  printf(" )");  }
41     }
42 }

View Code

档期的顺序遍历:

图片 6图片 7

 1 #define M 100
 2 void searchLayer(BTREE T)
 3 {//广度优先递归遍历,与非递归遍历几乎一样,非递归遍历甚至更方便
 4     static BTREE queue[M],p;
 5     static int front=-1,rear=-1,isInitial=1;
 6     if(T!=NULL)
 7     {
 8         if(isInitial)
 9         {
10             queue[++rear]=T;
11             isInitial=0;
12         }
13         if(front<rear)
14         {
15             p=queue[++front];
16             printf("%c",p->data);
17             if(p->lchild!=NULL)queue[++rear]=p->lchild;
18             if(p->rchild!=NULL)queue[++rear]=p->rchild;
19             searchLayer(T);
20         }
21     }
22 }
23 
24 //也可借助深度遍历来完成,以下是Java版,功能是输出同层的节点
25 /**
26  * Definition for a binary tree node.
27  * public class TreeNode {
28  *     int val;
29  *     TreeNode left;
30  *     TreeNode right;
31  *     TreeNode(int x) { val = x; }
32  * }
33  */
34 public class Solution {
35     public List<List<Integer>> levelOrder(TreeNode root) {
36         List<List<Integer>> res=new ArrayList<>();
37         if(root==null)
38         {
39             return res;
40         }
41         helper(0,root,res);
42         return res;
43     }
44     public void helper(int depth,TreeNode node,List<List<Integer>>res)
45     {//通过 前序深度优先遍历 来实现 递归版的广度优先遍历
46         if(node==null) return;
47         if(res.size()==depth)
48         {
49             res.add(new ArrayList<Integer>());
50         }
51         res.get(depth).add(node.val);
52         helper(depth+1,node.left,res);
53         helper(depth+1,node.right,res);
54     }
55 }

View Code

2)、非递归遍历:

前序、中序遍历:

图片 8图片 9

 1 #define M 100
 2 void preOrder(BTREE T) 
 3 {
 4     BTREE stack[M],p=T;
 5     int top=-1;
 6     if(T!=NULL)
 7     {
 8         do
 9         {
10             while(p!=NULL)
11             {
12                 //visit(p);
13                 printf("%c",p->data);
14                 
15                 stack[++top]=p;
16                 p=p->lchild;
17             }
18             p=stack[top--];
19             p=p->rchild;
20         }while(!(p==NULL && top==-1));
21     }
22 }
23 void inOrder(BTREE T) 
24 {
25     BTREE stack[M],p=T;
26     int top=-1;
27     if(T!=NULL)
28     {
29         do
30         {
31             while(p!=NULL)
32             {
33                 stack[++top]=p;
34                 p=p->lchild;
35             }
36             p=stack[top--];
37             
38             //visit(p);
39             printf("%c",p->data);
40             
41             
42             p=p->rchild;
43         }while(!(p==NULL && top==-1));
44     }
45 }

View Code

后序遍历:(此遍历在拜会节点时,栈中保存了根节点到近期节点的父节点的保有节点)

图片 10图片 11

 1 void postOrder(BTREE T)
 2 {//后序非递归遍历,在访问节点时,栈里保存了根到当前节点的所有节点 
 3     BTREE stack1[M],p=T;
 4     int top=-1,flag,stack2[M];//flag用于标记节点是否能访问 
 5     if(T!=NULL)
 6     {
 7         do
 8         {
 9             while(p!=NULL)//①
10             {
11                 stack1[++top]=p;
12                 stack2[top]=0;
13                 p=p->lchild;
14             }
15             p=stack1[top];
16             flag=stack2[top--];
17             if(flag==0)
18             {//不能访问 
19                 stack1[++top]=p;
20                 stack2[top]=1;
21                 p=p->rchild;
22             }
23             else
24             {//能访问 
25                 //visit(p);
26                 printf("%c",p->data);
27                 
28                 p=NULL;//为了跳过① 
29             }
30         }while(!(p==NULL && top==-1));
31     }
32 }

View Code

等级次序遍历:

图片 12图片 13

 1 void layerOrder(BTREE T)
 2 {
 3     BTREE queue[M],p;
 4     int front=-1,rear=-1;
 5     if(T!=NULL)
 6     {
 7         queue[++rear]=T;
 8         
 9         while(front<rear)
10         {
11             p=queue[++front];
12             
13             //visit(p);
14             printf("%c",p->data);
15             
16             if(p->lchild!=NULL)
17             {
18                 queue[++rear]=p->lchild;
19             }
20             if(p->rchild!=NULL)
21             {
22                 queue[++rear]=p->rchild;
23             }
24         }
25     }
26 }

View Code

2、顺序存款和储蓄遍历:(输入的是截然二叉树格局的 档次遍历 连串,即除末层外,各层上的空节点都要用特殊字符填充;遍历格局与链式存款和储蓄的非递归遍历大概千篇大器晚成律,只是这里用数组下标表示父子节点关系,而链式存款和储蓄中用到是指针)

1)递归遍历:

前序、中序、后序、等级次序遍历:

图片 14图片 15

 1 //bt为输入序列,补空为完全二叉树形式
 2 void searchPrefixOfArray(char bt[],int n,int i)
 3 {
 4     if(i<n && bt[i]!='#')
 5     {
 6         printf("%c",bt[i]);
 7         searchPrefixOfArray(bt,n,2*i+1);
 8         searchPrefixOfArray(bt,n,2*i+2);
 9     }
10 }
11 void searchInfixOfArray(char bt[],int n,int i)
12 {
13     if(i<n && bt[i]!='#')
14     {
15         searchInfixOfArray(bt,n,2*i+1);
16         printf("%c",bt[i]);
17         searchInfixOfArray(bt,n,2*i+2);
18     }
19 }
20 void searchPostfixOfArray(char bt[],int n,int i)
21 {
22     if(i<n && bt[i]!='#')
23     {
24         searchPostfixOfArray(bt,n,2*i+1);
25         searchPostfixOfArray(bt,n,2*i+2);
26         printf("%c",bt[i]);
27     }
28 }
29 void searchLayerOfArray(char bt[],int n,int i)
30 {
31     while(i<n)
32     {
33         if(bt[i]!='#')
34         {
35             printf("%c",bt[i]);
36         }
37         i++;
38     }    
39 }

View Code

2)非递归遍历:

前序、中序遍历:

图片 16图片 17

 1 void preOrderOfArray(char bt[],int n)
 2 {//输入序列按完全二叉树形式补空 
 3     int stack[M],top=-1,i=0;
 4     if(n>0)
 5     {
 6         do
 7         {
 8             while(i<n && bt[i]!='#')
 9             {
10                 //visio(bt[i]);
11                 printf("%c",bt[i]);
12                 
13                 stack[++top]=i;
14                 i=2*i+1;
15             }
16             i=stack[top--];
17             i=2*i+2;
18         }while(!((i>=n || bt[i]=='#') && top==-1));
19     }
20 }
21 
22 void inOrderOfArray(char bt[],int n)
23 {//输入序列按完全二叉树形式补空
24     int stack[M],top=-1,i=0;
25     if(n>0)
26     {
27         do
28         {
29             while(i<n && bt[i]!='#')
30             {
31                 stack[++top]=i;
32                 i=2*i+1;
33             }
34             i=stack[top--];
35             
36             //visio(bt[i]);
37             printf("%c",bt[i]);
38             
39             i=2*i+2;
40         }while(!((i>=n || bt[i]=='#') && top==-1));
41     }
42 }

View Code

后序遍历:

图片 18图片 19

 1 void postOrderOfArray(char bt[],int n)
 2 {//输入序列按完全二叉树形式补空
 3     int stack1[M],stack2[M],top=-1,i=0,flag;
 4     if(n>0)
 5     {
 6         do
 7         {
 8             while(i<n && bt[i]!='#')
 9             {
10                 stack1[++top]=i;
11                 stack2[top]=0;
12                 i=2*i+1;
13             }
14             i=stack1[top];
15             flag=stack2[top--];
16             
17             if(flag==0)
18             {
19                 stack1[++top]=i;
20                 stack2[top]=1;
21                 i=2*i+2;
22             }
23             else
24             {
25                 //visit(bt[i]);
26                 printf("%c",bt[i]);
27                 
28                 i=n;
29             }
30         }while(!((i>=n || bt[i]=='#') && top==-1));
31     }
32 }

View Code

等级次序遍历:

图片 20图片 21

 1 void layerOrderOfArray(char bt[],int n)
 2 {//输入序列按完全二叉树形式补空
 3     int queue[M],front=-1,rear=-1,i;
 4     if(n>0)
 5     {
 6         queue[++rear]=0;
 7         while(front<rear)
 8         {
 9             i=queue[++front];
10             
11             //visit(bt[i]);
12             printf("%c",bt[i]);
13             
14             if(2*i+1<n && bt[2*i+1]!='#') queue[++rear]=2*i+1;
15             if(2*i+2<n && bt[2*i+2]!='#') queue[++rear]=2*i+2;
16         }
17     }
18 }

View Code

附:上述遍历的总体代码:

图片 22图片 23

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 typedef struct node
  4 {
  5     int data;
  6     struct node* lchild;
  7     struct node* rchild;
  8 }BTNode,*BTREE;
  9 
 10 //链式存储递归遍历(深度优先、广度优先) 
 11 void searchPrefix(BTREE T)
 12 {
 13     if(T!=NULL)
 14     { 
 15         printf("%c",T->data);
 16         
 17         searchPrefix(T->lchild);
 18         
 19         searchPrefix(T->rchild);
 20     }
 21 }
 22 void searchInfix(BTREE T)
 23 {
 24     if(T!=NULL)
 25     {
 26         searchInfix(T->lchild);
 27         
 28         printf("%c",T->data);
 29         
 30         searchInfix(T->rchild);
 31     }
 32 }
 33 void searchPostfix(BTREE T)
 34 {
 35     if(T!=NULL)
 36     {
 37         searchPostfix(T->lchild);
 38         
 39         searchPostfix(T->rchild);
 40         
 41         printf("%c",T->data);
 42     }
 43 }
 44 
 45 #define M 100
 46 void searchLayer(BTREE T)
 47 {//广度优先递归遍历,也可借助深度遍历来完成
 48     static BTREE queue[M],p;
 49     static int front=-1,rear=-1,isInitial=1;
 50     if(T!=NULL)
 51     {
 52         if(isInitial)
 53         {
 54             queue[++rear]=T;
 55             isInitial=0;
 56         }
 57         if(front<rear)
 58         {
 59             p=queue[++front];
 60             printf("%c",p->data);
 61             if(p->lchild!=NULL)queue[++rear]=p->lchild;
 62             if(p->rchild!=NULL)queue[++rear]=p->rchild;
 63             searchLayer(T);
 64         }
 65     }
 66 }
 67 
 68 //链式存储非递归遍历(深度优先、广度优先) 
 69 void preOrder(BTREE T) 
 70 {
 71     BTREE stack[M],p=T;
 72     int top=-1;
 73     if(T!=NULL)
 74     {
 75         do
 76         {
 77             while(p!=NULL)
 78             {
 79                 //visit(p);
 80                 printf("%c",p->data);
 81                 
 82                 stack[++top]=p;
 83                 p=p->lchild;
 84             }
 85             p=stack[top--];
 86             p=p->rchild;
 87         }while(!(p==NULL && top==-1));
 88     }
 89 }
 90 void inOrder(BTREE T) 
 91 {
 92     BTREE stack[M],p=T;
 93     int top=-1;
 94     if(T!=NULL)
 95     {
 96         do
 97         {
 98             while(p!=NULL)
 99             {
100                 stack[++top]=p;
101                 p=p->lchild;
102             }
103             p=stack[top--];
104             
105             //visit(p);
106             printf("%c",p->data);
107             
108             
109             p=p->rchild;
110         }while(!(p==NULL && top==-1));
111     }
112 }
113 void postOrder(BTREE T)
114 {//后序非递归遍历,在访问节点时,栈里保存了根到当前节点父节点的所有节点 
115     BTREE stack1[M],p=T;
116     int top=-1,flag,stack2[M];//flag用于标记节点是否能访问 
117     if(T!=NULL)
118     {
119         do
120         {
121             while(p!=NULL)//①
122             {
123                 stack1[++top]=p;
124                 stack2[top]=0;
125                 p=p->lchild;
126             }
127             p=stack1[top];
128             flag=stack2[top--];
129             if(flag==0)
130             {//不能访问 
131                 stack1[++top]=p;
132                 stack2[top]=1;
133                 p=p->rchild;
134             }
135             else
136             {//能访问 
137                 //visit(p);
138                 printf("%c",p->data);
139                 
140                 p=NULL;//为了跳过① 
141             }
142         }while(!(p==NULL && top==-1));
143     }
144 }
145 
146 void layerOrder(BTREE T)
147 {
148     BTREE queue[M],p;
149     int front=-1,rear=-1;
150     if(T!=NULL)
151     {
152         queue[++rear]=T;
153         
154         while(front<rear)
155         {
156             p=queue[++front];
157             
158             //visit(p);
159             printf("%c",p->data);
160             
161             if(p->lchild!=NULL)
162             {
163                 queue[++rear]=p->lchild;
164             }
165             if(p->rchild!=NULL)
166             {
167                 queue[++rear]=p->rchild;
168             }
169         }
170     }
171 }
172 
173 //顺序存储递归遍历(深度优先、广度优先) 
174 void searchPrefixOfArray(char bt[],int n,int i)
175 {
176     if(i<n && bt[i]!='#')
177     {
178         printf("%c",bt[i]);
179         searchPrefixOfArray(bt,n,2*i+1);
180         searchPrefixOfArray(bt,n,2*i+2);
181     }
182 }
183 void searchInfixOfArray(char bt[],int n,int i)
184 {
185     if(i<n && bt[i]!='#')
186     {
187         searchInfixOfArray(bt,n,2*i+1);
188         printf("%c",bt[i]);
189         searchInfixOfArray(bt,n,2*i+2);
190     }
191 }
192 void searchPostfixOfArray(char bt[],int n,int i)
193 {
194     if(i<n && bt[i]!='#')
195     {
196         searchPostfixOfArray(bt,n,2*i+1);
197         searchPostfixOfArray(bt,n,2*i+2);
198         printf("%c",bt[i]);
199     }
200 }
201 void searchLayerOfArray(char bt[],int n,int i)
202 {
203     while(i<n)
204     {
205         if(bt[i]!='#')
206         {
207             printf("%c",bt[i]);
208         }
209         i++;
210     }    
211 }
212 
213 //顺序存储非递归遍历(深度优先、广度优先) 
214 void preOrderOfArray(char bt[],int n)
215 {//输入序列按完全二叉树形式补空 
216     int stack[M],top=-1,i=0;
217     if(n>0)
218     {
219         do
220         {
221             while(i<n && bt[i]!='#')
222             {
223                 //visio(bt[i]);
224                 printf("%c",bt[i]);
225                 
226                 stack[++top]=i;
227                 i=2*i+1;
228             }
229             i=stack[top--];
230             i=2*i+2;
231         }while(!((i>=n || bt[i]=='#') && top==-1));
232     }
233 }
234 
235 void inOrderOfArray(char bt[],int n)
236 {//输入序列按完全二叉树形式补空
237     int stack[M],top=-1,i=0;
238     if(n>0)
239     {
240         do
241         {
242             while(i<n && bt[i]!='#')
243             {
244                 stack[++top]=i;
245                 i=2*i+1;
246             }
247             i=stack[top--];
248             
249             //visio(bt[i]);
250             printf("%c",bt[i]);
251             
252             i=2*i+2;
253         }while(!((i>=n || bt[i]=='#') && top==-1));
254     }
255 }
256 
257 void postOrderOfArray(char bt[],int n)
258 {//输入序列按完全二叉树形式补空
259     int stack1[M],stack2[M],top=-1,i=0,flag;
260     if(n>0)
261     {
262         do
263         {
264             while(i<n && bt[i]!='#')
265             {
266                 stack1[++top]=i;
267                 stack2[top]=0;
268                 i=2*i+1;
269             }
270             i=stack1[top];
271             flag=stack2[top--];
272             
273             if(flag==0)
274             {
275                 stack1[++top]=i;
276                 stack2[top]=1;
277                 i=2*i+2;
278             }
279             else
280             {
281                 //visit(bt[i]);
282                 printf("%c",bt[i]);
283                 
284                 i=n;
285             }
286         }while(!((i>=n || bt[i]=='#') && top==-1));
287     }
288 }
289 
290 void layerOrderOfArray(char bt[],int n)
291 {//输入序列按完全二叉树形式补空
292     int queue[M],front=-1,rear=-1,i;
293     if(n>0)
294     {
295         queue[++rear]=0;
296         while(front<rear)
297         {
298             i=queue[++front];
299             
300             //visit(bt[i]);
301             printf("%c",bt[i]);
302             
303             if(2*i+1<n && bt[2*i+1]!='#') queue[++rear]=2*i+1;
304             if(2*i+2<n && bt[2*i+2]!='#') queue[++rear]=2*i+2;
305         }
306     }
307 }
308 
309 
310 //构建 
311 char nextToken(char str[]) //读取下一字符,略过空格 
312 {
313     static int pos=0;
314     while(str[pos]!='' && str[pos]==' '){ pos++; }
315     return str[pos++];
316 }
317 
318 
319 void createPreOrder(char prefixStr[],BTREE *T)
320 {//输入序列为 全补空、不带括号 的序列 
321     char x=nextToken(prefixStr);
322     if(x=='#')
323     {
324         *T=NULL;
325     }
326     else
327     {
328         *T=(BTREE)malloc(sizeof(BTNode));
329         (*T)->data=x;
330         createPreOrder(prefixStr,&((*T)->lchild));
331         createPreOrder(prefixStr,&((*T)->rchild));
332     }
333 }
334 
335 int main()
336 {
337     
338     //1、链式存储遍历 
339     BTREE T=NULL;
340     //char str[]="*+A##/-B##C##D##E##";
341     char str[]="AB D## E G# H### C F## #";
342     createPreOrder(str,&T);
343     
344     //1.1、链式存储递归遍历
345     printf("链式存储递归遍历:n"); 
346     searchPrefix(T);
347     printf("n");
348 
349     searchInfix(T);
350     printf("n");
351     
352     searchPostfix(T);
353     printf("n");
354     
355     searchLayer(T);
356     printf("n");
357     
358     //1.2、链式存储非递归遍历
359     printf("n链式存储非递归遍历:n");
360     preOrder(T);
361     printf("n");
362 
363     inOrder(T);
364     printf("n");
365     
366     postOrder(T);
367     printf("n"); 
368     
369     layerOrder(T);
370     printf("n"); 
371     
372     //2、顺序存储遍历 
373     char input[]="abcd#f#####e";
374     int n=sizeof(input)-1;
375     
376     //2.1、顺序存储递归遍历
377     printf("n顺序存储递归遍历:%dn",n);
378     searchPrefixOfArray(input,n,0);
379     printf("n");
380     
381     searchInfixOfArray(input,n,0);
382     printf("n");
383     
384     searchPostfixOfArray(input,n,0);
385     printf("n");
386     
387     searchLayerOfArray(input,n,0);
388     printf("n");
389     
390     //2.2、顺序存储非递归遍历
391     printf("n顺序存储非递归遍历:%dn",n);
392     preOrderOfArray(input,n);
393     printf("n");
394 
395     inOrderOfArray(input,n);
396     printf("n");
397     
398     postOrderOfArray(input,n);
399     printf("n"); 
400     
401     layerOrderOfArray(input,n);
402     printf("n"); 
403     
404     return 0;
405 }

tree traverse.c

连带参考

element-ui | 自个儿的博客

# -*- coding:utf-8 -*-
# 日期:2018/6/12 8:37
# Author:小鼠标

# 节点对象
class Node:
  def __init__(self):
    self.left_children = None
    self.left_height = 0
    self.right_children = None
    self.right_height = 0
    self.value = None

# 二叉树对象
class tree:
  def __init__(self):
    self.root = False
    self.front_list = []
    self.middle_list = []
    self.after_list = []
  # 生成二叉树
  def create_tree(self,n=0,l=[]):
    if l == []:
      print("传入的列表为空")
      return
    if n > len(l)-1:
      print("二叉树生成")
      return
    node = Node()
    node.value = l[n]
    if not self.root:
      self.root = node
      self.list = l
    else:
      self.add(self.root,node)
    self.create_tree(n+1,l)
  # 添加节点
  def add(self,parent,new_node):
    if new_node.value > parent.value:
      # 插入值比父亲值大,所以在父节点右边
      if parent.right_children == None:
        parent.right_children = new_node
        # 新插入节点的父亲节点的高度值为1,也就是子高度值0+1
        parent.right_height = 1
        # 插入值后 从下到上更新节点的height
      else:
        self.add(parent.right_children,new_node)
        # 父亲节点的右高度等于右孩子,左右高度中较大的值 + 1
        parent.right_height = max(parent.right_children.right_height, parent.right_children.left_height) + 1
        # ======= 此处开始判断平衡二叉树=======
        # 右边高度大于左边高度 属于右偏
        if parent.right_height - parent.left_height >= 2:
          self.right_avertence(parent)
    else:
      # 插入值比父亲值小,所以在父节点左边
      if parent.left_children == None:
        parent.left_children = new_node
        parent.left_height = 1
      else:
        self.add(parent.left_children,new_node)
        parent.left_height = max(parent.left_children.right_height, parent.left_children.left_height) + 1
        # ======= 此处开始判断平衡二叉树=======
        # 左边高度大于右边高度 属于左偏
        if parent.left_height - parent.right_height >= 2:
          self.left_avertence(parent)
  # 更新当前节点下的所有节点的高度
  def update_height(self,node):
    # 初始化节点高度值为0
    node.left_height = 0
    node.right_height = 0
    # 是否到最底层的一个
    if node.left_children == None and node.right_children == None:
      return
    else:
      if node.left_children:
        self.update_height(node.left_children)
        # 当前节点的高度等于左右子节点高度的较大值 + 1
        node.left_height = max(node.left_children.left_height,node.left_children.right_height) + 1
      if node.right_children:
        self.update_height(node.right_children)
        # 当前节点的高度等于左右子节点高度的较大值 + 1
        node.right_height = max(node.right_children.left_height, node.right_children.right_height) + 1
      # 检查是否仍有不平衡
      if node.left_height - node.right_height >= 2:
        self.left_avertence(node)
      elif node.left_height - node.right_height <= -2:
        self.right_avertence(node)

  def right_avertence(self,node):
    # 右偏 就将当前节点的最左节点做父亲
    new_code = Node()
    new_code.value = node.value
    new_code.left_children = node.left_children
    best_left = self.best_left_right(node.right_children)
    v = node.value
    # 返回的对象本身,
    if best_left == node.right_children and best_left.left_children == None:
      # 说明当前节点没有有节点
      node.value = best_left.value
      node.right_children = best_left.right_children
    else:
      node.value = best_left.left_children.value
      best_left.left_children = best_left.left_children.right_children
    node.left_children = new_code
    self.update_height(node)

  # 处理左偏情况
  def left_avertence(self,node):
    new_code = Node()
    new_code.value = node.value
    new_code.right_children = node.right_children
    best_right = self.best_left_right(node.left_children,1)
    v = node.value
    # 返回的对象本身,
    if best_right == node.left_children and best_right.right_children == None:
      # 说明当前节点没有有节点
      node.value = best_right.value
      node.left_children = best_right.left_children
    else:
      node.value = best_right.right_children.value
      best_right.right_children = best_right.right_children.left_children
    node.right_children = new_code
    self.update_height(node)
  # 返回node节点最左(右)子孙的父级
  def best_left_right(self,node,type=0):
    # type=0 默认找最左子孙
    if type == 0:
      if node.left_children == None:
        return node
      elif node.left_children.left_children == None:
        return node
      else:
        return self.best_left_right(node.left_children,type)
    else:
      if node.right_children == None:
        return node
      elif node.right_children.right_children == None:
        return node
      else:
        return self.best_left_right(node.right_children,type)
  # 前序(先中再左最后右)
  def front(self,node=None):
    if node == None:
      self.front_list = []
      node = self.root
    # 输出当前节点
    self.front_list.append(node.value)
    # 先判断左枝
    if not node.left_children == None:
      self.front(node.left_children)
    # 再判断右枝
    if not node.right_children == None:
      self.front(node.right_children)
    # 返回最终结果
    return self.front_list
  # 中序(先左再中最后右)
  def middle(self,node=None):
    if node == None:
      node = self.root
    # 先判断左枝
    if not node.left_children == None:
      self.middle(node.left_children)
    # 输出当前节点
    self.middle_list.append(node.value)
    # 再判断右枝
    if not node.right_children == None:
      self.middle(node.right_children)
    return self.middle_list
  # 后序(先左再右最后中)
  def after(self,node=None):
    if node == None:
      node = self.root
    # 先判断左枝
    if not node.left_children == None:
      self.after(node.left_children)
    # 再判断右枝
    if not node.right_children == None:
      self.after(node.right_children)
    self.after_list.append(node.value)
    return self.after_list
  # 节点删除
  def del_node(self,v,node=None):
    if node == None:
      node = self.root
      # 删除根节点
      if node.value == v:
        self.del_root(self.root)
        return
    # 删除当前节点的左节点
    if node.left_children:
      if node.left_children.value == v:
        self.del_left(node)
        return
    # 删除当前节点的右节点
    if node.right_children:
      if node.right_children.value == v:
        self.del_right(node)
        return
    if v > node.value:
      if node.right_children:
        self.del_node(v, node.right_children)
      else:
        print("删除的元素不存在")
    else:
      if node.left_children:
        self.del_node(v, node.left_children)
      else:
        print("删除的元素不存在")
  #删除当前节点的右节点
  def del_right(self,node):
    # 情况1 删除节点没有右枝
    if node.right_children.right_children == None:
      node.right_children = node.right_children.left_children
    else:
      best_left = self.best_left_right(node.right_children.right_children)
      # 表示右枝最左孙就是右枝本身
      if best_left == node.right_children.right_children and best_left.left_children == None:
        node.right_children.value = best_left.value
        node.right_children.right_children = best_left.right_children
      else:
        node.right_children.value = best_left.left_children.value
        best_left.left_children = best_left.left_children.right_children
  # 删除当前节点的左节点
  def del_left(self,node):
    # 情况1 删除节点没有右枝
    if node.left_children.right_children == None:
      node.left_children = node.left_children.left_children
    else:
      best_left = self.best_left_right(node.left_children.right_children)
      # 表示右枝最左子孙就是右枝本身
      if best_left == node.left_children.right_children and best_left.left_children == None:
        node.left_children.value = best_left.value
        node.left_children.right_children = best_left.right_children
      else:
        node.left_children.value = best_left.left_children.value
        best_left.left_children = best_left.left_children.right_children
  # 删除根节点
  def del_root(self,node):
    if node.right_children == None:
      if node.left_children == None:
        node.value = None
      else:
        self.root = node.left_children
    else:
      best_left = self.best_left_right(node.right_children)
      # 表示右枝最左子孙就是右枝本身
      if best_left == node.right_children and best_left.left_children == None:
        node.value = best_left.value
        node.right_children = best_left.right_children
      else:
        node.value = best_left.left_children.value
        best_left.left_children = best_left.left_children.right_children

  # 搜索
  def search(self,v,node=None):
    if node == None:
      node = self.root
    if node.value == v:
      return True
    if v > node.value:
      if not node.right_children == None:
        return self.search(v, node.right_children)
    else:
      if not node.left_children == None:
        return self.search(v, node.left_children)
    return False
if __name__ == '__main__':
  # 需要建立二叉树的列表
  list = [4, 6, 3, 1, 7, 9, 8, 5, 2]
  t = tree()
  t.create_tree(0,list)
  res = t.front()
  print('前序', res)

销毁

  通过遍历来销毁:后序递归遍历;后序非递归遍历(那个时候栈中保存了现阶段节点的父阿妈节点到根节点的具有节点)

何宏伟

将最右节点的左枝给予其父节点的右枝

性质

1、节点数=度数+1

2、第i层节点数:2(i-1),i≥1

3、高为i的二叉树节点数最多:2i-1,i≥1

4、n个节点的二叉树深度最小为:ceil( log2(n+1卡塔尔国卡塔尔(قطر‎,为白玉无瑕平衡二叉树时取最小值

5、度为0的节点数=度为2的节点数+1。(因为 节列举n=n0+n1+n2 且 分支数 n-1=n1+2n2,联立可得之)

6、n个节点的完全二叉树从1起对节点从上到下从左到右的号子,编号为i的节点:父节点编号为 floor(i/2卡塔尔,除非该节点已为父节点;左孩子节点编号为2i,除非2i>n即该节点已为叶子节点;右孩子编号为2i+1,除非2i+1>n即右孩子不设有。

扩张,对于截然m叉树编号为i的节点,其父节点编号为 floor((i+m-2卡塔尔(قطر‎/m ),第j个男女编辑号为 mi+j-m+1 。

1℃ 二叉树的遍历

二叉树,各个节点最多有多少个子树的树形构造,多少个子树被喻为左子树 | 右子树

从逻辑上来看,二叉树是递归定义的,直观的来看有5中基本类型:

图片 24

5 types

  • a - 空树,未有其余节点
  • b - 独有叁个父节点
  • c - 唯有左子树
  • d - 唯有右子树
  • e - 既有左子树也可以有右子树

二叉树的递归天性动手,大家能够十分轻便的写出二叉树的遍历,平时常有3中遍历(这里就不实行详细概念了,只简轻易单介绍):前序遍历,中序遍历,后序遍历

  • 前序遍历 - 先访问根节点,再拜望左子树,再拜见右子树
  • 中序遍历 - 先访问左子树,再拜望根节点,再拜望右子树
  • 前序遍历 - 先访谈左子树,再拜候右子树,再拜会根节点

很扎眼,贴合树的递归定义构造了3中遍历方式。

图片 25

示例图

Python代码示例 | C++代码示例

      图片 26

定义

具备n(n≥)个节点的周朝集结D与D上的关联合公司合福睿斯构成的构造T。即T:=(D,Escort卡塔尔(قطر‎。

树的逻辑表示法:树形表示、文氏图表示、凹入表示、嵌套括号表示。

有序树、无序树。

从自然抽象

二、左枝未有最右节点,

 1、树

[嵌牛导读]

多年来项目中接受了意气风发种树型控件

图片 27

Tree Directory

这种树形控件被采纳在此样的风貌:

  • 项目中单个配置亟待四个子级配置造成后才足以转移
  • 单个配置所含有的信息归属树形结构,雷同于“n叉树”

这种树形控件,其出示情势选取级联档次的树形方式,轻巧易行易懂,等级次序明显,配置显著。我们的身边这种树形目录太多太多,像书本的目录,word文书档案的目录,豆蔻梢头篇诗歌的目录,包罗HTML页面层层叠叠的节点等等,所以大家有不可能贫乏中间隔看看这棵树

大家得以反证一下:

建立

python 平衡二叉树实今世码示例。依照输入的系列创设设布局用二叉链表存款和储蓄的二叉树。此处假定连串为字符串,每种字符对应树中三个节点

输入:

第一说下补空,由输入系列(前缀、中缀、后缀皆可)创设二叉树时,假使类别里不曾标识一些节点甘休新闻,则是因为不能够辨识停止或怎么样是叶节点进而不能够由类别营造出树。所谓补空正是在体系中投入一些特殊字符如'#',加在哪?方式1:平常是系列对应的树的节点的空指针域中,也即度为1和0的节点的空孩子,那时候对此n个节点的体系其补空数为n+1;方式2:也可以只对度为1的节点补空。有意思的是只要输入系列是表明式,则用前种补空情势时唯有叶节点即操作数补空、用后种补空时髦未节点被补空。日常用前种办法补空,某个特殊情形下才用后世。

加括号:把根节点和其左右子树看成意气风发体,在其外围加上括号。

百言不比风流倜傥图,树T按章程1、2分别被补空为T1、T2:

图片 28

对输入体系:由单纯系列就想营造二叉树则须要类别包括补空音讯或连串本人蕴含额外信息(如前缀表明式类别操作符为内部节点操作数为叶节点),要下不补空就能够创设二叉树则需七个连串。

总结:(带括号补空:前、中、后序递归;   不带括号补空:前序递归、后序非递归、档次非递归;   不带括号不补空:前后缀表明式、前中序、中后序等),当中,由 不带括号内补空档案的次序类别营造二叉树最直观最适用,如LeetCode中与树有关的题目标输入。

1、平常来说,输入连串里必要包罗补空新闻,那个时候可使用 前序、中序、后序 遍历输入种类来树立二叉树,只要营造进度遍历选择的序与输入连串接收的序同样。分为二种状态:

1)带括号的补空体系(格局1或2)(可按章程1或2补空,不管是T1、T2,有多少个里头节点就有几个括号,即为T的节点数或内部节点数)

a、带括号、补空,前序体系(递归营造):

图片 29图片 30

 1 void createPreOrder_withBrackets(char prefix[],BTREE &T)
 2 {
 3 //要求输入的前缀序列带括号 ,并含有对度为0和1的节点的补空特殊字符。此时非特殊字符都成了“内部节点”,有几个非特殊字符就有几个括号。 
 4 //当然也可以只对度为1的补空,此时有几个非叶节点的非特殊字符就有几个括号。若输入的是前缀表达式,则此情况的内部节点其实就是操作符,叶节点是操作数。 
 5 //例子:度为0和1的补空:( A( B( D##) ( E( G#( H##) ) #) ) ( C( F##) #) ),只对度为1的补空:( A( BD( E( G#H )# ) )( CF# ) ) 
 6 //特殊例子(前缀表达式):度为0和1的补空:( *( +( A##) ( /( -( B##) ( C##) ) ( D##) ) ) ( E##) ) ,只对度为1的补空:(*(+A(/(-BC)D))E)
 7     char x=nextToken(prefix);
 8     
 9     if(x=='#')
10     {
11         T=NULL;
12     }
13     else
14     {
15         T=(BTREE)malloc(sizeof(BTNode));
16         T->lchild=NULL;
17         T->rchild=NULL;
18         
19         if(x=='(')
20         {//处理括号里的表达式 
21             x=nextToken(prefix);//表达式的操作符 
22             T->data=x;
23             
24             createPreOrder_withBrackets(prefix,T->lchild);//表达式的左操作数 
25             
26             createPreOrder_withBrackets(prefix,T->rchild);//表达式的右操作数 
27             
28             nextToken(prefix);//右括号 
29         }
30         else
31         {
32             T->data=x;
33         }        
34     }
35 }

createPreOrder_withBrackets

若输入按议程1补空,则括号数为T1的个中节点数即T的节点数,如 ( *( +( A##) ( /( -( B##) ( C##) ) ( D##) ) ) ( E##) ) 、 ( A( B( D##) ( E( G#( H##) ) #) ) ( C( F##) #) ) ;

若输入按章程2补空,则括号数为T2的当中节点数即T的中间节点数。如 (*(+A(/(-BC)D))E) 、 ( A( BD( E( G#H )# ) )( CF# 卡塔尔国 ),可以发掘前面三个就是前缀表明式,只可是多了括号。

能够开掘,无论哪类补空方式,括号数都是补空后的树的内部节点数。动脑筋,表达式树的此中节点都以操作符叶节点都以操作数,此中缀表达式的括号数正是操作符(内部节点)数,与这里的括号数有什么关系?

b、带括号、补空,中序类别(递归创设):与上临近,更换大器晚成行代码顺序就可以。

c、带括号、补空,中序类别(递归创设):同样,改造生龙活虎行代码顺序就可以。

输入示例:

|--------------------------------------------------------------------------------------------------------------------------------------------|

|                        情势1:度为1、0的节点补空             |  格局2:度为1的节点补空         |

|     前缀:( *( +( A##) ( /( -( B##) ( C##) ) ( D##) ) ) ( E##) )      |  (*(+A(/(-BC)D))E)                     |

| 示例1  中缀:( ( ( #A#) +( ( ( #B#) -( #C#) ) /( #D#) ) ) *( #E#) )       |  ((A+((B-C)/D))*E)                     |

|     后缀:(((##A)(((##B)(##C)-)(##D)/)+)(##E)*)          |  ((A((BC-)D/)+)E*)                     |

|---------------------------------------------------------------------------------------------------------------------------------------------|

|     前缀:( A( B( D##) ( E( G#( H##) ) #) ) ( C( F##) #) )     |  ( A( BD( E( G#H )# ) )( CF# ) )  |

| 示例2  中缀:( ( ( #D#) B( ( #G( #H#) ) E#) ) A( ( #F#) C#) )      |  ( ( DB( ( #GH )E# ) )A( FC# ) )  |

|     后缀:(((##D)((#(##H)G)#E)B)((##F)#C)A)          |  ( ( D( ( #HG )#E )B )( F#C )A )  |

|_____________________________________________________________________________________|

能够窥见,此种方法能对带括号的中缀表明式营造表达式树。

2)不带括号的补空体系(只可以方式1)。实际上本办法接受得最多,加括号是为着程序深入剖判但不便于人观察,括号数生机勃勃多不信你不会被搞蒙。。。

a、不带括号、全补空、前序种类(递归创设):

图片 31图片 32

 1 void createPreOrder(char prefixStr[],BTREE &T)
 2 {
 3     char x=nextToken(prefixStr);
 4     if(x=='#')
 5     {
 6         T=NULL;
 7     }
 8     else
 9     {
10         T=(BTREE)malloc(sizeof(BTNode));
11         T->data=x;
12         createPreOrder(prefixStr,T->lchild);
13         createPreOrder(prefixStr,T->rchild);
14     }
15 }

View Code

输入示例(上表第一列前序者去掉括号就能够): +A##/-B##C##D##E## 、 AB D## E G# H### C F## # 

b、不带括号,全补空、中序种类,能够发掘参数不管什么中序种类补空后每种字符左右均为#,所以其相应的树不唯后生可畏,故不带括号的中序补空种类无法创设树。

c、不带括号、全补空、后序种类(非递归构建):每境遇壹个非补空字符时为之创制一个新节点并从栈中取七个节点作为其子女

图片 33图片 34

 1 void createPostOrder(char infix[],BTREE &T)
 2 {// 
 3     int stackSize=100;
 4     BTREE stack[stackSize],p;
 5     int top=-1;
 6     char x;
 7     while(1)
 8     {
 9         x=nextToken(infix);
10         if(x=='')
11         {
12             break;
13         }
14         else if(x=='#')
15         {
16             stack[++top]=NULL;
17         }
18         else
19         {
20             p=(BTREE)malloc(sizeof(BTNode));
21             p->data=x;
22             p->lchild=stack[top-1];;
23             p->rchild=stack[top];
24             stack[top-1]=p;
25             top--;
26         }
27     }
28     T=stack[0];
29 }

View Code

输入示例(上表第一列后序者去掉括号就可以)

d、不带括号、按完全二叉树情势补空、等级次序遍历类别(非递归构建)

图片 35图片 36

 1 void createLayerOrder(char layerSeq[],int n,BTREE &T)
 2 {//输入序列是广度优先序列,且按完全二叉树形式补空,因为要利用父子节点间编号的关系。如 "12#34#####5"
 3     if(n<0) return;
 4 
 5     BTREE node[n];
 6     int i,j;
 7     for(i=0;i<n;i++)
 8     {
 9         if(layerSeq[i]!='#')
10         {
11             node[i]=(BTREE)malloc(sizeof(BTNode));
12             node[i]->data=layerSeq[i];
13             node[i]->lchild=NULL;
14             node[i]->rchild=NULL;
15             if(i==0)
16             {
17                 T=node[i];
18             }
19             else
20             {
21                 j=(i-1)/2;//父节点下标
22                 if(2*j+1==i)node[j]->lchild=node[i];//当前节点是父节点的左孩子
23                 else node[j]->rchild=node[i] ;//当前节点是父节点的右孩子 
24             }
25         }
26     }
27 }

View Code

e、不带括号、内补空、等级次序连串,最直接最常用

将内补空连串转为完全二叉树情势补空连串,然后按d管理或直接在转变的进度中创造:

图片 37图片 38

 1 //输入层次遍历序列(内补空),构建二叉树 
 2 void createLayerOrder2(char layerSeq[],int n,BTREE &T)
 3 {    
 4     //先将序列转为完全二叉树形式补空的序列 
 5     const int M=100;
 6     
 7     if(n<=0) return;
 8     
 9     char input[M];//node[]用于以完全二叉树形式存储节点
10     BTREE node[M];
11     
12     int i=0,nonBlank=0;
13     while(i<n)
14     {//统计非空字符数,作为下面循环结束的条件 
15         input[i]=layerSeq[i];
16         if(input[i]!='#')
17         {
18             nonBlank++;
19         }
20         i++;
21     }
22     
23     i=0;
24     int j;
25     while(nonBlank>0)
26     {
27         if(input[i]!='#')
28         {
29             nonBlank--;
30             {//法1,转换为完全二叉树补空形式过程中构建 
31                 node[i]=(BTREE)malloc(sizeof(BTNode));
32                 node[i]->data=input[i];
33                 node[i]->lchild=NULL;
34                 node[i]->rchild=NULL;
35                 if(i==0)
36                 {
37                     T=node[i];
38                 }
39                 else
40                 {
41                     j=(i-1)/2;
42                     if(2*j+1==i)node[j]->lchild=node[i];
43                     else if(2*j+2==i) node[j]->rchild=node[i];                
44                 }                
45             }
46         }
47         else
48         {
49             //后移两位 
50             for(j=n-1;j>=2*i+1;j--)
51             {
52                 input[j+2]=input[j];
53             }
54             n+=2;
55             input[2*i+1]='#';
56             input[2*i+2]='#';
57         }
58         i++;
59     }
60         
61 
62     {//法2,调用,根据完全二叉树形式补空序列构建二叉树 
63 //        input[n]='';
64 //        printf("%sn",input);
65 //        createLayerOrder(input,n,T) ;//输入二叉树形式补空的序列,构建二叉树 
66     }
67 }

View Code

2、要想输入时不需补空:

1)要么同期提供中序、前序系列 或 同不时间提供中序、后序序列或 同一时间提供中序、档期的顺序连串。

法豆蔻梢头(两种均可用此法):根据中序连串下标选取逐点插入法营造“二叉找寻树”——前序、档案的次序体系通首至尾各要素依次插入;后序系列从后到前各要素依次插入。

图片 39图片 40

 1 //根据 中序序列 和 后序|前序|层次序列 构建二叉树。采用逐点插入法构建“二叉搜索树”。 
 2 int cbiGetIndex(char inorder[],int n,char val)
 3 {//获取给定值在中序序列的下标 
 4     int i=0;
 5     while(i<n && inorder[i]!=val)
 6     {
 7         i++;
 8     }
 9     return i;
10 }
11 void cbiBuildBST(BTREE &T,char inorder[],int n,char val)
12 {//插入一个值到二叉搜索树 
13     if(T==NULL)
14     {
15         T=(BTREE)malloc(sizeof(BTNode));
16         T->data=val;
17         T->lchild=NULL;
18         T->rchild=NULL;
19     }
20     else if(cbiGetIndex(inorder,n,val) < cbiGetIndex(inorder,n,T->data))
21     {
22         cbiBuildBST(T->lchild,inorder,n,val);
23     }
24     else
25     {
26         cbiBuildBST(T->rchild,inorder,n,val);
27     }
28 }
29 void createByInAndOtherOrder(BTREE &T,char input[],int isInputPostOrder,char inorder[],int n)
30 {//根据 中序序列 和 后序|前序|层次序列 构建二叉树。采用逐点插入法构建“二叉搜索树”。 
31 printf("%s %dn",input,n);
32     int i;
33     if(isInputPostOrder)
34     {//若input是后序序列,从后往前依次插入各元素 
35         for(i=n-1;i>=0;i--)
36         {
37             cbiBuildBST(T,inorder,n,input[i]);
38         }
39     }
40     else{//否则input是前序或后序序列,从前往后依次插入各元素 
41         for(i=0;i<n;i++)
42         {
43             cbiBuildBST(T,inorder,n,input[i]);
44         }
45     }
46 }

View Code

法二(前二种可用此法):取前序连串首成分,找到在中序系列的岗位,此岗位分割成的左右两片段便是左子树和右子树,两部分的尺寸分别对应前序连串接下去两有些的长短,递归举办。

a、由前序、中序种类创设二叉树:(不带括号、不补空、递归营造)。

图片 41图片 42

 1 //由前序、中序序列(不补空不带括号)构建二叉树。有重复元素的话树不唯一,所以不能有重 
 2 void createByPreInOrder(BTREE &T,char preorder[],int preStart,int preEnd,char inorder[],int inStart,int inEnd) 
 3 {//求前序序列首元素在中序序列的位置,此位置左边为左子树序列、右边为右子树序列,两者的长度分别对应前序序列接下来的两段长度,接下来递归进行。 
 4     if(preStart>preEnd || inStart>inEnd || preEnd-preStart!=inEnd-inStart)
 5     {
 6         return;
 7     }
 8     
 9     //求前序序列首元素在中序序列的位置 及 中序序列被该元素分成的左右子序列的长度 
10     int pivot;
11     for(pivot=inStart; pivot<=inEnd && preorder[preStart]!=inorder[pivot];pivot++);
12     int leftLen=pivot-inStart;//位置左边的元素个数 
13     int rightLen=inEnd-pivot;//位置右边的元素个数 
14     
15     T=(BTREE)malloc(sizeof(BTNode));
16     T->data=preorder[preStart];
17     T->lchild=NULL;
18     T->rchild=NULL;
19     if(leftLen>0)
20     {
21         createByPreInOrder(T->lchild,preorder,  preStart+1,  preStart+1+leftLen-1,  inorder,  inStart,  pivot-1);
22     }
23     if(rightLen>0)
24     {
25         createByPreInOrder(T->rchild,preorder,  preStart+1+leftLen,  preEnd,  inorder,  pivot+1,  inEnd);
26     }
27 }

View Code

b、由后序、中序系列营造二叉树:(不带括号、不补空、递归构建)。与上述相似,只可是每一次取的是后序连串的末尾值来创设新节点

图片 43图片 44

 1 //由后序、中序序列(不补空不带括号)构建二叉树。有重复元素的话树不唯一,所以不能有重 
 2 void createByPostInOrder(BTREE &T,char postorder[],int postStart,int postEnd,char inorder[],int inStart,int inEnd) 
 3 {//求后序序列末元素在中序序列的位置,此位置左边为左子树序列、右边为右子树序列,两者的长度分别对应后序序列从首元素开始的两段长度,接下来递归进行。 
 4     if(postStart>postEnd || inStart>inEnd || postEnd-postStart!=inEnd-inStart)
 5     {
 6         return;
 7     }
 8     
 9     //求前序序列首元素在中序序列的位置 及 中序序列被该元素分成的左右子序列的长度 
10     int pivot;
11     for(pivot=inStart; pivot<=inEnd && postorder[postEnd]!=inorder[pivot];pivot++);
12     int leftLen=pivot-inStart;
13     int rightLen=inEnd-pivot;
14     
15     T=(BTREE)malloc(sizeof(BTNode));
16     T->data=postorder[postEnd];
17     T->lchild=NULL;
18     T->rchild=NULL;
19     if(leftLen>0)
20     {
21         createByPostInOrder(T->lchild,postorder,  postStart,  postStart+leftLen-1,  inorder,  inStart,  pivot-1);
22     }
23     if(rightLen>0)
24     {
25         createByPostInOrder(T->rchild,postorder,  postStart+leftLen,  postEnd-1,  inorder,  pivot+1,  inEnd);
26     }
27 }

View Code

注意:

若提供了二叉查找树的后序遍历系列则就可以营造出该树,因为二叉查找树的中序类别是雨后春笋的,大家能够从后序种类拿到中序连串;实际上,不获取也可,从后往前依次将各样成分插入就可以。(给定BST的前序系列时与此相通)。当时实际上是上述法后生可畏的独特情形。

2)要么连串本人包罗额外音讯:如前缀表达式或后缀表明式因操作符为此中节点操作数为叶节点,可直接依照系列之构建表明式树;带括号的中缀表明式(种种运算符都有对应的括号)括号能提供额外音信,由此也能平昔依照之建构树。

由表明式种类创设表明式树示例:由表明式系列构建表达式树-MarchOn(前缀、中缀递归,后缀非递归)

a、前缀表达式种类创设表达式树(不带括号、不补空、递归营造):

图片 45图片 46

 1 void createPrefix_recursive(char prefix[],BTREE &T)
 2 {//递归方式_由前缀表达式构建表达式树,输入示例:*+A/-BCDE
 3     char x=nextToken(prefix);
 4     
 5     T=(BTREE)malloc(sizeof(BTNode));
 6     T->data=x;
 7     T->lchild=NULL;
 8     T->rchild=NULL;
 9     
10     if(!isOpNum(x))//是操作符。前缀表达式的最后一个字符一定是操作数,所以下面的递归会停止。 
11     { 
12         createPrefix_recursive(prefix,T->lchild);
13         createPrefix_recursive(prefix,T->rchild);
14     }
15 }

View Code

输入示例: *+A/-BCDE 

b、中缀表达式种类构建表达式树(带括号、不补空,递归创设):直接用带括号补空的形式(1、1、b)中的方法。可是鉴于表达式树内部节点为操作符叶子节点为操作数空中楼阁为度为1的节点,所以创设格局能够微微简化:

图片 47图片 48

 1 void createInfix_recursive(char infix[],BTREE &T)
 2 {//递归方式_由中缀表达式构建表达式树,要求输入的中缀表达式加括号,有几个操作数就几个括号 
 3     char x=nextToken(infix);
 4     
 5     T=(BTREE)malloc(sizeof(BTNode));
 6     T->lchild=NULL;
 7     T->rchild=NULL;
 8     
 9     if(x=='(')
10     {//处理括号里的表达式 
11         createInfix_recursive(infix,T->lchild);//表达式的左操作数 
12         
13         x=nextToken(infix);//表达式的操作符 
14         T->data=x;
15         
16         createInfix_recursive(infix,T->rchild);//表达式的右操作数 
17         nextToken(infix);//右括号 
18     }
19     else
20     {
21         T->data=x;
22     }
23 }

View Code

输入示例: ((A+((B-CState of Qatar/D卡塔尔国State of Qatar*E) 

c、后缀表明式连串塑造表明式树(不带括号、不补空,非递归创设):

图片 49图片 50

 1 #define M 100
 2 void createPostfix_nonrecursive(char postfix[],BTREE &T)
 3 {//非递归方式_由后缀表达式构建表达式树 
 4     BTREE stack[M],p;
 5     int top=-1;
 6     char x;
 7     while(1)
 8     {
 9         x=nextToken(postfix);
10         if(x=='') 
11         {
12             break;
13         }
14         
15         p=(BTREE)malloc(sizeof(BTNode)) ;
16         p->data=x;
17         p->lchild=NULL;
18         p->rchild=NULL;
19         
20         if(isOpNum(x))
21         {//操作数 
22             stack[++top]=p;
23         }
24         else
25         {//操作符 
26             p->lchild=stack[top-1];
27             p->rchild=stack[top];
28             stack[top-1]=p;
29             top--;
30         }
31     }
32     T=stack[0];
33 }

View Code

输入示例: ABC-D/+E* 

此间计算了基于分歧输入情势塑造二叉树的议程,当碰着不是那么些情势的时,能够向那几个格局靠。如A( (B  ( D,E(G卡塔尔(قطر‎卡塔尔(قطر‎, C(F(,H卡塔尔国 卡塔尔国  卡塔尔国 State of Qatar

然则,也毫无那么死板局限于这里的办法,条条大路通休斯敦,明确还应该有其它措施的。

附:上述有关树创造的完好代码:

图片 51图片 52

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 typedef struct node
  4 {
  5     int data;
  6     struct node* lchild;
  7     struct node* rchild;
  8 }BTNode,*BTREE;
  9 
 10 
 11 //遍历 
 12 
 13 void searchPrefix(BTREE T)
 14 {
 15     if(T!=NULL)
 16     { 
 17         printf("%c",T->data);
 18         
 19         searchPrefix(T->lchild);
 20         
 21         searchPrefix(T->rchild);
 22     }
 23 }
 24 void searchInfix(BTREE T)
 25 {
 26     if(T!=NULL)
 27     {//访问到内部节点时左右加括号 ,因此几个内部节点就有几个括号,如果树是表达式树 ,则得到了带括号的中缀表达式 
 28 //        if(T->lchild!=NULL || T->rchild!=NULL){   printf("( ");   }
 29         searchInfix(T->lchild);
 30 //        if((T->lchild!=NULL || T->rchild!=NULL) && (T->lchild==NULL)){   printf("#");   }//内部节点的空孩子用特殊符号代替 
 31         
 32         printf("%c",T->data);
 33         
 34         searchInfix(T->rchild);
 35 //        if((T->lchild!=NULL || T->rchild!=NULL) && (T->rchild==NULL)){   printf("#");   }//内部节点的空孩子用特殊符号代替 
 36 //        if(T->lchild!=NULL || T->rchild!=NULL){  printf(" )");  }
 37     }
 38 }
 39 void searchPostfix(BTREE T)
 40 {
 41     if(T!=NULL)
 42     {//访问到内部节点时左右加括号 ,因此几个内部节点就有几个括号,如果树是表达式树 ,则得到了带括号的后缀表达式
 43 //        if(T->lchild!=NULL || T->rchild!=NULL){   printf("( ");   }
 44         searchPostfix(T->lchild);
 45 //        if((T->lchild!=NULL || T->rchild!=NULL) && (T->lchild==NULL)){   printf("#");   }//内部节点的空孩子用特殊符号代替 
 46         
 47         searchPostfix(T->rchild);
 48 //        if((T->lchild!=NULL || T->rchild!=NULL) && (T->rchild==NULL)){   printf("#");   }//内部节点的空孩子用特殊符号代替 
 49         
 50         printf("%c",T->data);
 51 //        if(T->lchild!=NULL || T->rchild!=NULL){  printf(" )");  }
 52     }
 53 }
 54 
 55 
 56 //构建 
 57 char nextToken(char str[]) //读取下一字符,略过空格 
 58 {
 59     static int pos=0;
 60     while(str[pos]!='' && str[pos]==' '){ pos++; }
 61     return str[pos++];
 62 }
 63 
 64 
 65 void createPreOrder_withBrackets_c(char prefix[],BTREE *T)
 66 {//为了能更改T,这里采用了指针,为了更清晰简洁,可以用C++里的引用 
 67     char x=nextToken(prefix);
 68     
 69     if(x=='#')
 70     {
 71         *T=NULL;
 72     }
 73     else
 74     {
 75         *T=(BTREE)malloc(sizeof(BTNode));
 76         (*T)->lchild=NULL;
 77         (*T)->rchild=NULL;
 78         
 79         if(x=='(')
 80         {//处理括号里的表达式 
 81             x=nextToken(prefix);//表达式的操作符 
 82             (*T)->data=x;
 83             
 84             createPreOrder_withBrackets_c(prefix,&((*T)->lchild));//表达式的左操作数 
 85             
 86             createPreOrder_withBrackets_c(prefix,&((*T)->rchild));//表达式的右操作数 
 87             
 88             nextToken(prefix);//右括号 
 89         }
 90         else
 91         {
 92             (*T)->data=x;
 93         }        
 94     }
 95 }
 96 
 97 void createPreOrder_withBrackets(char prefix[],BTREE &T)
 98 {
 99 //要求输入的前缀序列带括号 ,并含有对度为0和1的节点的补空特殊字符。此时非特殊字符都成了“内部节点”,有几个非特殊字符就有几个括号。 
100 //当然也可以只对度为1的补空,此时有几个非叶节点的非特殊字符就有几个括号。若输入的是前缀表达式,则此情况的内部节点其实就是操作符,叶节点是操作数。 
101 //例子:度为0和1的补空:( A( B( D##) ( E( G#( H##) ) #) ) ( C( F##) #) ),只对度为1的补空:( A( BD( E( G#H )# ) )( CF# ) ) 
102 //特殊例子(前缀表达式):度为0和1的补空:( *( +( A##) ( /( -( B##) ( C##) ) ( D##) ) ) ( E##) ) ,只对度为1的补空:(*(+A(/(-BC)D))E)
103     char x=nextToken(prefix);
104     
105     if(x=='#')
106     {
107         T=NULL;
108     }
109     else
110     {
111         T=(BTREE)malloc(sizeof(BTNode));
112         T->lchild=NULL;
113         T->rchild=NULL;
114         
115         if(x=='(')
116         {//处理括号里的表达式 
117             x=nextToken(prefix);//表达式的操作符 
118             T->data=x;
119             
120             createPreOrder_withBrackets(prefix,T->lchild);//表达式的左操作数 
121             
122             createPreOrder_withBrackets(prefix,T->rchild);//表达式的右操作数 
123             
124             nextToken(prefix);//右括号 
125         }
126         else
127         {
128             T->data=x;
129         }        
130     }
131 }
132 
133 void createInOrder_withBrackets(char infix[],BTREE &T)
134 {//要求输入的序列带括号 ,内部节点才带括号;度为1的节点缺失的孩子补特殊字符(度为0的可补可不补) 
135     char x=nextToken(infix);
136     
137     if(x=='#')
138     {
139         T=NULL;
140     }
141     else
142     {
143         T=(BTREE)malloc(sizeof(BTNode));
144         T->lchild=NULL;
145         T->rchild=NULL;
146         
147         if(x=='(')
148         {//处理括号里的表达式 
149             createInOrder_withBrackets(infix,T->lchild);//表达式的左操作数 
150             
151             x=nextToken(infix);//表达式的操作符 
152             T->data=x;
153             
154             createInOrder_withBrackets(infix,T->rchild);//表达式的右操作数 
155             
156             nextToken(infix);//右括号 
157         }
158         else
159         {
160             T->data=x;
161         }
162     }
163 }
164 
165 void createPostOrder_withBrackets(char infix[],BTREE &T)
166 {//要求输入的序列带括号 ,内部节点才带括号;度为1的节点缺失的孩子补特殊字符(度为0的可补可不补) 
167     char x=nextToken(infix);
168 
169     if(x=='#')
170     {
171         T=NULL;
172     }
173     else
174     {
175         T=(BTREE)malloc(sizeof(BTNode));
176         T->lchild=NULL;
177         T->rchild=NULL;
178         
179         if(x=='(')
180         {//处理括号里的表达式 
181             createPostOrder_withBrackets(infix,T->lchild);//表达式的左操作数 
182     
183             createPostOrder_withBrackets(infix,T->rchild);//表达式的右操作数 
184             
185             x=nextToken(infix);//表达式的操作符 
186             T->data=x;
187     
188             nextToken(infix);//右括号         
189         }
190         else
191         {
192             T->data=x;
193         }
194     }
195 }
196 
197 void createPreOrder(char prefixStr[],BTREE &T)
198 {//输入序列为 全补空、不带括号 的序列 
199     char x=nextToken(prefixStr);
200     if(x=='#')
201     {
202         T=NULL;
203     }
204     else
205     {
206         T=(BTREE)malloc(sizeof(BTNode));
207         T->data=x;
208         createPreOrder(prefixStr,T->lchild);
209         createPreOrder(prefixStr,T->rchild);
210     }
211 }
212 
213 
214 void createPostOrder(char infix[],BTREE &T)
215 {// 输入序列为 全补空、不带括号 的序列 
216     int stackSize=100;
217     BTREE stack[stackSize],p;
218     int top=-1;
219     char x;
220     while(1)
221     {
222         x=nextToken(infix);
223         if(x=='')
224         {
225             break;
226         }
227         else if(x=='#')
228         {
229             stack[++top]=NULL;
230         }
231         else
232         {
233             p=(BTREE)malloc(sizeof(BTNode));
234             p->data=x;
235             p->lchild=stack[top-1];;
236             p->rchild=stack[top];
237             stack[top-1]=p;
238             top--;
239         }
240     }
241     T=stack[0];
242 }
243 
244 //输入层次遍历序列(全补空),构建二叉树 
245 void createLayerOrder(char layerSeq[],int n,BTREE &T)
246 {//输入序列是广度优先序列,且按完全二叉树形式补空,因为要利用父子节点间编号的关系。如 "12#34#####5"
247 //构建后的实际节点数≤n 
248     if(n<=0) return;
249 
250     BTREE node[n];
251     int i,j;
252     for(i=0;i<n;i++)
253     {
254         if(layerSeq[i]!='#')
255         {
256             node[i]=(BTREE)malloc(sizeof(BTNode));
257             node[i]->data=layerSeq[i];
258             node[i]->lchild=NULL;
259             node[i]->rchild=NULL;
260             if(i==0)
261             {
262                 T=node[i];
263             }
264             else
265             {
266                 j=(i-1)/2;//父节点下标
267                 if(2*j+1==i)node[j]->lchild=node[i];//当前节点是父节点的左孩子
268                 else node[j]->rchild=node[i] ;//当前节点是父节点的右孩子 
269             }
270         }
271     }
272 }
273 
274 //输入层次遍历序列(内补空),构建二叉树 
275 void createLayerOrder2(char layerSeq[],int n,BTREE &T)
276 {    
277     //先将序列转为完全二叉树形式补空的序列 
278     const int M=100;
279     
280     if(n<=0) return;
281     
282     char input[M];//node[]用于以完全二叉树形式存储节点
283     BTREE node[M];
284     
285     int i=0,nonBlank=0;
286     while(i<n)
287     {//统计非空字符数,作为下面循环结束的条件 
288         input[i]=layerSeq[i];
289         if(input[i]!='#')
290         {
291             nonBlank++;
292         }
293         i++;
294     }
295     
296     i=0;
297     int j;
298     while(nonBlank>0)
299     {
300         if(input[i]!='#')
301         {
302             nonBlank--;
303             {//法1,转换为完全二叉树补空形式过程中构建 
304                 node[i]=(BTREE)malloc(sizeof(BTNode));
305                 node[i]->data=input[i];
306                 node[i]->lchild=NULL;
307                 node[i]->rchild=NULL;
308                 if(i==0)
309                 {
310                     T=node[i];
311                 }
312                 else
313                 {
314                     j=(i-1)/2;
315                     if(2*j+1==i)node[j]->lchild=node[i];
316                     else if(2*j+2==i) node[j]->rchild=node[i];                
317                 }                
318             }
319         }
320         else
321         {
322             //后移两位 
323             for(j=n-1;j>=2*i+1;j--)
324             {
325                 input[j+2]=input[j];
326             }
327             n+=2;
328             input[2*i+1]='#';
329             input[2*i+2]='#';
330         }
331         i++;
332     }
333         
334 
335     {//法2,调用,根据完全二叉树形式补空序列构建二叉树 
336 //        input[n]='';
337 //        printf("%sn",input);
338 //        createLayerOrder(input,n,T) ;//输入二叉树形式补空的序列,构建二叉树 
339     }
340 }
341 
342 //由前序、中序序列(不补空不带括号)构建二叉树。有重复元素的话树不唯一,所以不能有重 
343 void createByPreInOrder(BTREE &T,char preorder[],int preStart,int preEnd,char inorder[],int inStart,int inEnd) 
344 {//求前序序列首元素在中序序列的位置,此位置左边为左子树序列、右边为右子树序列,两者的长度分别对应前序序列接下来的两段长度,接下来递归进行。 
345     if(preStart>preEnd || inStart>inEnd || preEnd-preStart!=inEnd-inStart)
346     {
347         return;
348     }
349     
350     //求前序序列首元素在中序序列的位置 及 中序序列被该元素分成的左右子序列的长度 
351     int pivot;
352     for(pivot=inStart; pivot<=inEnd && preorder[preStart]!=inorder[pivot];pivot++);
353     int leftLen=pivot-inStart;//位置左边的元素个数 
354     int rightLen=inEnd-pivot;//位置右边的元素个数 
355     
356     T=(BTREE)malloc(sizeof(BTNode));
357     T->data=preorder[preStart];
358     T->lchild=NULL;
359     T->rchild=NULL;
360     if(leftLen>0)
361     {
362         createByPreInOrder(T->lchild,preorder,  preStart+1,  preStart+1+leftLen-1,  inorder,  inStart,  pivot-1);
363     }
364     if(rightLen>0)
365     {
366         createByPreInOrder(T->rchild,preorder,  preStart+1+leftLen,  preEnd,  inorder,  pivot+1,  inEnd);
367     }
368 }
369 
370 //由后序、中序序列(不补空不带括号)构建二叉树。有重复元素的话树不唯一,所以不能有重 
371 void createByPostInOrder(BTREE &T,char postorder[],int postStart,int postEnd,char inorder[],int inStart,int inEnd) 
372 {//求后序序列末元素在中序序列的位置,此位置左边为左子树序列、右边为右子树序列,两者的长度分别对应后序序列从首元素开始的两段长度,接下来递归进行。 
373     if(postStart>postEnd || inStart>inEnd || postEnd-postStart!=inEnd-inStart)
374     {
375         return;
376     }
377     
378     //求前序序列首元素在中序序列的位置 及 中序序列被该元素分成的左右子序列的长度 
379     int pivot;
380     for(pivot=inStart; pivot<=inEnd && postorder[postEnd]!=inorder[pivot];pivot++);
381     int leftLen=pivot-inStart;
382     int rightLen=inEnd-pivot;
383     
384     T=(BTREE)malloc(sizeof(BTNode));
385     T->data=postorder[postEnd];
386     T->lchild=NULL;
387     T->rchild=NULL;
388     if(leftLen>0)
389     {
390         createByPostInOrder(T->lchild,postorder,  postStart,  postStart+leftLen-1,  inorder,  inStart,  pivot-1);
391     }
392     if(rightLen>0)
393     {
394         createByPostInOrder(T->rchild,postorder,  postStart+leftLen,  postEnd-1,  inorder,  pivot+1,  inEnd);
395     }
396 }
397 
398 //根据 中序序列 和 后序|前序|层次序列 构建二叉树。采用逐点插入法构建“二叉搜索树”。 
399 int cbiGetIndex(char inorder[],int n,char val)
400 {//获取给定值在中序序列的下标 
401     int i=0;
402     while(i<n && inorder[i]!=val)
403     {
404         i++;
405     }
406     return i;
407 }
408 void cbiBuildBST(BTREE &T,char inorder[],int n,char val)
409 {//插入一个值到二叉搜索树 
410     if(T==NULL)
411     {
412         T=(BTREE)malloc(sizeof(BTNode));
413         T->data=val;
414         T->lchild=NULL;
415         T->rchild=NULL;
416     }
417     else if(cbiGetIndex(inorder,n,val) < cbiGetIndex(inorder,n,T->data))
418     {
419         cbiBuildBST(T->lchild,inorder,n,val);
420     }
421     else
422     {
423         cbiBuildBST(T->rchild,inorder,n,val);
424     }
425 }
426 void createByInAndOtherOrder(BTREE &T,char input[],int isInputPostOrder,char inorder[],int n)
427 {//根据 中序序列 和 后序|前序|层次序列 构建二叉树。采用逐点插入法构建“二叉搜索树”。 
428 printf("%s %dn",input,n);
429     int i;
430     if(isInputPostOrder)
431     {//若input是后序序列,从后往前依次插入各元素 
432         for(i=n-1;i>=0;i--)
433         {
434             cbiBuildBST(T,inorder,n,input[i]);
435         }
436     }
437     else{//否则input是前序或后序序列,从前往后依次插入各元素 
438         for(i=0;i<n;i++)
439         {
440             cbiBuildBST(T,inorder,n,input[i]);
441         }
442     }
443 }
444 
445 //二叉查找树创建、查找、删除(递归、非递归) 
446 void insertBinarySearchTree_nonrecursive(BTREE &T,char item)
447 {
448     BTREE p,q;
449     p=(BTREE)malloc(sizeof(BTNode));
450     p->data=item;
451     p->lchild=NULL;
452     p->rchild=NULL;
453     if(T==NULL) T=p;
454     else
455     {
456         q=T;
457         while(1)
458         {
459             if(item < q->data)
460             {
461                 if(q->lchild!=NULL) q=q->lchild;
462                 else
463                 {
464                     q->lchild=p;
465                     break;
466                 }
467             }
468             else
469             {
470                 if(q->rchild!=NULL) q=q->rchild;
471                 else
472                 {
473                     q->rchild=p;
474                     break;
475                 }
476             }
477         }
478     }
479 }
480 void insertBinarySearchTree_recursive(BTREE &T,char item)
481 {
482     if(T==NULL)
483     {
484         T=(BTREE)malloc(sizeof(BTNode));
485         T->data=item;
486         T->lchild=NULL;
487         T->rchild=NULL;    
488     }
489     else if(item< T->data)
490     {
491         insertBinarySearchTree_recursive(T->lchild,item);
492     }
493     else
494     {
495         insertBinarySearchTree_recursive(T->rchild,item);
496     }
497 }
498 
499 BTREE searchBinarySearchTree_nonrecursive(BTREE T,char item)
500 {
501     if(T==NULL)
502         return NULL;
503     BTREE p=T;
504     while(p!=NULL)
505     {
506         if(p->data==item)
507             return p;
508         else if(p->data<item)
509             p=p->lchild;
510         else
511             p=p->rchild;
512     }
513 }
514 
515 BTREE searchBinarySearchTree_recursive(BTREE T,char item)
516 {
517     if(T==NULL || T->data==item)
518         return T;
519     else if(T->data < item)
520         searchBinarySearchTree_recursive(T->lchild,item);
521     else
522         searchBinarySearchTree_recursive(T->rchild,item);
523 }
524 
525 void deleteBSTNode(BTREE &T,char key)
526 {//删除二叉查找树中的一个节点。也可以借助后序非递归遍历来实现 ,此时栈顶元素存在的话为当前节点的父节点 
527     if(T==NULL)return;
528     else if(key<T->data)deleteBSTNode(T->lchild,key);
529     else if(key>T->data)deleteBSTNode(T->rchild,key);
530     else
531     {
532         if(T->lchild==NULL)
533         {
534             BTREE tmp=T;
535             T=T->rchild;
536             free(tmp); 
537         } 
538         else if(T->rchild==NULL)
539         {
540             BTREE tmp=T;
541             T=T->lchild;
542             free(tmp) ;
543         } 
544         else
545         {
546             //找右子树的最小节点(最左边)的值替换被删节点的值
547             BTREE p=T->rchild;
548             while(p->lchild!=NULL)
549             {
550                 p=p->lchild;
551             }
552             T->data=p->data;
553             deleteBSTNode(T->rchild,p->data);
554             
555             //也可以找左子树最右的值
556 //            BTREE p=T->lchild;
557 //            while(p->lchild!=NULL)
558 //            {
559 //                p=p->lchild;
560 //            }
561 //            T->data=p->data;
562 //            deleteBSTNode(T->lchild,p->data);
563         }
564     }
565 }
566 
567 void createBinarySearchTree(BTREE &T,char input[],int n)
568 {
569     int i;
570     for(i=0;i<n;i++)
571     {
572         insertBinarySearchTree_nonrecursive(T,input[i]);
573 //        insertBinarySearchTree_recursive(T,input[i]);
574     }
575     
576     for(i=0;i<n;i++)
577     {//验证递归查找和非递归查找的正确性 
578         if(searchBinarySearchTree_nonrecursive(T,input[i])!=searchBinarySearchTree_recursive(T,input[i]))
579         {
580             printf("error in searchBinarySearchTreen");
581         }
582     }
583 }
584 
585 
586 
587 int main()
588 {
589 
590     //测试1,特殊序列(表达式 )。度为1的节点空孩子一定要补空,度为0的可以不补;由于表达式内部节点为操作符度都为故不需要补空 
591     
592     //度为1的节点补空 
593     //(*(+A(/(-BC)D))E)
594     //((A+((B-C)/D))*E)
595     //((A((BC-)D/)+)E*)
596     
597     //度为1、0的节点补空 
598     //( *( +( A##) ( /( -( B##) ( C##) ) ( D##) ) ) ( E##) )
599     //( ( ( #A#) +( ( ( #B#) -( #C#) ) /( #D#) ) ) *( #E#) )
600     //(((##A)(((##B)(##C)-)(##D)/)+)(##E)*)
601     
602     //测试2,普通序列 
603     
604     //度为1的节点补空
605     //( A( BD( E( G#H )# ) )( CF# ) )
606     //( ( DB( ( #GH )E# ) )A( FC# ) )
607     //( ( D( ( #HG )#E )B )( F#C )A )
608     
609     //度为1、0的节点补空
610     //( A( B( D##) ( E( G#( H##) ) #) ) ( C( F##) #) )
611     //( ( ( #D#) B( ( #G( #H#) ) E#) ) A( ( #F#) C#) )
612     //(((##D)((#(##H)G)#E)B)((##F)#C)A)
613     
614 
615     
616     //测试1,特殊序列(表达式 ) ,度为1、0的节点都得补空 
617     //*+A##/-B##C##D##E##
618     //#A#+#B#-#C#/#D#*#E#
619     //##A##B##C-##D/+##E*
620     
621     //测试2,普通序列 ,度为1、0的节点都得补空 
622     //ABD##EG#H###CF###
623     //#D#B#G#H#E#A#F#C#
624     //##D###HG#EB##F#CA
625 
626     BTREE T=NULL;
627     
628     //加括号:全补空或内补空,前缀、中缀、后缀 
629 //    char str[]="(*(+A(/(-BC)D))E)";    
630 //char str[]="(  *(+(A##)(/(-(B##)(C##))(D##)))(E##)  )";
631 //    char str[]="( A( BD( E( G#H )# ) )( CF# ) )";
632 //char str[]="( A( B( D##) ( E( G#( H##) ) #) ) ( C( F##) #) )"; 
633 //    createPreOrder_withBrackets(str,T);
634 
635 //    char str[]="((A+((B-C)/D))*E)";    
636 //    char str[]="( ( DB( ( #GH )E# ) )A( FC# ) )";
637 //char str[]="( ( ( #A#) +( ( ( #B#) -( #C#) ) /( #D#) ) ) *( #E#) )";
638 //    createInOrder_withBrackets(str,T);
639 
640 //    char str[]="(  ( A((BC-)D/)+ )E* )";
641 //char str[]="(((##A)(((##B)(##C)-)(##D)/)+)(##E)*)";
642 //    char str[]="( ( D( ( #HG )#E )B )( F#C )A )";
643 //    createPostOrder_withBrackets(str,T);
644 
645 
646     //不加括号:全补空 ,前缀、后缀、广度优先 
647 //    char str[]="*+A##/-B##C##D##E##";
648 //    char str[]="AB D## E G# H### C F## #";
649 //    createPreOrder(str,T);
650     
651 //    char str[]="#A#+#B#-#C#/#D#*#E#";//不带括号的中序序列的树是不唯一的,所以没法构建 
652 //    char str[]="#D#B#G#H#E#A#F#C#";
653 //    createInOrder(str,T);    
654 
655 //    char str[]="##A##B##C-##D/+##E*";
656 //    char str[]="##D # ##H G#EB##F#CA";
657 //    createPostOrder(str,T);
658 
659 //    char layerSeq[]="12#34#####5";
660 //    createLayerOrder(layerSeq,sizeof(layerSeq)/sizeof(char)-1,T);//广度优先、二叉树形式补空 
661     char layerSeq2[]="12#34###5";
662     createLayerOrder2(layerSeq2,sizeof(layerSeq2)/sizeof(char)-1,T);//广度优先、内补空 。可以将序列转换为完全二叉树形式补空再用上述方法构建,也可以在转换过程中构建。 
663 
664     //由前序、中序序列 或 后序、中序序列 或 中序、层次序列 构建二叉树。不补空、不加括号。 
665     char inorder[]="254163";
666     char preorder[]="124536";
667     char postorder[]="542631";
668     char layerorder[]="123465";
669 //    createByInAndOtherOrder(T,postorder,1,inorder,sizeof(inorder)-1);//法1,三种输入方式都可用此法构建二叉树 
670 //    createByInAndOtherOrder(T,preorder,0,inorder,sizeof(inorder)-1);
671 //    createByInAndOtherOrder(T,layerorder,0,inorder,sizeof(inorder)-1);
672 //    createByPreInOrder(T,preorder,0,sizeof(preorder)-1-1,inorder,0,sizeof(inorder)-1-1) ;//法2,知道前序、中序 
673 //    createByPostInOrder(T,postorder,0,sizeof(postorder)-1-1,inorder,0,sizeof(inorder)-1-1);//法2,知道后序、中序 
674     
675     //二叉查找树创建、查找(递归、非递归)、删除 
676 //    char data[]="43265178";
677 //    createBinarySearchTree(T,data,sizeof(data)/sizeof(char)-1);
678 //    deleteBSTNode(T,'4');
679     
680     
681     
682     searchPrefix(T);      
683     printf("n");
684     searchInfix(T);
685     printf("n");
686     searchPostfix(T);
687     printf("n");
688     
689     return 0;
690 }

tree_build.cpp

[嵌牛提问]

  • 二叉树是在触及数据构造,算法经过中势必会超越的,怎么着从树顶到树底通透到底的访谈树的每贰个节点?
  • 二叉树扩展到n叉树,有哪些差别呢?

那是自家钻了两日才写出的代码,哈哈,努力依旧有回报的,加油。

3、其他

1、二叉树与树、森林的调换

二叉树与常常树的双向转变、与丛林的双向调换。(日常树转为二叉树后根节点度为1,包蕴多棵树的老林转为二叉树后根节点度为2)。二叉树转为树或森林时,该二叉树须是由后面一个转变而来的。

2、树、森林的遍历:

a、二叉树:前序、中序、后序、层次

b、树:前序、后序

c、森林:前序(即按树的前序遍历依次遍历每棵树)、中序(即按树的后序遍历形式挨个遍历每棵树,尼玛叫后序更适用吗)

将树或森林转为二叉树或反向调换后:(不用记,比方就明知道)

二叉树的前序、树的前序、森林的前序遍历系列同样

二叉树的中序、树的后序、森林的中序(尼玛你若叫后序遍历这里就集结了)相像

 

2℃ n叉树的拜望操作

二叉树扩展到n叉树

变的是:树的子树不再独有唯有两棵子树,能够是n颗子树
不改变的是:树的定义依旧依照递归本性

当自己要将时髦变化的子配置充裕到曾经成形到的结构结水果树中,小编须要做的是:

访谈那颗n叉树,找到作者索要插入子配置的职分(必要子配置的父节点),然后插入到该父节点中产生新的配置结水果树

对于n叉树的遍历大家相仿能够使用那3中遍历格局,也会有别的的不二等秘书籍叫做深度优先DFS(Depth First Search),广度优先BFS(Breadth First Search)

  • DFS - 从树顶开端找,找到第生机勃勃棵不为空的子树,从那棵树起来,接着访谈它的率先颗不为空的子树,总是刨根究底,深度优先
  • BFS - 从树顶开头,访谈不为空的子树,访谈完后,在访问下大器晚成层的子树,张开搜索,广度优先

从递归的角度来看目录树,会发觉树构造的面目都以如出一辙的,毫无被它层层叠叠的构造吓到,三个生生不息KO

伪代码如下

InsertConfigIntoConfigResult(root, id) {
  if (root) {
    if (root.id === id) {
       INSERTDATA() // 将数据插入      
    } else {
      root.children.forEach(element => {
        InsertConfigIntoConfigResult(element, id) // 访问子树
      })
    }
  }
}

这会儿分三种状态:

非常二叉树

1、了不起平衡二叉树(独有最终大器晚成层或者不满)

满二叉树(是天时地利平衡二叉树,且各层都满)

完全二叉树(是突出平衡二叉树,且最终豆蔻年华层节点依次从左填到右)

2、正则(正规)二叉树:唯有度为0或2的节点的二叉树 

3、头脑二叉树:将二叉树的空指针域用来存款和储蓄直接四驱、直接后继节点(称为线索)的二叉树,如此遍历就无需用栈了

因此遍历二叉树进行二叉树的线索化,遵照遍历方法的例外分为前序线索二叉树、中序线索二叉树、后序线索二叉树

前序线索二叉树中无法找到有个别节点的一贯四驱节点、后序线索二叉树不能够找到有个别二叉树的第一手后继节点,由此普通用中序线索二叉树。

4、哈夫曼树(最优二叉树):带权路线长度WPL最小的二叉树。

WPL=Σ(叶节点权值×路线长度)= 非根节点的权值和 = 非叶节点的权值和

从没度为1的节点(即哈夫曼树是正则二叉树)、给定权值体系布局的哈夫曼树不唯风流洒脱但WPL相像。

5、二叉查找树(亦称二叉排序树、二叉搜索树)BST:各个节点的左子树的具备节点的值小于该节点值,右子树的享有节点值小于该节点值的二叉树。

搜寻长度:

内部节点、外界节点、平均查找长度ASL(成功时ASL1、退步时ASL2、综合)、内路径长度IPL、外路线长度EPL。EPL=IPL+2n,

某个节点查找成功时比较次数=所在层数=路线+1,故全数节点查找成功的相比较次数=IPL+n;某些值查找失利的可比次数=最终二回比较的叶节点的层=外界节点的外路线长度,故全体节点查找未果的可比次数为EPL

ASL1=(IPL+n)/n,ASL2=EPL/(n+1)

ASL=(IPL+n+EPL卡塔尔国/(n+n+1State of Qatar=(3n+IPLState of Qatar/(2n+1卡塔尔,当IPL最小时平均查找长度最小。

种数:对包括n个数的不改变种类,其BST树有卡特兰数种。

二叉查找树的中序遍历取得升序类别,决断二叉树是不是是二叉查找树能够相中序遍历种类是还是不是升序来决断(递归、非递归均可),当然,还或许有其余越来越好的艺术。

1)二叉查找树制造(递归、非递归):(只给定BST的前序种类就能够构建出BST,依次早先将来插入每种元素就可以;只给定后序种类时临近,只不过是从后一心插入)

图片 53图片 54

 1 void insertBinarySearchTree_nonrecursive(BTREE &T,char item)
 2 {
 3     BTREE p,q;
 4     p=(BTREE)malloc(sizeof(BTNode));
 5     p->data=item;
 6     p->lchild=NULL;
 7     p->rchild=NULL;
 8     if(T==NULL) T=p;
 9     else
10     {
11         q=T;
12         while(1)
13         {
14             if(item < q->data)
15             {
16                 if(q->lchild!=NULL) q=q->lchild;
17                 else
18                 {
19                     q->lchild=p;
20                     break;
21                 }
22             }
23             else
24             {
25                 if(q->rchild!=NULL) q=q->rchild;
26                 else
27                 {
28                     q->rchild=p;
29                     break;
30                 }
31             }
32         }
33     }
34 }
35 void insertBinarySearchTree_recursive(BTREE &T,char item)
36 {
37     if(T==NULL)
38     {
39         T=(BTREE)malloc(sizeof(BTNode));
40         T->data=item;
41         T->lchild=NULL;
42         T->rchild=NULL;    
43     }
44     else if(item< T->data)
45     {
46         insertBinarySearchTree_recursive(T->lchild,item);
47     }
48     else
49     {
50         insertBinarySearchTree_recursive(T->rchild,item);
51     }
52 }
53 void createBinarySearchTree(BTREE &T,char input[],int n)
54 {
55     int i;
56     for(i=0;i<n;i++)
57     {
58 //        insertBinarySearchTree_nonrecursive(T,input[i]);
59         insertBinarySearchTree_recursive(T,input[i]);
60     }
61 }

View Code

2)二叉查找树查找节点(递归、非递归):

图片 55图片 56

 1 BTREE searchBinarySearchTree_nonrecursive(BTREE T,char item)
 2 {
 3     BTREE p=T;
 4     while(p!=NULL)
 5     {
 6         if(p->data==item)
 7             return p;
 8         else if(p->data<item)
 9             p=p->lchild;
10         else
11             p=p->rchild;
12     }
13     return p;
14 }
15 
16 BTREE searchBinarySearchTree_recursive(BTREE T,char item)
17 {
18     if(T==NULL || T->data==item)
19         return T;
20     else if(T->data < item)
21         searchBinarySearchTree_recursive(T->lchild,item);
22     else
23         searchBinarySearchTree_recursive(T->rchild,item);
24 }

View Code

3)二叉查找树删除节点(删除后保卫安全BST的性质,BST形状或者不唯风华正茂):相关:LeetCode450

先找到节点,若找到,则实行删减操作:

a、倘若叶子节点则直接删除;

b、不然,若左孩子空、右孩子非空,则删掉后用右孩子替代之;

c、不然,若左孩子非空、右孩子空,则删掉后用左孩子代替之;

d、不然,值用右子树的渺小节点(即右子树的最左节点)的值代替之,并维护右子树即:对该最左节点开展a或b操作。当然,也能够用左子树的最大节点(即左子树的最右节点)的值庖代之并对该最右节点进行a或c操作。

递归法:

图片 57图片 58

 1 void deleteBSTNode(BTREE &T,char key)
 2 {//删除二叉查找树中的一个节点。也可以借助后序非递归遍历来实现 ,此时栈顶元素存在的话为当前节点的父节点 
 3     if(T==NULL)return;
 4     else if(key<T->data)deleteBSTNode(T->lchild,key);
 5     else if(key>T->data)deleteBSTNode(T->rchild,key);
 6     else
 7     {
 8         if(T->lchild==NULL)
 9         {
10             BTREE tmp=T;
11             T=T->rchild;
12             free(tmp); 
13         } 
14         else if(T->rchild==NULL)
15         {
16             BTREE tmp=T;
17             T=T->lchild;
18             free(tmp) ;
19         } 
20         else
21         {
22             //找右子树的最小节点(最左边)的值替换被删节点的值
23             BTREE p=T->rchild;
24             while(p->lchild!=NULL)
25             {
26                 p=p->lchild;
27             }
28             T->data=p->data;
29             deleteBSTNode(T->rchild,p->data);
30             
31             //也可以找左子树最右的值
32 //            BTREE p=T->lchild;
33 //            while(p->rchild!=NULL)
34 //            {
35 //                p=p->rchild;
36 //            }
37 //            T->data=p->data;
38 //            deleteBSTNode(T->lchild,p->data);
39         }
40     }
41 }

View Code

非递归法:(用后序非递归遍历,比较费心)

4)验证是不是是二叉查找树:二叉查找树的中序遍历拿到升序连串,决断二叉树是还是不是是二叉查找树能够相中序遍历体系是还是不是升序来决断(递归、非递归均可),当然,还会有其余更加好的措施,查看相关--LeetCode98。

图片 59图片 60

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {//通过中序遍历。是BST 等价于 中序遍历序列是升序
11     public boolean isValidBST(TreeNode root) {
12         inOrder(root);
13         return isValid;
14     }
15     private TreeNode lastVisited=null;
16     private boolean isValid=true;
17     private void inOrder(TreeNode root)
18     {//中序遍历,如果遇到上次访问节点值比当前根节点大,则invalid并结束
19         if(root!=null)
20         {
21             inOrder(root.left);
22             
23             if(lastVisited!=null)
24             {
25                 if(lastVisited.val>=root.val)
26                 {
27                     isValid=false;
28                 }
29             }
30             lastVisited=root;
31             
32             inOrder(root.right);
33         }
34     }
35 }
36 
37 public class Solution {
38     public boolean isValidBST(TreeNode root) {
39         return isBST(root, Long.MIN_VALUE, Long.MAX_VALUE); 
40     }
41     
42     private boolean isBST(TreeNode root, long min, long max) {//通过前序遍历
43         
44         if(root == null) {
45             return true;
46         }
47         
48         // check the node's restriction
49         if(!(root.val > min && root.val < max)) {
50             return false;
51         }
52         
53         // check left
54         boolean l = isBST(root.left, min, root.val);
55         boolean r = isBST(root.right, root.val, max);
56         
57         return (l == true && r == true);
58     }
59 }

View Code

最优二叉查找树:给定一个不改变系列{xi},i∈[1,n],再给定查找每种体系值的概率bi以至查找值不设有时落入区间(xi, xi+1),i∈[0,n]的概率ai,所有的ai、bi总的数量为1。如何营造二叉搜索树使平均查找路线最短?——动态规划(与求矩阵连乘的足足乘法次数很像)

二叉查找树的平衡:普通的二叉查找树即便平均时间复杂度为O(lgn卡塔尔,但最坏情况下衰退为线性链表当时时间复杂度为O(nState of Qatar,由此实际使用中不实用。平常思量平衡性,如:

5.1、平衡二叉树(亦称平衡二叉查找树AVL树):种种节点的左右子树深度最多差1的二叉查找树

在乎,平衡二叉树最初是为了精雕细琢二叉排序树的性质而思索平衡性进而提议来的——即AVL树(当然,其平衡性未有优良平衡二叉树必要那么严,否则维护资金太高),所以貌似提及平衡二叉树指的是平衡的二叉排序树

渺小平衡二叉树:节点数起码时的平衡二叉树,那时候各类分支节点的左右子树深度都恰恰相差1。设高为h的微小平衡二叉树的节点总量为F(h卡塔尔(قطر‎,则F(h卡塔尔国=左子树节点总的数量+右子树节点总量+1,即F(hState of Qatar=F(h-1卡塔尔国+F(h-2卡塔尔国+1,F(1卡塔尔=1、F(2卡塔尔=2。

5.2、红黑树:是另意气风发种考虑了平衡性了的二叉查找树。(可参照: 红黑树原理和算法)

性质:

1、各个节点为革命或浅珍珠红;

2、根节点为雪青;

3、叶节点为青黑(此叶节点指为空NULL的叶节点);

4、藤黄节点的子节点一定是紫藤色;

5、叁个节点到它每一种同层子孙节点的门道上玳瑁红节点数相仿(此条保证了从未一条路线会比别的渠道长2倍,故红黑树是周旋平衡的BST)。

含蓄n个节点的红黑树高度最多为 2*ceil( log2(n+1卡塔尔(قطر‎State of Qatar,即高为h的红黑树其节点数至稀有2h/2-1个,由此最坏时间复杂度为O(lgn卡塔尔。

复杂度:插入、删除、查找的平分和最坏时间复杂度为O(lgnState of Qatar,效能高。插入、删除节点恐怕会损坏上述特性,因而须要开展左旋或右旋转操作以维护性质。由于红黑树平衡性供给未有平衡二叉树那么高,因此插入或删除节点的掩护代价比继任者低。

利用:重要用来积存有序数据,如Java中的TreeMap、TreeSet,C++中STL中的map、set,Linux中的内部存款和储蓄器管理等就用了红黑树达成。

5.3、B、B+树:它们不是二叉树查找树,但由二叉查找树扩张而来,是多叉的检索树,且扩大了部分有益平衡性的约束。

 

[嵌牛正文]

将不平衡的成分的左枝的最右节点变为当前节点,

存储

1、顺序存款和储蓄:数组。(适用于完全二叉树的囤积,日常二叉树能够经过填充设想节点当成完全二叉树来存款和储蓄。劣点是荒疏空间)

2、链式存款和储蓄:

二叉链表(左孩子、右孩子):n个节点的二叉树有n+1个空指针域(空指针域即2n0+n1=n2+1+n0+n1=n+1)。线索二叉树通过应用空指针域指向直接四驱、后继节点来幸免遍历时使用酒馆,如中序线索二叉树。

三叉链表(父节点、左孩子、右孩子)

[嵌牛鼻子]

BFS,DFS,二叉树,N叉树

施行结果:

存款和储蓄构造

多种链表:定长链节点个数(二叉树等)、不定长链节点个数

三重链表:每种节点八个指针域(第多个儿女节点、双亲节点、第二个小伙子节点)

处理了有着节点 的左偏和右偏使整个二叉树平衡,那就是平衡二叉树的为主思索

基本概念

男女节点、双亲节点、子孙节点、祖先节点、兄弟节点

节点的度、树的度、节点的层系、树的深度或称中度。(档次、深度从1起)

叶子节点、分支节点、内部节点。(度为0的节点、度非0的节点,非根分支节点)

本文由澳门网络娱乐游戏平台发布于编程,转载请注明出处:python 平衡二叉树实今世码示例

相关阅读