数据结构35：二叉树前序遍历、中序遍历和后序遍历

本文转载自 ciyeer 查看原文 2018/05/16 3 数据/ 二叉树/ 遍历/ 结构/ 数据结构

递归算法底层的实现使用的是栈存储结构，所以可以直接使用栈写出相应的非递归算法。

先序遍历的非递归算法

从树的根结点出发，遍历左孩子的同时，先将每个结点的右孩子压栈。当遇到结点没有左孩子的时候，取栈顶的右孩子。重复以上过程。

实现代码函数：

// 先序遍历非递归算法
void PreOrderTraverse(BiTree Tree)
{
　　BiTNode *a[20];　　// 定义一个顺序栈
　　BiTNode *p;　　    // 临时指针
　　push(a, Tree);　　 // 根结点进栈
　　while (top != -1) 
　　{
　　　　p=getTop(a);　　// 取栈顶元素
　　　　pop();　　// 弹栈
　　　　while (p) 
　　　　{
　　　　　　displayElem(p);　　// 调用结点的操作函数
　　　　　　// 如果该结点有右孩子，右孩子进栈
　　　　　　if (p->rchild) 
　　　　　　{
　　　　　　　　push(a, p->rchild);
　　　　　　}
　　　　　　p = p->lchild;　　// 一直指向根结点最后一个左孩子
　　　　}
　　}
}

中序遍历的非递归算法

从根结点开始，遍历左孩子同时压栈，当遍历结束，说明当前遍历的结点没有左孩子，从栈中取出来调用操作函数，然后访问该结点的右孩子，继续以上重复性的操作。

实现代码函数：

//中序遍历非递归算法
void InOrderTraverse1(BiTree Tree)
{
　　BiTNode *a[20];　　 // 定义一个顺序栈
　　BiTNode *p;　　　　 // 临时指针
　　push(a, Tree);　　　//根结点进栈
　　while (top != -1) 
　　{
　　　　// top != -1说明栈内不为空，程序继续运行
　　　　while ((p = getTop(a)) &&p)
　　　　{
　　　　　　// 取栈顶元素，且不能为NULL
　　　　　　push(a, p->lchild);　　//将该结点的左孩子进栈，如果没有左孩子，NULL进栈
　　　　}
　　　　pop();　　//跳出循环，栈顶元素肯定为NULL，将NULL弹栈
　　　　if (top != -1) 
　　　　{
　　　　　　p = getTop(a);　　//取栈顶元素
　　　　　　pop();　　//栈顶元素弹栈
　　　　　　displayElem(p);
　　　　　　push(a, p->rchild);　　//将p指向的结点的右孩子进栈
　　　　}
　　}
}

补：中序遍历非递归算法的另一种实现

中序遍历过程中，只需将每个结点的左子树压栈即可，右子树不需要压栈。当结点的左子树遍历完成后，只需要以栈顶结点的右孩子为根结点，继续循环遍历即可。

实现代码：

void InOrderTraverse2(BiTree Tree)
{
　　BiTNode *a[20];　　// 定义一个顺序栈
　　BiTNode *p;　　// 临时指针
　　p = Tree;
　　// 当p为NULL或者栈为空时，表明树遍历完成
　　while (p || top != -1) 
　　{
　　　　// 如果p不为NULL，将其压栈并遍历其左子树
　　　　if (p) 
　　　　{
　　　　　　push(a, p);
　　　　　　p = p->lchild;
　　　　}
　　　　else 　　// 如果p=NULL,表明左子树遍历完成，需要遍历上一层节点的右子树
　　　　{
　　　　　　p = getTop(a);
　　　　　　pop();
　　　　　　displayElem(p);
　　　　　　p = p->rchild;
　　　　}
　　}
}

后序遍历的非递归算法

后序遍历是在遍历完当前结点的左右孩子之后，才调用操作函数，所以需要在操作结点进栈时，为每个结点配备一个标志位。当遍历该结点的左孩子时，设置当前结点的标志位为 0，进栈；当要遍历该结点的右孩子时，设置当前结点的标志位为 1，进栈。

这样，当遍历完成，该结点弹栈时，查看该结点的标志位的值：如果是 0，表示该结点的右孩子还没有遍历；反之如果是 1，说明该结点的左右孩子都遍历完成，可以调用操作函数。

实现代码函数：

// 后序遍历函数
void PostOrderTraverse(BiTree Tree)
{
　　SNode a[20];　　// 定义一个顺序栈
　　BiTNode *p;　　 // 临时指针
　　int tag;
　　SNode sdata;
　　p = Tree;
　　while (p || top != -1) 
　　{
　　　　while (p) 
　　　　{
　　　　　　// 为该结点入栈做准备
　　　　　　sdata.p = p;
　　　　　　sdata.tag = 0;　　// 由于遍历是左孩子，设置标志位为0
　　　　　　postpush(a, sdata);　　// 压栈
　　　　　　p = p->lchild;　　// 以该结点为根结点，遍历左孩子
　　　　}
　　　　sdata = a[top];　　  // 取栈顶元素
　　　　pop();　　　　　　　　 // 栈顶元素弹栈
　　　　p = sdata.p;
　　　　tag = sdata.tag;
　　　　// 如果tag == 0，说明该结点还没有遍历它的右孩子
　　　　if (tag == 0) 
　　　　{
　　　　　　sdata.p = p;
　　　　　　sdata.tag = 1;
　　　　　　postpush(a, sdata);　　//更改该结点的标志位，重新压栈
　　　　　　p = p->rchild;　　//以该结点的右孩子为根结点，重复循环
　　　　}
　　　　else    // 如果取出来的栈顶元素tag == 1，说明此节点左右子树都遍历完了，可以调用操作函数了
　　　　{
　　　　　　displayElem(p);
　　　　　　p = NULL;
　　　　}
　　}
}

非递归算法的完整实现

#include <stdio.h>
#include <string.h>
#define TElemType int

int top = -1;　　//top变量时刻表示栈顶元素所在位置
//构造结点的结构体
typedef struct BiTNode
{
　　TElemType data;　　//数据域
　　struct BiTNode *lchild, *rchild;　　//左右孩子指针
}BiTNode, *BiTree;

//初始化树的函数
void CreateBiTree(BiTree *T)
{
　　*T = (BiTNode*)malloc(sizeof(BiTNode));
　　(*T)->data = 1;
　　(*T)->lchild = (BiTNode*)malloc(sizeof(BiTNode));
　　(*T)->rchild = (BiTNode*)malloc(sizeof(BiTNode));
　　(*T)->lchild->data = 2;
　　(*T)->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
　　(*T)->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
　　(*T)->lchild->rchild->data = 5;
　　(*T)->lchild->rchild->lchild = NULL;
　　(*T)->lchild->rchild->rchild = NULL;
　　(*T)->rchild->data = 3;
　　(*T)->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
　　(*T)->rchild->lchild->data = 6;
　　(*T)->rchild->lchild->lchild = NULL;
　　(*T)->rchild->lchild->rchild = NULL;
　　(*T)->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
　　(*T)->rchild->rchild->data = 7;
　　(*T)->rchild->rchild->lchild = NULL;
　　(*T)->rchild->rchild->rchild = NULL;
　　(*T)->lchild->lchild->data = 4;
　　(*T)->lchild->lchild->lchild = NULL;
　　(*T)->lchild->lchild->rchild = NULL;
}

// 前序和中序遍历使用的进栈函数
void push(BiTNode **a, BiTNode *elem)
{
　　a[++top] = elem;
}

// 弹栈函数
void pop()
{
　　if (top==-1) 
　　{
　　　　return ;
　　}
　　top--;
}

// 模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode *elem)
{
　　printf("%d ", elem->data);
}

// 拿到栈顶元素
BiTNode *getTop(BiTNode **a)
{
　　return a[top];
}

// 先序遍历非递归算法
void PreOrderTraverse(BiTree Tree)
{
　　BiTNode *a[20];　　// 定义一个顺序栈
　　BiTNode *p;　　　　 // 临时指针
　　push(a, Tree);　　 // 根结点进栈
　　while (top != -1) 
　　{
　　　　p = getTop(a);　// 取栈顶元素
　　　　pop();　　　　　　// 弹栈
　　　　while (p) 
　　　　{
　　　　　　displayElem(p);　　// 调用结点的操作函数
　　　　　　// 如果该结点有右孩子，右孩子进栈
　　　　　　if (p->rchild) 
　　　　　　{
　　　　　　　　push(a ,p->rchild);
　　　　　　}
　　　　　　p = p->lchild;　　// 一直指向根结点最后一个左孩子
　　　　}
　　}
}

// 中序遍历非递归算法
void InOrderTraverse1(BiTree Tree)
{
　　BiTNode* a[20];　　// 定义一个顺序栈
　　BiTNode * p;　　　　// 临时指针
　　push(a, Tree);　　 // 根结点进栈
　　while (top != -1) 
　　{
　　　　// top != -1 说明栈内不为空，程序继续运行
　　　　while ((p = getTop(a)) && p)
　　　　{
　　　　　　//取栈顶元素，且不能为NULL
　　　　　　push(a, p->lchild);　　//将该结点的左孩子进栈，如果没有左孩子，NULL进栈
　　　　}
　　　　pop();　　//跳出循环，栈顶元素肯定为NULL，将NULL弹栈
　　　　if (top != -1) 
　　　　{
　　　　　　p = getTop(a);　　//取栈顶元素
　　　　　　pop();　　//栈顶元素弹栈
　　　　　　displayElem(p);
　　　　　　push(a, p->rchild);　　//将p指向的结点的右孩子进栈
　　　　}
　　}
}

//中序遍历实现的另一种方法
void InOrderTraverse2(BiTree Tree)
{
　　BiTNode *a[20];　　//定义一个顺序栈
　　BiTNode *p;　　　　 //临时指针
　　p = Tree;
　　//当p为NULL或者栈为空时，表明树遍历完成
　　while (p || top != -1) 
　　{
　　　　//如果p不为NULL，将其压栈并遍历其左子树
　　　　if (p) 
　　　　{
　　　　　　push(a, p);
　　　　　　p = p->lchild;
　　　　}
　　　　else  // 如果p == NULL,表明左子树遍历完成，需要遍历上一层节点的右子树
　　　　{
　　　　　　p = getTop(a);
　　　　　　pop();
　　　　　　displayElem(p);
　　　　　　p = p->rchild;
　　　　}
　　}
}

//后序遍历非递归算法
typedef struct SNode
{
　　BiTree p;
　　int tag;
}SNode;

//后序遍历使用的进栈函数
void postpush(SNode *a, SNode sdata)
{
　　a[++top] = sdata;
}

//后序遍历函数
void PostOrderTraverse(BiTree Tree)
{
　　SNode a[20];　　//定义一个顺序栈
　　BiTNode *p;　　 //临时指针
　　int tag;
　　SNode sdata;
　　p = Tree;
　　while (p || top != -1) 
　　{
　　　　while (p) 
　　　　{
　　　　　　//为该结点入栈做准备
　　　　　　sdata.p = p;
　　　　　　sdata.tag = 0;　　　　　//由于遍历是左孩子，设置标志位为0
　　　　　　postpush(a, sdata);　　//压栈
　　　　　　p = p->lchild;　　//以该结点为根结点，遍历左孩子
　　　　}
　　　　sdata = a[top];　　//取栈顶元素
　　　　pop();　　//栈顶元素弹栈
　　　　p = sdata.p;
　　　　tag = sdata.tag;
　　　　//如果tag == 0，说明该结点还没有遍历它的右孩子
　　　　if (tag == 0) 
　　　　{
　　　　　　sdata.p = p;
　　　　　　sdata.tag = 1;
　　　　　　postpush(a, sdata);　　//更改该结点的标志位，重新压栈
　　　　　　p = p->rchild;　　　　  //以该结点的右孩子为根结点，重复循环
　　　　}
　　　　else　　// 如果取出来的栈顶元素tag==1，说明此结点左右子树都遍历完了，可以调用操作函数了
　　　　{
　　　　　　displayElem(p);
　　　　　　p = NULL;
　　　　}
　　}
}

int main()
{
　　BiTree Tree;
　　CreateBiTree(&Tree);
　　printf("前序遍历: \n");
　　PreOrderTraverse(Tree);
　　printf("\n中序遍历算法1: \n");
　　InOrderTraverse1(Tree);
　　printf("\n中序遍历算法2: \n");
　　InOrderTraverse2(Tree);
　　printf("\n后序遍历: \n");
　　PostOrderTraverse(Tree);
}

运行结果
前序遍历:
1 2 4 5 3 6 7
中序遍历算法1:
4 2 5 1 6 3 7
中序遍历算法2:
4 2 5 1 6 3 7
后序遍历:
4 5 2 6 7 3 1

智能推荐

注意！

本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。

猜您在找

数据结构34：二叉树前序遍历、中序遍历和后序遍历数据结构——树（4）：二叉树前序，中序，后序遍历互求数据结构与算法（二）：二叉树前序，中序，后序遍历详解【数据结构与算法】二叉树前序、中序、后序遍历间关系二叉树前序、中序、后序遍历

智能推荐