设二叉树的前序序列为ABDEGHCFIJ,中序序列为DBGEHACIFJ。则后序序列为( )。

admin2019-06-12  33

问题 设二叉树的前序序列为ABDEGHCFIJ,中序序列为DBGEHACIFJ。则后序序列为(    )。

选项 A、JIHGFEDCBA
B、DGHEBIJFCA
C、GHIJDEFBCA
D、ABCDEFGHIJ

答案B

解析 二叉树的前序序列为ABDEGHCFIJ,由于前序遍历首先访问根结点,可以确定该二叉树的根结点是A。再由中序序列为DBGEHACIFJ,可以得到结点D、B、G、E、H位于根结点的左子树上,结点C、I、F、J位于根结点的右子树上。由于中序遍历和后序遍历都是先遍历左子树,故本题后序遍历首先访问D结点;再由后序遍历是最后访问根结点,故本题后序遍历最后访问的结点是根结点A。采用排除法可知,后续序列为DGHEBIJFCA。
转载请注明原文地址:https://kaotiyun.com/show/Qeep777K
0

最新回复(0)