二叉树的构建
1.构建方法
二叉树的前序、中序和后序序列中的任何一个都不能唯一确定一棵二叉树，二叉树的构建主要有两大方法。
第一种是中序序列和前、中，层次序列任一组合唯一确定一颗二叉树； 第二种是根据二叉树对应的扩充二叉树的先序或者后序序列来确定。注意扩充二叉树的中序遍历序列是不能唯一确定二叉树的结构。反例证明如下：
上图中扩展二叉树的中序遍历序列为：#B#D#A#C#，那么也可以对应为下面的扩展二叉树：
2.前序+中序序列构建
构建过程： （1）前序序列中的第一个数字为根结点，构造根结点； （2）找到根结点在中序序列中的位置，中序中根结点左右两边分别为左子树和右子树的中序序列，前序序列根节点后面分别为左子树和右子树的前序序列； （3）递归处理左右子树，返回根结点，完成构造。
构建过程示例： 以如下二叉树为例：
其前序遍历序列为：{1,2,4,7,3,5,6,8}，中序遍历序列为：{4,7,2,1,5,3,8,6}。
由于在中序遍历中，有三个左子树结点的值，因此在前序序列中，根节点后面的 3 个数字就是 3 个左子树结点的值，在后面的所有数字都是右子树结点的值。这样子我们就在前序序列和中序序列中找到了左右子树对应的子序列，然后再递归处理即可。
前序序列：
中序序列：
理解上面的过程，即可根据前序序列和中序序列构建二叉树。二叉树的存储可以用顺序存储（数组）或链式存储，本文采用的就是链式存储。Talk is cheap. Show me the code.
//二叉树节点结构体
struct BinaryTreeNode
{
int m_key;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
/*****************************************************
@brief: 根据前序序列和中序序列构建二叉树
@param: preOrder:前序序列; midOrder:中序序列; len:结点数
@ret: 二叉树根结点
*****************************************************/
BinaryTreeNode* constructPreMid(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;
}3.后序+中序序列构建
这种方法和前面先序+中序序列构建的过程很像，唯一的区别就是对后序序列处理时，所找出的根结点和左右子树的位置不同而已。
还是以上面的二叉树为例，给出构建过程。
后序遍历序列为：{7,4,2,5,8,6,3,1}，中序遍历序列为：{4,7,2,1,5,3,8,6}。
4.层次+中序序列构建
5.扩充二叉树前序序列构建
这种方法可以参考：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;
}注意： 扩展二叉树先根序列使用引用的方式，保证每次每次生成新节点时指针后移一位。
6.扩充二叉树后序序列构建
本人尚未研究，请知道的网友留言指教。
7.小结
本文内容还不够完善，如先序+中序构建二叉树可以用非递归的方法来实现，等等，鄙人后续会继续完善的。