以下面的序列为例
先根序列 a b e c d f g h i j
中根序列 e b c d a f h i g j
首先确认二叉树的根节点
由于先根序列中第一个元素是 a, 因此根元素是a
再根据中根序列知道根元素的左子树序列是 e b c d , 右子树序列是 f h i g j
在左子树中, 先根序列是 b e c d , 因此 b 是左子树的根元素, 因此节点 b 的左子树是 e, 右子树是 c d.
然后再分别对左右子树序列重复上面的过程, 进行递归, 即可确认二叉树的具体形状, 并求出另外一个序列
网友评论