从零开始学数据结构系列之第三章《二叉树链式结构及实现4》

后根遍历：

​ 中根遍历的原理就是，先遍历左子树，然后再遍历右，然后再根

​ 一句话来讲，就是 左 -> 右 -> 根

所以我们按顺序与根遍历/中根遍历类似

所以根遍历的顺序就是

​ D->E->B->F->G->C->A

递归的方式：

/*LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。*/
void postOrder(TreeNode* T) 
{
   	if(T == NULL)
		return;
	else
	{
		postOrder(T->lchild);
		postOrder(T->rchild);
		printf("%c->",T->data);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

非递归的方式，思想类似与栈的方式,相比之前的两个，这边多了一个标志位检验，防止数据重复出入栈

例如
	A
  B   C
   E  F  G

这样子类型的，如果不加入判断是否第一次入栈，则E会重复出入栈
1
2
3
4
5
6

展示代码

/*可以输入
ABD##E##CF##G##
来进行验证
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define size 20

typedef struct TreeNode 
{
	char data;
	struct TreeNode *lchild;
	struct TreeNode *rchild;
}TreeNode;

typedef struct Node 
{
	TreeNode *data;
	struct Node *next;
}Node;


void createTree(TreeNode** T,char* temp,int* index)
{
	char ch;
	
	ch = temp[*index];
	(*index)++;

	if( ch == '#') *T = NULL;
	else
	{
		 *T =(TreeNode*)malloc(sizeof(TreeNode));
		 (*T)->data = ch;
		createTree(&(*T)->lchild,temp,index);
		createTree(&(*T)->rchild,temp,index);		
	}
}

void preOrder(TreeNode* T) 
{
	if(T==NULL)
		return;
	else
	{
		printf("%c->",T->data);
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}


Node* initQueue() 
{
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = NULL;
	node->next =NULL;
	return node;
}
// 后根遍历
void enQueue(TreeNode* data, Node* list) 
{
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	
	while(list->next)list=list->next;
	node->next = list->next;
	list->next=node;
}


int isEmpty(Node* Q) 
{
	if(Q->next == NULL)
		return 1;
	else
		return 0;
}

Node* deQueue(Node* Q)
{
 if (isEmpty(Q)) 
     return NULL;
 else 
 {
	Node *node = Q->next;
	Q ->next = node->next;
    return node;
 }
}

void levelTraverse(Node* Q, TreeNode* T) 
{
    enQueue(T, Q);
    while (!isEmpty(Q)) 
	{
        Node* node = deQueue(Q);
        printf("%c->", node->data->data);
        if (node->data->lchild) 
		{
            enQueue(node->data->lchild, Q);
        }
        if (node->data->rchild) 
		{
            enQueue(node->data->rchild, Q);
        }
    }
}



int main(int argc, char* argv[]) 
{
	TreeNode *T;
	int i=0;
	char *temp=NULL;
	Node* Q = initQueue();

	temp=(char*)malloc(sizeof(char) * (size+1));
	gets(temp);
	createTree(&T,temp,&i);
	preOrder(T);       
    printf("\n");
    levelTraverse(Q, T);
    printf("\n");

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》