怎么用中序和后续生成二叉树？我只会用前序

1. 怎么用中序和后续生成二叉树？我只会用前序

已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：
1. 根据后序序列的最后一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在后序序列中确定左右子树的后序序列；
4. 由左子树的后序序列和中序序列建立左子树；
5. 由右子树的后序序列和中序序列建立右子树。
例如：已知二叉树的后序序列gdbehfca, 中序序列dgbaechf。
后序：gdbehfca  ->根：a
根据根结点来划分中序序列
中序：dgbaechf  ->  dgb+a+echf
由左右子树的结点集合来划分后序序列->后序：gdb+ehfc+a 
分别对根a的左右子树运用相同的方法分解出根和其左右子树的结点集合。
左子树后序序列gdb  －>根： b
根据根结点来划分左子树中序序列
中序：dgb  -> dg+ b 说明没有右子树
由左右子树的结点集合来划分后序序列->后序：gd+b 
对根b的左子树运用相同的方法分解出根和其左右子树的结点集合。依次递归。
得到的二叉树：
                                    a
                                   /  \
                                 b    c
                               /       /  \
                            d        e    f
                              \            /                          
                               g        h

2. 怎么用中序和后续生成二叉树？我只会用前序

已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：
1.
根据后序序列的最后一个元素建立根结点；
2.
在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3.
在后序序列中确定左右子树的后序序列；
4.
由左子树的后序序列和中序序列建立左子树；
5.
由右子树的后序序列和中序序列建立右子树。
例如：已知二叉树的后序序列gdbehfca,
中序序列dgbaechf。
后序：gdbehfca
->根：a
根据根结点来划分中序序列
中序：dgbaechf
->
dgb+a+echf
由左右子树的结点集合来划分后序序列->后序：gdb+ehfc+a
分别对根a的左右子树运用相同的方法分解出根和其左右子树的结点集合。
左子树后序序列gdb
－>根：
b
根据根结点来划分左子树中序序列
中序：dgb
->
dg+
b
说明没有右子树
由左右子树的结点集合来划分后序序列->后序：gd+b
对根b的左子树运用相同的方法分解出根和其左右子树的结点集合。依次递归。
得到的二叉树：
a
/
\
b
c
/
/
\
d
e
f
\
/
g
h

3. C++: 题目如下:已知一棵二叉树的先序，中序和后序序列如下，其中各有一部分未给出其值，请构造出该

4. 二叉树的先序、中序和后序序列 请构造出该二叉树

先序的第一个为二叉树树根A，因此后序的最后一个也是A
回到中序，以A为根划分，左子树有4个结点，右子树有5个结点
现在看后序：前4个最后的是B，因此先序的第二个是B，并且中序的第二个也是B
简化如下：
先序序列 ：A B C D E F_  H  _ J 
中序序列 ：C B E D A _ G F I _  
后序序列 ：C _ _ B H G J I _ A
回到先序，A后面连续4个为左子树的先序，因此后面的F就是右子树的根
因此后序的倒数第2个就是F
再利用先序的DE和中序的ED可以得到后序为ED
于是再次简化为：
先序序列 ：A B C D E F _ H _ J 
中序序列 ：C B E D A _ G F I _  
后序序列 ：C E D B H G J I F A
现在来看右子树：已知右子树的根为F
从中序可知，F有左右子树，且左右均为2个结点，
从后序序列可知其前的I就是右子树的根，因此，先序J前面的就是I，并且中序最后的就是J

剩下的就可以补充完整了（其实用二叉树的遍历序列也可硬性推导出）
最后结果是：
先序序列 ：A B C D E F G H I J 
中序序列 ：C B E D A H G F I J  
后序序列 ：C E D B H G J I F A

5. 已知二叉树的先序序列和中序序列怎么求后序序列？不是基于C++的，要在TC环境下能运行的，各位能人帮帮忙吧

/*    树中已知先序和中序求后序。

      如先序为：abdc,中序为：bdac .

      则程序可以求出后序为：dbca 。此种题型也为数据结构常考题型。

    算法思想：先序遍历树的规则为中左右，则说明第一个元素必为树的根节点，比如上例

中的a就为根节点,由于中序遍历为：左中右，再根据根节点a，我们就可以知道，左子树包含

元素为：db，右子树包含元素：c，再把后序进行分解为db和c（根被消去了），然后递归的

进行左子树的求解（左子树的中序为：db，后序为：db），递归的进行右子树的求解（即右

子树的中序为：c，后序为：c）。如此递归到没有左右子树为止。

关于“已知先序和后序求中序”的思考：该问题不可解，因为对于先序和后序不能唯一的确定

中序，比如先序为 ab，后序为ba，我只能知道根节点为a，而并不能知道b是左子树还是右子树

，由此可见该问题不可解。当然也可以构造符合中序要求的所有序列。





*/

#include 
#include 

int find(char c,char A[],int s,int e) /**//* 找出中序中根的位置。 */

{

int i;

for(i=s;i<=e;i++)

      if(A[i]==c) return i;

}

/**//* 其中pre[]表示先序序，pre_s为先序的起始位置，pre_e为先序的终止位置。 */

/**//* 其中in[]表示中序，in_s为中序的起始位置，in_e为中序的终止位置。 */

/**//* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]构成的后序序列。 */

void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)

{

char c;

int k;

if(in_s>in_e)    return ;                 /**//* 非法子树，完成。 */

if(in_s==in_e){printf("%c",in[in_s]); /**//* 子树子仅为一个节点时直接输出并完成。 */

                  return ;

                  }

c=pre[pre_s];                           /**//* c储存根节点。 */

k=find(c,in,in_s,in_e);                 /**//* 在中序中找出根节点的位置。 */

pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /**//* 递归求解分割的左子树。 */

pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /**//* 递归求解分割的右子树。 */

printf("%c",c);                         /**//* 根节点输出。 */

}

void main()

{

char pre[]="abdc";

char in[]="bdac";

printf("The result:");

pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);

getchar();

}

6. 根据先序和中序序列生成二叉树

在二叉树中，有三种主要的遍历方式（假设父节点为N，左孩子为L，右孩子为R）：
  
 先序遍历：N -> L -> R
  
 中序遍历：L -> N -> R
  
 后序遍历：L -> R -> N
                                          
 假设现有一颗二叉树如上图所示，上述二叉树的先序遍历和中序遍历结果为：
  
 先序遍历：ABCDEF
  
 中序遍历：CBDAEF
  
 分析： 先序遍历服从规则“根左右”，所以，对于一个先序遍历得到的数组，第一个元素一定是根节点；中序遍历服从规则”左根右“，所以由此可知，对于一个中序遍历得到的数组，根节点左边的元素都属于根节点的左子树，而根节点右边的元素都属于根节点的右子树。所以，可以先通过先序遍历的第一个元素确定根节点，然后通过中序遍历结合根节点，获得当前根节点的左右子树，再将子树看成一棵独立的树，继续使用先序遍历判断根节点，中序遍历判断子树的方式，最终建立起整棵树 。
  
 详细算法如下：
  
 1、先序或中序为空则返回，否则，通过先序序列创建根结点，再通过根节点在中序遍历的位置找出左右子树。
  
 2、在根绝点的左子树中，找左子树的根结点（在先序中找），转步骤1。
  
 3、在根节点的右子树中，找右子树的根结点（在先序中找），转步骤1。
  
 根据上述算法，可以看出创建出二叉树的关键在于先序序列和中序序列的划分，在对序列进行划分的时候要注意边界的问题。
  
 递归方式
  
 非递归方式

7. 给出先序和中序画出二叉树

问     题：
若某二叉树的前遍历访问顺序是序abdgcefh,中序遍历顺序是dgbaechf,则后序遍历的访问顺序是什么。
解    答：
此题的解答过程如下： 
（1）由前序遍历结果我们可知a为根结点，再看中序遍历结果，因为中序遍历顺序是左子树、根、右子树，因此由“中序遍历顺序是dgbaechf”可断定，dgb为该二叉树的左子树中序遍历结果，echf为右子树中序遍历结果。
（2）由前序遍历结果可知，左子树的前序遍历结果是bdg,右子树的前序遍历结果是cefh;因此，和第一步分析类似，可知b为左子树的根，再由“dgb 为该二叉树的左子树中序遍历结果”可知，dg为该左子树的左子树的中序遍历结果，再由dg在前序遍历结果中排列顺序dg可知，d为根，因此由“dg为该左 子树的左子树的中序遍历结果”可推出g为d的右孩子。
到此为止，可以完全推断出该二叉树的左子树的结构了。
按照同样方法，可以推断出该二叉树的右子树的结构，因此整个二叉树的结构图如下：
据此图，不难看出该二叉树的后序遍历结果是：gdbehfca.

8. 请问这个二叉树的前，中后序序列是怎样排列的，希望可以详细把这个知识点解答，尤其是中序，实在是不会，

中序遍历的顺序是左子树再根然后右子树
本题：
首先进入遍历判断是根A，发现A有左子树所以再次判断B，B也有左子树D，D没有左子树为空，所以第一个输出的是D，然后是根B，再B的右子树E，但是E有左子树G，所以G先遍历，然后E。
A的左子树都遍历完成后，遍历A，再遍历A的右子树C，C有左子树F，所以F先，F没有左子树只有右子树H，遍历F后遍历H，C的左子树遍历完成，遍历C，C没有右子树，最终A的右子树也遍历完成。
所以本题中序顺序是：DBGEAFHC
后序遍历的顺序是先左子树再右子树最后根，答案：DGEBHFCA
遍历题一定要记住前序、中序和后序的遍历顺序。