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

时间：2023-03-09 14:54:05
C递归算法与栈的分析,非全然二叉树遍历分析---ShinePans

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



1.首先对于栈的理解:

先进后出,后进先出

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

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

非全然二叉树的存储:

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

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

如图所看到的:

标准结构:

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

树:

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

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

遍历方式:

DLR,

LDR,

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

DRL,

RDL,

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

多层递归方式:

举例:

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

以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
= 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 }

相关文章