二叉树的遍历：先序中序后序遍历的递归与非递归实现及层序遍历

长沙7喜 2018-04-22

展开全文

作者：llhthinker

个人博客：http://www.cnblogs.com/llhthinker/

往期回顾：

Stanford机器学习笔记-1.线性回归

Stanford机器学习笔记-2.Logistic Regression

Stanford机器学习笔记-3.Bayesian statistics and Regularization

Stanford机器学习笔记-4. 神经网络Neural Networks (part one)

Stanford机器学习笔记-5.神经网络Neural Networks (part two)

Stanford机器学习笔记-6. 学习模型的评估和选择

Stanford机器学习笔记-7. Machine Learning System Design

Stanford机器学习笔记-8. 支持向量机(SVMs)概述

Stanford机器学习笔记-9. 聚类(Clustering)

Stanford机器学习笔记-10. 降维(Dimensionality Reduction)

对于一种数据结构而言，遍历是常见操作。二叉树是一种基本的数据结构，是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下：

typedef struct TreeNode *PtrToNode;
typedef struct TreeNode *BinTree;

struct TreeNode
{
int Data; //为简单起见，不妨假设树节点的元素为int型
BinTree Left;
BinTree Right;
};

二叉树的遍历主要有先序遍历，中序遍历，后序遍历，层序遍历四种方式，下面一一介绍。

1. 先序遍历

在先序遍历中，对节点的访问工作是在它的左右儿子被访问之前进行的。换言之，先序遍历访问节点的顺序是根节点-左儿子-右儿子。由于树可以通过递归来定义，所以树的常见操作用递归实现常常是方便清晰的。递归实现的代码如下：

void PreOrderTraversal(BinTree BT)
{
if( BT )
{
printf(“%d\n”, BT->Data); //对节点做些访问比如打印
PreOrderTraversal(BT->Left); //访问左儿子
PreOrderTraversal(BT->Right); //访问右儿子
}
}

由递归代码可以看出，该递归为尾递归（尾递归即递归形式在函数末尾或者说在函数即将返回前）。尾递归的递归调用需要用栈存储调用的信息，当数据规模较大时容易越出栈空间。虽然现在大部分的编译器能够自动去除尾递归，但是即使如此，我们不妨自己去除。非递归先序遍历算法基本思路：使用堆栈

　　a. 遇到一个节点，访问它，然后把它压栈，并去遍历它的左子树；

　　b. 当左子树遍历结束后，从栈顶弹出该节点并将其指向右儿子，继续a步骤；

　　c. 当所有节点访问完即最后访问的树节点为空且栈空时，停止。

　　实现代码如下：

void PreOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MAX_SIZE); //创建并初始化堆栈S
while(T || !IsEmpty(S))
{
while(T) //一直向左并将沿途节点访问（打印）后压入堆栈
{
printf('%d\n', T->Data);
Push(S, T);
T = T->Left;
}
if (!IsEmpty(S))
{
T = Pop(S); //节点弹出堆栈
T = T->Right; //转向右子树
}
}
}

2. 中序遍历

中序遍历的遍历路径与先序遍历完全一样。其实现的思路也与先序遍历非常相似。其主要的不同点是访问节点顺序不同：中序遍历是访问完所有左儿子后再访问根节点，最后访问右儿子，即为左儿子-根节点-右儿子。

递归实现的代码如下:

void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf('%d\n', BT->Data);
InOrderTraversal(BT->Right);
}
}

　　非递归辅助栈实现代码如下:

void InOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MaxSize); //创建并初始化堆栈S
while(T || !IsEmpty(S))
　　{
　　while(T) //一直向左并将沿途节点压入堆栈
　　{
　　 Push(S,T);
　　T = T->Left;
　　}
　　if(!IsEmpty(S))
　　{
　　 T = Pop(S); //节点弹出堆栈
　　 printf('%d\n', T->Data); //（访问）打印结点
　　 T = T->Right; //转向右子树
　　}
　　}
}

非递归不用辅助栈实现中序遍历：

试设计一个非递归算法，按中根顺序遍历非线索二叉树，但不得用任何辅助栈。在执行算法期间，允许改变左孩子指针和右孩子指针的值。

算法：右线索化+回溯

若当前树的根节点p有左孩子且未被线索化：将其左孩子的最右结点（可为左孩子本身）指向p，即右线索化，然后p = p->lChild；

若p有左孩子但已被线索化，说明该p是回溯上来的，即左孩子已经被访问了，则释放线索化的指针；

若p无左孩子，打印p，向上回溯(即p = p->rChild)。

代码如下：

/*
输入：ABDH##I##E##CF#J##G##
*/
#include

typedef struct BTNode* Position;
typedef Position BTree;
typedef char ElementType;
struct BTNode {
ElementType data;
Position lChild, rChild;
};

BTree CreateBTree(void);
void Inorder(BTree bt);

int main()
{
BTree bt = CreateBTree();
Inorder(bt);
return 0;
}

void Inorder(BTree bt)
{
Position p = bt;
while (p)
{
Position pLeft = p->lChild;
if (pLeft)
{
while (pLeft->rChild && pLeft->rChild != p) //找到以p为根结点的树的最右孩子
pLeft = pLeft->rChild;
if (pLeft->rChild == NULL) //线索化
{
pLeft->rChild = p;
p = p->lChild;
continue;
}
else //线索化后已被访问
{
pLeft->rChild = NULL; //释放指向根节点(祖先)的指针
}
}
printf('%c ', p->data); //打印
p = p->rChild; //向上回溯或者转向右子树
}
printf('\n');
}

BTree CreateBTree() //按照先序序列建立二叉树
{
BTree bt = NULL;
char ch;
scanf('%c', &ch);
if (ch != '#') //'#'代表空节点
{
bt = new BTNode;
bt->data = ch;
bt->lChild = CreateBTree();
bt->rChild = CreateBTree();
}
return bt;
}

运行结果：

参考博客：http://m.blog.csdn.net/blog/Raito__/40618257

3. 后序遍历

后序遍历与中序遍历，先序遍历的路径也完全一样。主要的不同点是后序遍历访问节点的顺序是先访问左儿子和右儿子，最后访问节点，即左儿子-右儿子-根节点。

递归实现思路与中序遍历和先序遍历相似，代码如下:

void PostOrderTraversal(BinTree BT)
{
if (BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf('%d\n', BT->Data);
}
}

后序遍历的非递归实现

思路一：

对于一个节点而言，要实现访问顺序为左儿子-右儿子-根节点，可以利用后进先出的栈，在节点不为空的前提下，依次将根节点，右儿子，左儿子压栈。故我们需要按照根节点-右儿子-左儿子的顺序遍历树，而我们已经知道先序遍历的顺序是根节点-左儿子-右儿子，故只需将先序遍历的左右调换并把访问方式打印改为压入另一个栈即可。最后一起打印栈中的元素。代码如下：

void PostOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S1 = CreatStack(MAX_SIZE); //创建并初始化堆栈S1
Stack S2 = CreatStack(MAX_SIZE); //创建并初始化堆栈S2
while(T || !IsEmpty(S1))
{
while(T) //一直向右并将沿途节点访问（压入S2）后压入堆栈S1
{
Push(S2, T);
Push(S1, T);
T = T->Right;
}
if (!IsEmpty(S1))
{
T = Pop(S1); //节点弹出堆栈
T = T->Left; //转向左子树
}
}
while(!IsEmpty(S2)) //访问（打印）S2中元素
{
T = Pop(S2);
printf('%d\n', T->Data);
}
}

思路一的优点是由于利用了先序遍历的思想，代码较简洁，思路较清晰。缺点是需要用一个栈来存储树的所有节点，空间占用较大。　　

思路二：

要访问一个节点的条件上一个访问的节点是右儿子。我们可以增加一个变量Prev来判断当前节点Curr的上一个节点与它的关系来执行相应的操作。
若Prev为空(Curr节点是根节点)或者Prev是Curr的父节点，将Curr节点的左孩子和右孩子分别压入栈；
若Prev是Curr的左儿子，则将Curr的右儿子压入栈；
否则Prev是Curr的右儿子，访问Curr;

代码如下:

void PostOrderTraversal(BinTree BT)
{
if(BT == NULL)
return ;
Stack S = CreatStack(MAX_SIZE);
BinTree Prev = NULL , Curr = NULL; //初始化
s.push(BT);
while(!IsEmpty(S))
{
Curr = Top(S); //将栈顶元素赋给Curr
if(Prev == NULL || Prev->Left == Curr || Prev->Right == Curr) //若Prev为NULL或是Curr的父节点
{
if(Curr->Left != NULL)
Push(S, Curr->Left);
else if(Curr->Right != NULL)
Push(S, Curr->Right);
}
else if(Curr->Left == Prev) //若Prev是Curr的左儿子
{
if(Curr->Right != NULL)
Push(S, Curr->Right);
}
else
{
printf('%d\n', Curr->Data); //访问当前节点
Pop(S); //访问后弹出
}
Prev = Curr; //处理完当前节点后将Curr节点变为Prev节点
}
}

4. 层序遍历

二叉树遍历的核心问题是二维结构的线性化。我们通过节点访问其左右儿子时，存在的问题是访问左儿子后，右儿子怎么访问。因此我们需要一个存储结构保存暂时不访问的节点。前面三种遍历方式的非递归实现，我们是通过堆栈来保存。事实上也可以通过队列来保存。

队列实现的基本思路：遍历从根节点开始，首先将根节点入队，然后执行循环：节点出队，访问（访问）根节点，将左儿子入队，将右儿子入队，直到队列为空停止。

这种遍历方式的结果是将二叉树从上到下，从左至右一层一层的遍历，即层序遍历，代码实现如下:

void LevelOrderTraversal(BinTree BT)
{
BinTree T;
Queue Q; //声明一个队列
if (BT == NULL)
return; //如果树为空，直接返回
Q = CreatQueue(MAX_SIZE); //创建并初始化队列
AddQ(Q, BT); //将根节点入队
while (!IsEmpty(Q))
{
T = DeleteQ(Q); 　　　　　　　　　　//节点出队
printf('%d\n', T->Data); 　　　　 //访问出队的节点
if (T->Left) AddQ(Q, T->Left); //若左儿子不为空，将其入队
if (T->Right) AddQ(Q, T->Right) //若右儿子不为空，将其入队
}
}