操作方法
我们也是用一个例子来讲我们的方式方法,例子如下图所示
拿到这样的题目的时候,我们第一步先看后根序列,后根序列是最后访问的根节点,所以我们这个时候能够确定的是根,如下图所示 我们可以确定a是根
第二步,确定了根节点之后,我们再看中根序列,这样可以确定左右孩子。如下图所示
第三步,定了左右孩子之后我们再看后根序列,再确定左子树的根节点。可以确定左子树的根节点是b,如下图
第四步,再看中根序列,然后确定左子树的左右孩子,这样一步一步的往下走
第五步,已经知道了 e d是左子树的右子树,然后接着看后根序列,这个时候有如下图所示的两种情形,
第六步,我们要根据中根序列来确定到底是哪一种树是我们想要的。过程如图所示,我们可以确定后面的一种是我们想要的。到这个地方我们的左子树就已经确定好了
第七步,我们接着来看右子树。还是先看后根序列和中根序列。
第八步,来确定右子树的左子树,方法和前面的类似,就不多讲
第九步,看中根序列确定g节点的右子树
第十步,看后根序列确定g节点的右子树的右根
现在就是我们的最后一步了,看中根序列确定就可以了。