二叉树构建，先序，中序，后序遍历（以及非递归实现），广度优先遍历
二叉树构建，先序，中序，后序遍历（以及非递归实现），广度优先遍历
二叉树是一类简单而又重要的树形结构，在数据的排序、查找和遍历方面有着广泛的应用。由于其清晰的结构，简单的逻辑，广泛的应用和大量的指针操作，在面试过程屡见不鲜，快被面试官玩坏了。相关的问题在百行代码内就可解决，特别适合手写代码，因此我们要充分做好准备，迎接面试时关于二叉树的相关问题，尤其是手写代码。
1. 二叉树简介
二叉树的相关概念，如，树高度，节点层数，节点度数，路径，叶节点，分支节点，根节点，父节点，左节点，右节点，兄弟节点，祖先节点，子孙节点，左子树，右子树等基本概念，不再赘述，可参见百度百科：二叉树。
1.1 二叉树的五种基本形态
二叉树可以定义为节点的有限集合，或者为空集，或者为根节点及其左右子树的节点集合。因此二叉树具有五种基本形态。 （1）空二叉树
（2）只有一个根节点
（3）有根节点和非空左子树
（4）有根节点和非空右子树
（5）有根节点并且左右子树均为非空
1.2二叉树的分类
二叉树有两大类，一是普通二叉树，二是特殊二叉树。
普通二叉树不用多说，除了特殊二叉树，都是普通二叉树。除了富人，都是屌丝。那就重点说一下特殊二叉树。
（1）完全二叉树 若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
一维数组可以作为完全二叉树的存储结构，堆排序使用的数据结构就是完全二叉树。下图所示就是完全二叉树
（2）满二叉树 国际标准定义是除了叶结点外每一个结点都有左右子结点的二叉树。如下图所示：
注意：这里的定义与国内某些教材的定义不同，国内的定义是：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。很显然，按照这个定义，上面的图示二叉树就不是满二叉树。
（3）扩充二叉树 扩充二叉树是对已有二叉树的扩充，扩充后的二叉树的节点都变为度数为2的分支节点。也就是说，如果原节点的度数为2，则不变，度数为1，则增加一个分支，度数为0的叶子节点则增加两个分支。
如下如所示，一棵普通二叉树及其扩充二叉树：
（4）平衡二叉树 是一棵空树或它的任意节点的左右两个子树的高度差的绝对值不超过1。
2.二叉树的构建
二叉树的前序、中序和后序序列中的任何一个都不能唯一确定一棵二叉树，我所知道的二叉树的构建主要有两大种方法。
第一种是根据前序+中序或者后序+中序来唯一确定二叉树的结构，第二种是根据二叉树对应的扩充二叉树的先序或者后序序列来确定。
网上有很多blog和资料都没有将上面的方法列举出来，有个文档资料里说根据扩充二叉树的任意一个遍历序列就能唯一确定这棵二叉树。这个说法是错误的，这份文档见here。
举一个反例即可证明根据扩充二叉树的中序遍历序列是不能唯一确定二叉树的结构，以文档中的描述为例：
上图中扩展二叉树的中序遍历序列为：#B#D#A#C#，那么也可以对应为下面的扩展二叉树：
2.1前序+中序序列构建二叉树（递归实现）
构建过程： （1）前序遍历序列中的第一个数字为根节点，构造根节点； （2）找到根节点在中序遍历序列中的位置，中序中根节点左右两边分别为左子树和有子树，前序序列根节点后面为左子树+右子树； （3）递归处理处理左右子树，返回根节点，完成构造。
构建过程示例： 以如下二叉树为例：
其前序遍历序列为：{1,2,4,7,3,5,6,8}，中序遍历序列为：{4,7,2,1,5,3,8,6}。
由于在中序遍历中，有三个左子树节点的值，因此在前序遍历的序列中，根节点后面的3个数字就是3个左子树节点的值，再后面的所有数字都是右子树节点的值。这样子我们就在前序序列和中序序列中找到了左右子书对应的子序列，然后再递归处理即可。如下图所示：
前序序列：
中序序列：
理解上面的过程，即可根据前序序列和中序序列写出如下构建二叉树代码。二叉树的存储可以先用线性存储，如数组，或者链式存储，本文采用的就是链式存储。实现废话不多说，上代码：
//二叉树节点结构体
struct BinaryTreeNode{
int m_key;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
/****************************************
func:根据前序序列和中序序列构建二叉树
para:preOrder:前序序列;midOrder:中序序列;len:节点数
****************************************/
BinaryTreeNode* construct(int* preOrder,int* midOrder,int len){
if(preOrder==NULL||midOrder==NULL||len<=0)
return NULL;
//先根遍历（前序遍历）的第一个值就是根节点的键值
int rootKey=preOrder[0];
BinaryTreeNode* root=new BinaryTreeNode;
root->m_key=rootKey;
root->m_pLeft=root->m_pRight=NULL;
if(len==1 && *preOrder==*midOrder)//只有一个节点
return root;
//在中根遍历（中序遍历）中找到根节点的值
int* rootMidOrder=midOrder;
int leftLen=0; //左子树节点数
while(*rootMidOrder!=rootKey&&rootMidOrder<=(midOrder+len-1)){
++rootMidOrder;
++leftLen;
}
if(*rootMidOrder!=rootKey)//在中根序列未找到根节点,输入错误
return NULL;
if(leftLen>0){ //构建左子树
root->m_pLeft=construct(preOrder+1,midOrder,leftLen);
}
if(len-leftLen-1>0){ //构建右子树
root->m_pRight=construct(preOrder+leftLen+1,rootMidOrder+1,len-leftLen-1);
}
return root;
}2.2后序+中序序列构建二叉树
这种方法和前面先序+中序序列构建的过程很像，唯一的区别就是对后序序列处理时，所找出的根节点和左右子树的位置不同而已。其具体实现，我就不给出了，网友可自行实现。
2.3扩充二叉树前序序列构建二叉树
这种方法可以参考：here。
假设扩展二叉树的前序遍历序列由键盘输入，root为指向根结点的指针，二叉链表的建立过程是：首先输入根结点，若输入的是一个“#”字符，则表明该二叉树为空树，即root=NULL；否则输入的字符应该赋给root->data，之后依次递归建立它的左子树和右子树。建立二叉链表的递归算法如下：
//先序创建二叉树
void CreatBTree(BTNode *&root)
{
char nValue = 0;
cin >> nValue;
if ('#' == nValue)
return;
else{
root = new BTNode();
root->m_value = nValue;
CreatBTree(root->m_left);
CreatBTree(root->m_right);
}
} 下面是本人根据扩展二叉树的先根序列完成二叉树的构建。与上面不同的是先根序列由参数给出，而非标准输入读取。扩充节点使用-1表示。
/**************************************************
//func:根据扩展二叉树先根序列构建二叉树。
//para:extendedBTPreorder:扩展二叉树先根序列。
//ret: 二叉树根节点。
**************************************************/
BinaryTreeNode* createBTree(int*& extendedBTPreorder){
if (-1==extendedBTPreorder[0]){
++extendedBTPreorder;
return NULL;
}
BinaryTreeNode* root = new BinaryTreeNode;
root->m_key =extendedBTPreorder[0];
++extendedBTPreorder;
root->m_pLeft=createBTree(extendedBTPreorder);
root->m_pRight=createBTree(extendedBTPreorder);
return root;
}注意：扩展二叉树先根序列使用引用的方式，保证每次每次生成新节点时指针后移一位。
2.4扩充二叉树后序序列构建二叉树
本人尚未研究，请知道的网友留言指教。
3.二叉树的遍历
二叉树的遍历分为两类，一类是深度优先周游，另一类是广度优先周游。
3.1深度优先周游
二叉树的深度优先周游有三种方式，就是我们常说的先根次序遍历（简称先序遍历）、中根次序遍历（中序遍历）和后跟次序遍历（后序遍历）。
因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。下面一一讲解具体的递归和非递归实现。
3.1.1先根次序遍历
先根次序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。
（1）递归实现
//先根递归遍历
void preOrderRecursion(BinaryTreeNode* root){
if(root==NULL)
return;
cout<<" "<<root->m_key; //visit
preOrderRecursion(root->m_pLeft);
preOrderRecursion(root->m_pRight);
}（2）非递归实现 根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问完左子树时，再访问它的右子树。因此其处理过程如下：
给定二叉树的根节点R： (a)并将根节点R入栈；
(b)判断栈是否为空，若不为空，取栈顶元素cur访问并出栈。然后先将cur的右子节点入栈，再将cur的左子节点入栈；
(c)重复(b)直到栈为空，则遍历结束。
//先根非递归遍历，需要使用栈
void preOrderStack(BinaryTreeNode* root){
if(root==NULL)
return;
stack<BinaryTreeNode*> stack;
stack.push(root);
BinaryTreeNode* cur=NULL;
while(!stack.empty()){
cur=stack.top();
cout<<" "<<cur->m_key; //visit
stack.pop();
if(cur->m_pRight!=NULL)
stack.push(cur->m_pRight);
if(cur->m_pLeft!=NULL)
stack.push(cur->m_pLeft);
}
}3.1.2中根次序遍历
中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。 （1）递归实现
//中根递归遍历
void midOrderRecursion(BinaryTreeNode* root){
if(root==NULL)
return;
midOrderRecursion(root->m_pLeft);
cout<<" "<<root->m_key; //visit
midOrderRecursion(root->m_pRight);
}（2）非递归实现 根据中序遍历的顺序，对于任一结点，先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：
对于给定的二叉树根节点R， (a)若其左孩子不为空，循环将R以及R左子树中的所有节点的左孩子入栈； (b)取栈顶元素cur，访问cur并将cur出栈。然后对cur的右子节点进行步骤（a）那样的处理； (c)重复（a）和（b）的操作，直到cur为空切栈为空。
//中根非递归遍历，需要使用栈
void midOrderStack(BinaryTreeNode* root){
if(root==NULL)
return;
stack<BinaryTreeNode*> stack;
BinaryTreeNode* cur=root;
while(!stack.empty()||cur!=NULL){
while(cur){
stack.push(cur);
cur=cur->m_pLeft;
}
cur=stack.top();
cout<<" "<<cur->m_key; //visit
stack.pop();
cur=cur->m_pRight;
}
}3.1.3后根次序遍历
后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。 （1）递归实现
//后根递归遍历
void postOrderRecursion(BinaryTreeNode* root){
if(root==NULL)
return;
postOrderRecursion(root->m_pLeft);
postOrderRecursion(root->m_pRight);
cout<<" "<<root->m_key; //visit
}（2）非递归实现 后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子要在右孩子前被访问，才能访问根节点。这就为流程的控制带来了难题。下面介绍两种思路。
第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。
//非递归后序遍历，版本1
void postOrderStack1(BinaryTreeNode* root){
if(root==NULL)
return;
stack<pair<BinaryTreeNode*,bool> > s;
pair<BinaryTreeNode*,bool> cur=make_pair(root,true);
while(cur.first!=NULL||!s.empty())
{
while(cur.first!=NULL) { //沿左子树一直往下搜索，直至出现没有左子树的结点
s.push(cur);
cur=make_pair(cur.first->m_pLeft,true);
}
if(!s.empty()){
if(s.top().second==true){ //表示是第一次出现在栈顶
s.top().second=false;
cur=make_pair(s.top().first->m_pRight,true); //将当前节点的右节点入栈
}
else{ //第二次出现在栈顶
cout<<s.top().first->m_key<<" ";
s.pop();
}
}
}
}第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点R， （a）先将R入栈。如果P不存在左孩子和右孩子，则可以直接访问它并出栈； （b）如果R存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点并出栈； （c）若非上述两种情况，则将R的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在父结点前面被访问。
//非递归后根遍历,版本2
void postOrderStack2(BinaryTreeNode* root)
{
if(root==NULL)
return;
stack<BinaryTreeNode*> s;
BinaryTreeNode *cur; //当前结点
BinaryTreeNode *pre=NULL; //前一次访问的结点
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->m_pLeft==NULL&&cur->m_pRight==NULL)||(pre!=NULL&&(pre==cur->m_pLeft||pre==cur->m_pRight))) //在判断当前节点时，左孩子和右孩子都在根结点前已经被访问
{
cout<<cur->m_key<<" "; //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop();
pre=cur;
}
else{
if(cur->m_pRight!=NULL)
s.push(cur->m_pRight);
if(cur->m_pLeft!=NULL)
s.push(cur->m_pLeft);
}
}
}3.2广度优先周游
广度优先周游的方式是按层次从上到下，从左到右的逐层访问，不难想到，可以利用一个队列来实现。基本思想是： （1）首先把二叉树的根节点送入队列； （2）队首的节点出队列并访问之，然后把它的右子节点和左子节点分别入队列； （3）重复上面两步操作，直至队空。
//广度优先遍历二叉树，使用队列实现
void breadthFirstOrder(BinaryTreeNode* root){
if(root==NULL) return;
queue<BinaryTreeNode*> queue;
queue.push(root);
while(!queue.empty()){
BinaryTreeNode* cur=queue.front();
cout<<" "<<cur->m_key;//visit
queue.pop();
if(cur->m_pLeft!=NULL)
queue.push(cur->m_pLeft);
if(cur->m_pRight!=NULL)
queue.push(cur->m_pRight);
}
} 4.验证结果
以上面建立的二叉树为例，进行各种遍历，验证代码如下：
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main(){
//先根序列
int preOrder[8]={1,2,4,7,3,5,6,8};
//中根序列
int midOrder[8]={4,7,2,1,5,3,8,6};
//建树
BinaryTreeNode* root=construct(preOrder,midOrder,8);
cout<<"---preOrder---"<<endl;
cout<<"recursion version: ";
preOrderRecursion(root);
cout<<endl<<"stack version: ";
preOrderStack(root);
cout<<endl<<endl<<"---midOrder---"<<endl;
cout<<"recursion version: ";
midOrderRecursion(root);
cout<<endl<<"stack version1: ";
postOrderStack1(root);
cout<<endl<<"stack version2: ";
postOrderStack2(root);
cout<<endl<<endl<<"---postOrder---"<<endl;
cout<<"recursion version: ";
postOrderRecursion(root);
cout<<endl<<"stack version: ";
postOrderStack1(root);
cout<<endl<<endl<<"---Breadth First Order---"<<endl;
breadthFirstOrder(root);
}实验结果如下图：
实验结果markdown编辑器不知道出啥问题了，上传不了照片，报Object reference not set to an instance of an object.的错误。所以截图就换成如下文字描述：
---preOrder---
recursion version: 1 2 4 7 3 5 6 8
stack version: 1 2 4 7 3 5 6 8
---midOrder---
recursion version: 4 7 2 1 5 3 8 6
stack version: 4 7 2 1 5 3 8 6
---postOrder---
recursion version: 7 4 2 5 8 6 3 1
stack version1: 7 4 2 5 8 6 3 1
stack version2: 7 4 2 5 8 6 3 1
---Breadth First Order---
1 2 3 4 5 6 7 85.小结
本文内容还不够完善，如以扩充二叉树来构建二叉树还未给出其实现原理与代码，再如先序+中序构建二叉树可以用非递归的方法来实现，等等，鄙人后续会继续完善的。
参考文献
[1]二叉树的非递归遍历. [2]百度百科.二叉树.
腾讯云开发者
