C递归算法与栈的分析,非完全二叉树遍历分析-ShinePans
对于递归,这里面的分析最好当然是用图形的方式来分析了.这里来总结一下
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
= 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
|
}
|