后根遍历:
中根遍历的原理就是,先遍历左子树,然后再遍历右,然后再根
一句话来讲,就是 左 -> 右 -> 根
所以我们按顺序与根遍历/中根遍历类似
所以根遍历的顺序就是
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);
}
}
非递归的方式,思想类似与栈的方式,相比之前的两个,这边多了一个标志位检验,防止数据重复出入栈
例如
A
B C
E F G
这样子类型的,如果不加入判断是否第一次入栈,则E会重复出入栈
展示代码
/*可以输入
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.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》