一、 已知先序和中序遍历序列，求后序遍历序列
先序序列：ABDECF
中序序列：DBEAFC
步骤：
- 由先序序列确定根结点A
- 由中序序列确定根结点A的左子树（DBE）和右子树（FC）
- 对于根结点A的左子树，有：
先序序列：BDE
中序序列：DBE
对于根结点A的右子树，有：
先序序列：CF
中序序列：FC
分别对左右子树递归进行1-3步，直至左右子树为空
构建二叉树
最后得后序序列：DEBFCA
二、 已知中序和后序遍历序列，求先序遍历序列
中序序列：DBEAFC
后序序列：DEBFCA
步骤：
- 由后序序列确定根结点A
- 由中序序列确定根结点A的左子树（DBE）和右子树（FC）
- 对于根结点A的左子树，有：
中序序列：DBE
后序序列：DEB
对于根结点A的右子树，有：
中序序列：FC
后序序列：FC
分别对左右子树递归进行1-3步，直至左右子树为空
构建二叉树
最后得先序序列：ABDECF
三、 已知先序和后序遍历序列
这种情况无法唯一确定一颗二叉树，例如：
先序序列：ABC
后序序列：CBA
中序序列：CBA、BCA、ACB、ABC
四、代码实现
#include <iostream>
using namespace std;
/* 二叉树结点 */
struct Node
{
char data;
Node* lchild;
Node* rchild;
Node():lchild(nullptr),rchild(nullptr){};
};
/* 递归创建二叉树 */
Node* rCreate(char data, Node* lchild, Node* rchild)
{
Node* root = new Node;
root->data = data;
root->lchild = lchild;
root->rchild = rchild;
return root;
}
/* 由先序和中序序列，建立二叉树
* 参数：先序序列、中序序列、序列长度
* 返回值：当前树的根结点
*/
Node* CreateA(char* preSeq, char* inSeq, int len)
{
int rootIndex = 0;
Node* root = nullptr;
if(len == 0) return nullptr;
else if(len == 1)
{
root = new Node;
root->data = *preSeq;
return root;
}
while(*preSeq != inSeq[++rootIndex]);
//递归创建左子树
Node* lchild = CreateA(preSeq+1, inSeq, rootIndex);
//递归创建右子树
Node* rchild = CreateA(preSeq+rootIndex+1, inSeq+rootIndex+1, len-rootIndex-1);
return rCreate(*preSeq, lchild, rchild);
}
/* 由中序和后序序列，建立二叉树
* 参数：中序序列、后序序列、序列长度
* 返回值：当前树的根结点
*/
Node* CreateB(char* inSeq, char* postSeq, int len)
{
int rootIndex = 0;
Node* root = nullptr;
if(len == 0) return nullptr;
else if(len == 1)
{
root = new Node;
root->data = *inSeq;
return root;
}
while(postSeq[len-1] != inSeq[++rootIndex]);
//递归创建左子树
Node* lchild = CreateB(inSeq, postSeq, rootIndex);
//递归创建右子树
Node* rchild = CreateB(inSeq+rootIndex+1, postSeq+rootIndex, len-rootIndex-1);
return rCreate(postSeq[len-1], lchild, rchild);
}
/* 先序遍历二叉树 */
void preOrderTraverse(Node* root)
{
if(root)
{
cout << root->data;
preOrderTraverse(root->lchild);
preOrderTraverse(root->rchild);
}
}
/* 后序遍历二叉树 */
void postOrderTraverse(Node* root)
{
if(root)
{
postOrderTraverse(root->lchild);
postOrderTraverse(root->rchild);
cout << root->data;
}
}
/* 后序遍历删除二叉树 */
void DeleteTree(Node* root)
{
if(root)
{
DeleteTree(root->lchild);
DeleteTree(root->rchild);
delete root;
}
}
int main()
{
char preSeq[] = "ABDECF";
char inSeq[] = "DBEAFC";
char postSeq[] = "DEBFCA";
Node* btreeA = nullptr;
Node* btreeB = nullptr;
//由先序和中序序列构建二叉树
btreeA = CreateA(preSeq, inSeq, 6);
//输出后序序列
postOrderTraverse(btreeA);
cout << endl;
//由中序和后序序列构建二叉树
btreeB = CreateB(inSeq, postSeq, 6);
//输出先序序列
preOrderTraverse(btreeB);
//删除二叉树
DeleteTree(btreeA);
DeleteTree(btreeB);
return 0;
}
作者：Wray Zheng
原文：http://www.codebelief.com/article/2016/12/binary-tree-traversal-sequence/
