由遍历序列求二叉树

已知一棵二叉树中序遍历序列为DGBAECHIF，后序遍历序列为ABDGCEFHI，求出该二叉树；望高手指教啊~~~

8269680 · 2018-4-30 01:03:53

先序：中左右：1243576
中序：左中右：4215736
看先序，第一位为1，1就为二叉树的第一位。在看中序，可得该二叉树左边为：2，4；右边为：5，7，3，6；将中序分为两部分：2，4与3，5，7，6，这样1的两个子结点为2和3。看中序，4在2前面，4就在2的左边，5和7在3的前面，那么5和7就在3的左边，6在3的右边。最后要确定5和7的位置，看先序，5在7的前面，因此5在3的左边，7在5的左边。由此得树：
   1
   / \
2 3
/ /  \
  4 5 6
   /
   7
根据后序：左右中，得：4275631

时间比较紧,这是以前我的最佳回答,只要把你的数据替换以下就好了,祝你成功

yhm9084nerv · 2018-4-30 01:03:54

#1楼得分：0回复于：2008-12-01 09:24:32根据前序遍历序列的第一个元素,为树的根,可以把中序遍历序列分为俩部分,前面一部分是左子树,后面一部分是右子树.然后再分开求这俩部分,再在前序遍历序列找各自最先出现的元素,再分,一直分到都是元素的时候就行拉.EG:前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F根节点D,在中序序列中可以把序列分为俩部分左子树 (空集,)和右子树元素C，B，E，H，A，G，I，F接着分别画左,右子树.左子树 (空集,)不用画。
右子树:可以从前序序列找出右子树的根接点A又可以把右子树元素C，B，E，H，A，G，I，F分为俩部分C，B，E，H,和G，I，F再根据前序序列,再分,同样的作法.不知道我说清楚了没?

由遍历序列求二叉树

2 个回复