Question

已知二叉树的前序和中序后序 怎么用c求它的层次遍历

不建立二叉树行不行，可以的话最好不要建立

Answer 1

可以不用建立二叉树。

使用两个队列A,B，A用来存放当前要遍历的层，B队列用来存放A队列那层的下一层（当然在实际编程中可以通过分割元素将AB放在一个队列中）。

算法：

1. 将前序遍历的第一个节点（根节点）加入队列A。

2. 如果队列A为空，跳转到第4步，否则执行第3步。

3. 对于队列A中的每一个元素，找到其左右孩子，并将其左右孩子依次放入队列B。在遍历队列A时，就是在以层次遍历法遍历此二叉树。当队列A中的每一个元素都处理完成后，将队列B作为队列A（即要遍历的下一层），将队列A清空作为新的队列B。跳转到第2步。

4. 结束。

   
   

对于队列中任意一节点，如何找到其左右孩子？

找左孩子：任意一节点N，在前序遍历中找到其下一个节点X（若N为最后一个节点，则N无孩子）。在此二叉树的中序遍历中，如果X在N的前面（不一定相邻），则X为N的左孩子，否则N无左孩子。

找右孩子：任意一节点N，在后序遍历中找到N前面一个节点X（若N为第一节点，则N无孩子），在此二叉树的中序遍历中，如果X在N的后面（不一定相邻），则X为N的右孩子，否则N无右孩子。

Answer 2

无需建立二叉树：

1. 获取当前前序序列的第一个元素并输出（按层次遍历）

2. 从对应的中序序列中找到该元素，该元素此时将二分中序序列中的元素

3. 依据划分出的两个序列，在前序序列中找到这两个序列（按照中序中序列的元素个数即可划分）

4. 对划分后的先序序列继续1, 2，3两步（要平行进行不能处理完一个序列再处理另一个序列）直到遍历全部元素，此时得到的序列即为层次遍历序列。

例如： 先序ABDECFG， 中序DBEAFCG

   按照算法：

1. 输出先序第一个元素A

2. 依据A得到中序划分后的两个序列DBE，FCG，因此此时序列第一个子序列的长度为3

   3.  由于划分后的左序列长度为3，先序中除A以外剩下的元素被划分为BDE、CFG

   4.  对先序序列BDE和CFG重复上面的步骤，先输出两个序列的先序第一个元素B、C

   5, 从中序序列DBE，FCG得到划分的子序列D、E和F、G，左序列的长度都为1

   6. 因此前序序列被划分为了D、E和F、G四个序列，接着输出D、E、F、G

  因此遍历的序列为ABCDEFG