【数据结构周周练】011 非递归算法实现二叉树的遍历

柔光的暖阳◎ 2021-06-11 15:13 486阅读 0赞

# 一、前言 #

从第七篇周周练博客开始就一直在围绕二叉树的创建和遍历在进行分享，因为这是很重要的一部分内容，二叉树怎么用顺序表创建，怎么用链式结构来创建，怎么用递归算法创建，不用递归算法怎么创建。顺序二叉树的遍历，二叉链表的递归遍历等等，这些都是最基础也最重要的东西之一。

本次要给大家分享的是非递归遍历方法，先序和中序的非递归算法比较方便，后续遍历比较麻烦，**可以通过孩子结点是否访问，来决定是否访问左右子树，从而防止重复访问**。原理同非递归创建二叉树类似，在这里不重复分享代码，有兴趣的，大家可以自己尝试。**代码真的只有自己写了，算法自己认真琢磨了，才能慢慢学明白，知识都是一点一点，一次一次磨练出来的**。

# 二、题目 #

将下图用二叉树存入，并通过三种遍历方式对该树进行遍历。其中圆角矩形内为结点数据，旁边数字为结点编号，编号为0的结点为根节点，箭头指向的结点为箭尾的孩子结点。要求遍历每个结点时能够查询当前结点的数据、编号、双亲结点以及孩子结点的编号，如果结点是根节点或者叶子结点，请说明。

![70][]

#  三、代码 #

## 1、非递归先序遍历算法 ##

void PreOrderBiTree(BiTree BT) {
    	LinkStack S = (LinkStack)malloc(sizeof(LNode));
    	if (!S)
    	{
    		cout << "空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	S->next = NULL;
    	BiTree  p = BT;
    	while (p || S)
    	{
    		if (p)
    		{
    			Push(S, p);
    			VisitBiTree(p);
    			p = p->lChild;
    		}
    		else
    		{
    			Pop(S, p);
    			p = p->rChild;
    		}
    	}
    }

## 2、非递归中序遍历算法 ##

void InOrderBiTree(BiTree BT) {
    	LinkStack S = (LinkStack)malloc(sizeof(LNode));
    	if (!S)
    	{
    		cout << "空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	S->next = NULL;
    	BiTree  p = BT;
    	while (p || S)
    	{
    		if (p)
    		{
    			Push(S, p);
    			p = p->lChild;
    		}
    		else
    		{
    			Pop(S, p);
    			VisitBiTree(p);
    			p = p->rChild;
    		}
    	}
    }

# 四、实现效果 #

![70 1][]

![70 2][]

[70]: /images/20210516/d04ce3cd8ec84cd28e1343540a3601df.png
[70 1]: /images/20210516/0ed0a1dbdfa045128e6abc00b45c9a77.png
[70 2]: /images/20210516/bcfd30687cea467981b9874d6e768151.png