如何根据二叉树的前序遍历和中序遍历如何构建二叉树

Question

如题所述

Answer 1

已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：
1. 根据前序序列的第一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在前序序列中确定左右子树的前序序列；
4. 由左子树的前序序列和中序序列建立左子树；
5. 由右子树的前序序列和中序序列建立右子树。

已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：
1. 根据后序序列的最后一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在后序序列中确定左右子树的后序序列；
4. 由左子树的后序序列和中序序列建立左子树；
5. 由右子树的后序序列和中序序列建立右子树。
另外,站长团上有产品团购,便宜有保证本回答被提问者和网友采纳