关于二叉树的概念，想必大家基本上都已经很清楚了，那么在这里我就不再一一赘述了。那么请看下面这道题：
如果已知某二叉树的前序遍历结果为{1,2,4,7,3,5,6,8}，中序遍历序列为{4,7,2,1,5,3,8,6}，求此重建后的二叉树。
1、实现思路：
      我们都知道前序遍历是先访问根节点，然后是左子树，接着是右子树，因此在前序遍历序列中，第一个节点值就是根结点的值。但是在中序遍历中根节点是处在序列的中间，左子树的节点的值是位于根节点的左边，右子树的节点的值位于根结点值的右边，因此我们可以通过扫描中序遍历的序列来确定根节点的值和它的右子树和左子树。
分析过程如下图所示：



具体的代码实现如下图所示：
#include<iostream>
using
namespace
std;


//结点信息
struct
BinaryTreeNode
{
          
int
_value;
          
BinaryTreeNode* _left;
          
BinaryTreeNode* _right;
};


BinaryTreeNode* RebuiltTree(int
*
preorder,
int*
inorder
,
int
length)
{
          
//判空
          
if(preorder
==
NULL
||
inorder
==
NULL
||
length
<= 0)
          {
                   
return
NULL
;
    }


          
return
_RebuiltTree(preorder
,
preorder
+
length
- 1,
inorder
,
inorder
+
length
- 1);
          
}


//重建二叉树--->传入前序遍历序列的头指针与尾指，中序遍历序列的头指针与尾指针针
BinaryTreeNode* _RebuiltTree(int
*
startpreorder,
int*
endpreorder
,int*
startinorder,int
*
endinorder)
{
          
int
rootvalue =
startpreorder
[0];//前序遍历序列的第一个值为重建后二叉树的根节点的值
          
BinaryTreeNode* root =
new
BinaryTreeNode();
//创建一个指针，并为它申请一块空间，并且这个指针有此二叉树每个节点应有的全部内容
          
//将根结点的值赋给root->_value，并且将root->_left 与 root->_right都赋为空
          root->_value = rootvalue;
          root->_left = root->_right =
NULL;


          
//在前序遍历序列中找根节点
          
if
(startpreorder
==
endpreorder)
          {
                   
if
(startinorder
==
endinorder
&& *
startpreorder
== *startinorder)//如果此条件满足，则找到根结点的值
                   {
                             
return
root;
                   }
                   
else
                   {
                             cout<<
"非法输入"
<<endl;
                   }
          }


          
//在中序遍历中找到根结点的值，然后将中序遍历序列划分为两个区间，一个是根节点左边的左子树区间，一个是根节点右边的右子树区间
          
int* _startinorder =
startinorder
;//让_startinorder指向startinorder，以防后面改变startinorder，从而在后面无法确定左子树的区间。
          
          
//在中序遍历序列中查找根结点的值
          
while
(_startinorder <=
endinorder
&& *_startinorder != rootvalue)
          {
                   ++_startinorder;
          }
          
//_startinorder与endinorder相等，并且*_startinorder != rootvalue说明中序遍历序列中没有根节点。
          
if
(_startinorder ==
endinorder
&& *_startinorder != rootvalue)
          {
                   cout <<
"非法输入"
<< endl;
          }
          
//走到这里说明_startinorder指针已经走到根结点的位置
          
int
leftlength = _startinorder -
startinorder
;//求出左子树的长度及结点个数
          
int* leftpreorderEnd =
startpreorder
+ leftlength;
          
if
(leftlength > 0)
          {
              
//构建左子树
                   root->_left = _RebuiltTree(
startpreorder
+ 1, leftpreorderEnd,
startinorder
, _startinorder - 1);
          }
          
if
(leftlength <
endpreorder
-
startpreorder)
          {
              
//构建右子树
                   root->_right = _RebuiltTree(leftpreorderEnd + 1,
endpreorder, _startinorder+1,
endinorder
);
          }
          
return
root;
}
void
Test()
{
          
BinaryTreeNode* ret =
NULL
;
          
int
preorder[] = { 1, 2, 4, 7, 3, 5, 6, 8 };
          
int
inorder[] = { 4, 7, 2, 1, 5, 3, 8, 6 };
          ret = RebuiltTree(preorder, inorder, 8);
          cout <<
"ret="
<< ret << endl;
}

满二叉树，已知其先序序列求后续序列 C++实现
分析
实例分析
实现思路
代码实现
测试结果

分析
       正常来说只是知道一个二叉树的先序遍历是无法确定一颗二叉树的，但是作为一棵满二叉树，树的形态确定了，先序遍历的顺序固定为“根左右”的条件下，二叉树也就得以确定。

       那么在满二叉树的情况下，如何通过先序遍历得到后续遍历呢？让我们先进行下面的分析
实例分析


以上图二叉树作为例子:

    其先序遍历为：abdecfg（根左右）

    后续遍历为： debfgca （左右根）
通常情况下，我们进先序遍历，一定是从根出发，于是这个根便是整个序列中的“头部”：

               a |  bdecfg

去掉“头部”以后，剩下的部分由左右两个子树构成。因为先序是根左右的次序，观察&思索也可以发现——剩下的部分从中间等分刚好可以得到这颗树的左右两个子树部分：

               bde  |  cfg

化分出来的两个子序列也是子树的先序遍历：

               b |  de               c |  fg
于是就形成一个“套娃”。然后首先会做出的反应就是递归。
实现思路
       既然已经确定使用递归了，现在的关键就是：怎么递归、在哪里使用递归、递归做什么以及递归结束的条件（也就是寻找最小的子问题）。

       通过上述实例的分析，整个满二叉树先序遍历的序列可以的流程为：根->左子树->右子树；每颗子树的流程也是：根->左子树->右子树。现在要获取的是后续遍历，在不耗费额外空间时间重构整棵树的条件下，把这个过程改为：左子树->右子树->根。

       在先序序列中如何体现 左子树->右子树->根 的流程呢？不妨在草稿纸上用刚刚的实例看看：



先序拆解：

               a |    bde | cfg

               a |    （b| de） | （c| fg）
后序（左右根）：（（de） b）->（（fg）c）-> a
可以发现实际上就是把序列分成：头部、左部、右部，然后按照：左部——右部——头部 的顺序输出。头部只有一个字符，左右部本身视作一个新的先序序列再次划分三部。

       划到后面，左右部只剩下三个字符组成的先序，此时最后一次化分，可以得到只有头部的先序序列，只需要输出头部就可以了，然后逐步回代，因为子树的头输出过了，组成大树以后，其左右子树也就已经完成的输出，也只需要输出头部即可。
于是就有：

化分函数(树先序序列 ){

    if（序列数量大于一个）{

        化分函数(左子树先序序列)；

        化分函数(右子树先序序列)；

    }

    输出根（头部序列）；

}
代码实现
#include <iostream>
//#include<cmath>
using namespace std;

#define GET_ARRAY_LEN(array, len) { len = sizeof(array)/sizeof(array[0]);}
//获取数组长度宏


/**
* @a           目标数组
* @begin  子树开始的下标
* @end    子树结束的下标
**/
void preToPost(char a[],
	int begin,
	int end
	) {
	char root = a[begin];   //暂存根，子树遍历完后最后输出
	
	if (begin + 1 <= end) {
		begin = begin + 1;//左端+1（把根节点独立出来）
		
		//此时左子树从begin+1位开始，到(begin+end)/2)结束
		preToPost(a, begin,((begin+end)/2)); //左子树

        //此时右子树从((begin+end)/2) + 1)位开始，到end结束
		preToPost(a, (((begin+end)/2) + 1), end); //右子树
	}
	cout << root;  //输出根

}

void main() {
	//测试数据
	//char a[] = { 'a','b','d','h','i','e','j','k','c','f','l','m','g','n','o' };  
	char a[] = { 'a','b','d','e','c','f','g' };
	int length;  //字符数组长度
	
	/*
	这里可以添加一个判断序列数量是否满足满二叉树的判定
	if (  ) {
	   cout<<"输出数据不满足满二叉树条件"<<endl;
		return ;// 判断是否满足满二叉树的条件
	}*/
	
	GET_ARRAY_LEN(a, length); //调用写好的宏得到数组长度
	
	//测试数据输出
	cout<<"先序遍历为："<<endl;
	for (int i = 0;i < length;i++)
		cout << a[i];
	cout << endl;
	
	cout<<"后序遍历为："<<endl;
	preToPost(a, 0, length - 1);
	cout << endl << endl << endl << endl;
}

测试结果


运行环境：Windows10 家庭版、Visual Studio 2019

树、森林和二叉树的转换

树转换为二叉树:

 树的先根序列对应二叉树的先序遍历

 树的后根序列对应二叉树的中序遍历

 

从树的二叉链表表示的定义可知，任何一棵和数对应的二叉树，其右子树必为空。

都遵循这样一个规律：左孩子右兄弟（也就是说，在二叉树转换为树或者是森林的时候，左孩子是左孩子，右孩子是左孩子的兄弟）

下面请IGN



森林转换为二叉树

（1）把每棵树转换为二叉树。

（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。

4-1-1 && 4-1-4 二叉树及其遍历 树的遍历 && 还原二叉树 (25 分)
4-1-4 二叉树及其遍历 还原二叉树 (25 分)
给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。
输入格式:
输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。
输出格式:
输出为一个整数，即该二叉树的高度。
输入样例:
9
ABDFGHIEC
FDHGIBEAC

输出样例:
5

本题主要分成两个部分：根据先序和中序遍历序列建树、求高度
（中 + 先/后 -> 后/先）（即必须包含中序遍历序列）
根据先序和中序遍历序列建树：先序序列第一个是根节点，根据根节点在中序序列的位置可以确定左子树和右子树的元素，然后开始递归建左右子树
求高度：递归实现
//中 + 先 -> 后
#include<iostream>
using namespace std;
#define MAXN 55

struct Tree
{
	char ch;
	struct Tree* left;
	struct Tree* right;
};
typedef struct Tree* PTree;

PTree BuildTree(char* pre, char* in, int n)
{
	if (n == 0)return NULL;

	int m;//找到头结点在中序序列中的位置
	for (m = 0; in[m] != pre[0]; m++);

	PTree T = new Tree;
	T->ch = pre[0];

	T->left = BuildTree(pre + 1, in, m);//建立左子树
	T->right = BuildTree(pre + m + 1, in + m + 1, n - m - 1);//建立右子树
	return T;
}

int GetHeight(PTree T)
{
	if (T == NULL)
		return 0;
	int m = GetHeight(T->left);
	int n = GetHeight(T->right);
	return max(m + 1, n + 1);
}

int main()
{
	int n; cin >> n;
	char preorder[MAXN], inorder[MAXN];
	for (int i = 0; i < n; i++)
		cin >> preorder[i];//先序
	for (int i = 0; i < n; i++)
		cin >> inorder[i];//中序

	PTree T = BuildTree(preorder, inorder, n);
	cout<< GetHeight(T);

	return 0;
}

思考：如何根据后序遍历序列和中序遍历序列建树？
4-1-1 二叉树及其遍历 树的遍历 (25 分)
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：
4 1 6 3 5 7 2

#include<iostream>
#include<queue>
using namespace std;
#define MAXN 35
typedef struct Tree* pTree;
struct Tree
{
	int data;
	pTree left;
	pTree right;
};

pTree BuildTree(int* post, int *in, int n)
{
	if (n == 0)return NULL;

	int m;
	for (m = n - 1; in[m] != post[n - 1]; m--);

	pTree T = new Tree;
	T->data = post[n - 1];

	T->left = BuildTree(post, in, m);
	T->right = BuildTree(post + m, in + m + 1, n - m - 1);
	return T;
}

void Levelorder(pTree T)
{
	int flag = 0;
	queue<pTree>q;
	q.push(T);
	while (!q.empty())
	{
		pTree temp = q.front();
		q.pop();
		if (flag++)cout << " ";
		cout << temp->data;
		if (temp->left)
			q.push(temp->left);
		if (temp->right)
			q.push(temp->right);
	}
}

int main()
{
	int postorder[MAXN], inorder[MAXN];
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> postorder[i];
	for (int i = 0; i < n; i++)
		cin >> inorder[i];

	pTree T = BuildTree(postorder, inorder, n);
	Levelorder(T);

	return 0;
}