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