二叉树的前中后序遍历,递归和非递归方式
数据结构系列:二叉树遍历
1. 思想介绍:
1.1递归介绍
用递归方式遍历二叉树。以递归方式对二叉树进行遍历时,算法的思路为:对整棵二叉树的遍历不断转化为对每个结点同样形式的遍历,从而实现对整棵二叉树的遍历。其思路简述如下:
(1)前序遍历
①: 访问根结点。
②: 对根结点的左子树进行前序遍历。
③: 对根结点的右子树进行前序遍历。
(2) 中序遍历
①: 对根结点的左子树进行中序遍历。
②: 访问根结点。
③: 对根结点的右子树进行中序遍历。
(3)后序遍历
①: 对根结点的左子树进行后序遍历。
②: 对根结点的右子树进行后序遍历。
③: 访问根结点。
1.2 非递归介绍
用递归方式遍历二叉树。以非递归方式对二叉树进行遍历的算法需要借助一个栈来存放访问过的结点。其思路简述如下:
(1)前序遍历
从整棵二叉树的根结点开始,对于任意结点VV,访问结点VV并将结点VV入栈,并判断结点VV的左子结点LL是否为空。若LL不为空,则将LL置为当前结点VV;若LL为空,则取出栈顶结点,并将栈顶结点的右子结点置为当前结点VV。重复上述操作,直到当前结点VV为空结点且栈为空,遍历结束。
(2)中序遍历
从整棵二叉树的根结点开始,对于任一结点VV,判断其左子结点LL是否为空。若LL不为空,则将VV入栈并将L置为当前结点VV;若LL为空,则取出栈顶结点并访问该栈顶结点,然后将其右子结点置为当前结点VV。重复上述操作,直到当前结点V为空结点且栈为空,遍历结束。
(3)后序遍历
首先将整棵二叉树的根结点入栈。取栈顶结点VV,若VV不存在左子结点和右子结点,或VV存在左子结点或右子结点,但其左子结点和右子结点都被访问过了,则访问结点VV,并将VV从栈中弹出。若非上述两种情况,则将VV的右子结点和左子结点依次入栈。重复上述操作,直到栈为空,遍历结束。
2. 算法流程图:
用递归方式对二叉树进行遍历的算法流程较为简单,流程图略。
**用非递归方式对二叉树进行先序遍历的算法流程图如图1所示。 **
图1: 用非递归方式对二叉树进行先序遍历的算法流程图
用非递归方式对二叉树进行中序遍历的算法流程图如图2所示。
图2: 用非递归方式对二叉树进行中序遍历的算法流程图
**用非递归方式对二叉树进行后序遍历的算法流程图如图3所示。 **
图3: 用非递归方式对二叉树进行后序遍历的算法流程图
第二步:代码演示
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Stack_increment 20
#define Stack_Size 100
typedef struct Tree
{
char data;
struct Tree *lchild;
struct Tree *rchild;
}Node;
Node* createBinaryTree()
{
Node *root;
char ch;
scanf("%c", &ch);
if (ch == '#')
{
root = NULL;
}
else
{
root = (Node *)malloc(sizeof(Node));
root -> data = ch;
root -> lchild = createBinaryTree();
root -> rchild = createBinaryTree();
}
return root;
}
typedef struct
{
int top;
Node* arr[Stack_Size];
}Stacktree;
void InitStack(Stacktree *S)
{
S->top = 0;
}
void Push(Stacktree* S, Node* x)
{
int top1 = S -> top;
if (x -> data == '#')
{
return;
}
else
{
S -> arr[top1++] = x;
S -> top++;
}
}
int Pop(Stacktree *S)
{
int top = S -> top;
if (S->top == 0)
{
return 0;
}
else
{
--(S->top);
return 1;
}
}
Node* GetTop(Stacktree *S)
{
int top1 = S -> top;
Node*p;
p = S -> arr[top1--];
return p;
}
Node* GetTop1(Stacktree *S)
{
int top1 = S -> top;
Node*p;
top1--;
p = S -> arr[top1];
return p;
}
int IsEmpty(Stacktree *S)
{
return(S->top == 0 ? 1 : 0);
}
void preorderRecursive(Node *p )
{
if (p != NULL)
{
printf("%c ", p -> data);
preorderRecursive(p -> lchild);
preorderRecursive(p -> rchild);
}
}
void inorderRecursive(Node *p )
{
if (p != NULL)
{
inorderRecursive(p -> lchild);
printf("%c ", p -> data);
inorderRecursive(p -> rchild);
}
}
void postorderRecursive(Node *p )
{
if (p != NULL)
{
postorderRecursive(p -> lchild);
postorderRecursive(p -> rchild);
printf("%c ", p -> data);
}
}
void preordernotRecursive(Node *p)
{
if(p)
{
Stacktree stree ;
InitStack(&stree);
Node *root = p;
while(root != NULL || !IsEmpty(&stree))
{
while(root != NULL)
{
printf("%c ", root->data);
Push(&stree, root);
root = root -> lchild;
}
if(!IsEmpty(&stree))
{
Pop(&stree);
root = GetTop(&stree);
root = root -> rchild;
}
}
}
}
void inordernotRecursive(Node *p)
{
if(p)
{
Stacktree stree;
InitStack(&stree);
Node *root = p;
while(root != NULL || !IsEmpty(&stree))
{
while(root != NULL)
{
Push(&stree, root);
root = root -> lchild;
}
if(!IsEmpty(&stree))
{
Pop(&stree);
root = GetTop(&stree);
printf("%c ", root -> data);
root = root -> rchild;
}
}
}
}
void postordernotRecursive(Node *p)
{
Stacktree stree;
InitStack(&stree);
Node *root;
Node *pre = NULL;
Push(&stree, p);
while (!IsEmpty(&stree))
{
root = GetTop1(&stree);
if ((root -> lchild == NULL && root -> rchild == NULL) || (pre != NULL && (pre == root -> lchild || pre == root -> rchild)))
{
printf("%c ", root -> data);
Pop(&stree);
pre = root;
}
else
{
if (root -> rchild != NULL)
{
Push(&stree, root -> rchild);
}
if (root -> lchild != NULL)
{
Push(&stree, root -> lchild);
}
}
}
}
void main()
{
printf("请输入二叉树,'#'为空\n");
Node *root = createBinaryTree();
printf("\n递归先序遍历:\n");
preorderRecursive(root);
printf("\n递归中序遍历:\n");
inorderRecursive(root);
printf("\n递归后序遍历:\n");
postorderRecursive(root);
printf("\n非递归先序遍历\n");
preordernotRecursive(root);
printf("\n非递归中序遍历\n");
inordernotRecursive(root);
printf("\n非递归后序遍历\n");
postordernotRecursive(root);
getchar();
getchar();
}
三:程序运行展示
所用树形结构如为下图
转载博客地址:https://blog.****.net/asd20172016/article/details/80786186