二叉树的还原 二叉树的周游方式 前序周游 后序周游 中序周游 可以由哪两种周游方式唯一确定一棵二叉树? 前序+中序? 前序+后序? 中序+后序?
前序+后序 前序:AB 后序:BA A A B B 通过这一简单的反例可知,前序和后序无法唯一确定一棵二叉树!
例 前序:ABDECF 中序:DBEAFC 后序:DEBFCA
中序+后序 中序:DBEAFC 后序:DEBFCA 由后序序列可知根结点是 A 再根据中序序列,可判断左右子树 中序 DBE A FC 左子树 右子树 同理,再对左子树,右子树进行上述分析 左子树的根结点是 B 右子树的根结点是 C D B E F C 左子树 右子树 左子树
故还原成一棵唯一的二叉树! A B C D E F
前序和中序还原二叉树 A B C D F E
再来看一下课本上例题5.1二叉树的还原 前序:A BD CEGFHI 中序:BDAGECHFI 左子树 右子树 B D GE C HFI 前序:A BD CEGFHI 根 左子树 右子树 中序:BDAGECHFI 左子树 右子树 B D GE C HFI 根 右子树 左子树 右子树 右子树继续分解: 左子树 右子树 G E H F I 由此还原成唯一的一棵二叉树! (中序+后序同理可得)
上述还原方法采用了递归的思想 根据先序的第一个元素或者后序的最后一个元素来确定根结点。 在中序序列找到该元素,确定该元素的左右子树的中序序列。 再分别对左右子树进行上述步骤的还原