Home > programming > inorder and postorder to construct binary tree

inorder and postorder to construct binary tree


题目:
设对一棵二叉树进行中序遍历和后序遍历的结果分别为:
(1)中序遍历 B D C E A F H G
(2)后序遍历 D E C B H G F A
画出该二叉树。

解答:

1.由后序遍历最后一位是A可知:A为根节点

2.由中序遍历可把由A把原节点分为BDCE,FHG左右子树 // BDCE(A)FHG

3.由后序遍历BDCE顺序为DECB,可知B为左子树根节点

4.由中序遍历BDCE顺序为BDCE,可知该子树无左子树,右子树有节点DEC

5.由后序遍历DCE顺序为DEC,可知C为下一个子树的根节点

6.由中序遍历DCE顺序为DCE,可知DE分别为根节点C的左右子树(叶子)

以A为根的树的左子树处理完毕,右子树相同处理即可。

总结:

1.由后续遍历最后一位判断根节点

2.由该根节点在中序遍历中的位置判断以它为根节点的其他节点的左右分布

3.循环上面两项直到完成。

Advertisements
Categories: programming
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: