首页 > 代码库 > C递归算法与栈的分析,非全然二叉树遍历分析---ShinePans

C递归算法与栈的分析,非全然二叉树遍历分析---ShinePans

2024-09-22 19:19:29   214人阅读

             对于递归,这里面的分析最好当然是用图形的方式来分析了.这里来总结一下


1.首先对于栈的理解:

先进后出,后进先出


  技术分享先进后出


2.在进行非全然二叉树的存储之后,我们要做的是对其进行遍历或者索引,查找某个孩子,或某个左孩子或右孩子的双亲,不然存了是徒劳的.

非全然二叉树的存储:

我觉得最好的存储方式是动态链表,静态链表仅仅有在某些很特殊的情况下才行得通的选择,比方说已知这个二叉树就是这样,不会再改变

而对于动态链表,我觉得最好的方式是建立5个指针,一个数据域,这五个指针各自是:*lchild(左孩子),*rchild(右孩子) ,* parent(双亲) ,*node(指向结构体)  ,*p(暂时指针)

如图所看到的:

               标准结构:

                                                        技术分享

               树:

                                                          技术分享           

               结构:技术分享

              遍历方式:

                                 DLR,

                                 LDR,

                                 LRD.  这三种为正序遍历 (先左子)

                                 DRL,

                                 RDL,

                                 RLD. 这三种为逆序遍历  (先右子)   

               多层递归方式:

                                 举例:

                                                                   

                                                 技术分享


                                          以DLR遍历方式来举例:    

                            递归第一层:     訪问1,  左孩子是否有 ?

有,进入一下曾...       A  ..右孩子推断被搁置

                                    递归等二层:    訪问2, 此时 2被视为 根, 左孩子是否有 ?

有,进入下一层....   B ..右孩子推断被搁置

                                               递归第三层:   訪问4 ,此时 4被视为根 ,左孩子 是否有?

有,进入下一层 ... C  .右孩子推断被搁置

                                                         递归第四层:   訪问8 ,此时 8被视为 根 ,左孩子是否有? 没有  D.. 右孩子推断: 没,回到 C 返回第三层 被搁置的推断

                                               回到第三层:  4 右孩子是否有?

 有.. 进入下一层 

                                                          递归到新第四层:  9被视为根 ,是否有 左孩子?

没有  E: 是否有右孩子 ?

没有  回到第三层

                                              回到第三层:  语句运行完成, 回到第二层..... .

                                  递归第二层:  2 的右子树 : 有 为 5, 进入新的 第三层 递归

                                              递归到新的第三层: 5 被视为根 , 5的左子树? 没 , 5的右 子树?

没 回到第二层 ..

                                  回到第二层:  第二层语句所有运行完成 回到第一层

                        递归第一层:  1 的右孩子? 有 进入新的一层: 

                                  新的第二层:  1的右孩子3 被视为 根, 是否有左孩子? 没 是否有右孩子 ?

没 回到第一层

                       回到第一层: 所有完成

                      递归运行完成



04 #include <stdlib.h>
05 #include <malloc.h>
06 #include <stdio.h>
07 typedef struct node
08 {
09     char data;
10     struct node *lchild;
11     struct node *rchild;
12 }*BiTree;
13  
14 void creatBT(BiTree &T)//建立二叉树函数
15 {
16     char ch;
17     scanf("%c",&ch);
18     if(ch==‘.‘)
19     {
20         T=NULL;//   .空子树；
21     }
22     else
23     {
24         T=(node *)malloc(sizeof(node));//分配空间
25         if(!T)exit(0);
26         T->data = http://www.mamicode.com/ch;//T赋值
27         creatBT(T->lchild);//左子树赋值
28         creatBT(T->rchild);//右子树赋值
29     }
30 }
31  
32 void pre_order(node *T)//前序遍历
33 {
34     if(T)
35     {
36         printf("%c ",T->data);
37         pre_order(T->lchild);
38         pre_order(T->rchild);
39     }
40  
41 }
42  
43 void mid_order(node *T)//中序遍历
44 {
45     if(T)
46     {
47         mid_order(T->lchild);
48         printf("%c ",T->data);
49         mid_order(T->rchild);
50     }
51 }
52  
53 void behind_order(node *T)//后序遍历
54 {
55     if(T)
56     {
57         behind_order(T->lchild);
58         behind_order(T->rchild);
59         printf("%c ",T->data);
60     }
61 }
62  
63 int main()
64 {
65     node *T;
66     printf("请按先序序列输入一串字符,当子树为空时,输入.\n");
67     creatBT(T);//建树
68     printf("建树成功,T指向二叉树的根!\n");
69  
70     printf("\n前序遍历二叉树的结果:");
71     pre_order(T);
72  
73     printf("\n中序遍历二叉树的结果:");
74     mid_order(T);
75  
76     printf("\n后序遍历二叉树的结果:");
77     behind_order(T);printf("\n");
78      
79      
80     system("pause");
81      
82     return 0;
83 }

C递归算法与栈的分析,非全然二叉树遍历分析---ShinePans


联系
我们