Download presentation
Presentation is loading. Please wait.
1
二叉树的还原 二叉树的周游方式 前序周游 后序周游 中序周游 可以由哪两种周游方式唯一确定一棵二叉树？
前序+中序？ 前序+后序？ 中序+后序？
2
前序+后序 前序：AB 后序：BA A A B B 通过这一简单的反例可知，前序和后序无法唯一确定一棵二叉树！
3
例 前序：ABDECF 中序：DBEAFC 后序：DEBFCA
4
中序+后序 中序：DBEAFC 后序：DEBFCA 由后序序列可知根结点是 A 再根据中序序列，可判断左右子树 中序 DBE A FC
左子树 右子树 同理，再对左子树，右子树进行上述分析 左子树的根结点是 B 右子树的根结点是 C D B E Ｆ C 左子树 右子树 左子树
5
故还原成一棵唯一的二叉树！ Ａ Ｂ Ｃ Ｄ Ｅ Ｆ
6
前序和中序还原二叉树 A B C D F E
7
再来看一下课本上例题５．１二叉树的还原 前序：Ａ ＢＤ ＣＥＧＦＨＩ 中序：ＢＤＡＧＥＣＨＦＩ 左子树 右子树 B D ＧＥ Ｃ ＨＦＩ
前序：Ａ ＢＤ ＣＥＧＦＨＩ 根 左子树 右子树 中序：ＢＤＡＧＥＣＨＦＩ 左子树 右子树 B D ＧＥ Ｃ ＨＦＩ 根 右子树 左子树 右子树 右子树继续分解： 左子树 右子树 G E Ｈ Ｆ Ｉ 由此还原成唯一的一棵二叉树！ （中序＋后序同理可得）
8
上述还原方法采用了递归的思想 根据先序的第一个元素或者后序的最后一个元素来确定根结点。 在中序序列找到该元素，确定该元素的左右子树的中序序列。 再分别对左右子树进行上述步骤的还原
Similar presentations
