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 }

巴特西

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

最新文章

热门文章