C++ 根据前序和中序画二叉树

Question

前序abcdefgh,
中序cdbagfeh,
是不是这样子的？
画这个到底有什么诀窍？？？
大佬能解答一下？？
到底要怎么区分左右子树的子节点在左侧还是在右侧

Answer 1

首先
前序的意思是：中-->左-->右
中序的意思是：左-->中-->右

分析

01 前序：abcdefgh 说明根节点为 a
02 中序：cdbagfeh 由于根节点为 a，所以 cdb 在 a 的左子树上，gfeh 在 a 的右子树上

先考虑 a 的左子树

03 前序为：bcd 说明根节点为 b
04 中序为：cdb 由于根节点为 b，所以 cd 在 b 的左子树上

再考虑 b 的左子树

05 前序为：cd 说明根节点为 c
06 中序为：cd 由于根节点为 c，所以 d 为 c 的右节点

再考虑 a 的右子树

07 前序：efgh 说明根节点为 e
08 中序：gfeh 由于根节点为 e，所以 gf 在 e 的左子树上，h 在 e 的右子树上，h 为 e 的右节点

再考虑 e 的左子树

09 前序：fg 说明根节点为 f
10 中序：gf 由于根节点为 f，所以 g 为 f 的左节点

总结：

由 01 可知，根节点为 a

由 03 可知，a 的左节点为 b
由 07 可知，a 的右节点为 e

由 05 可知，b 的左节点为 c

由 09 可知，e 的左节点为 f
由 08 可知，e 的右节点为 h

由 06 可知，c 的右节点为 d

由 10 可知，f 的左节点为 g

画个图：

            a
          /   \
         b     e
        /     / \ 
       c     f   h
        \   /   
         d g
         

差不多就这样分析

---

---

更新：由中序和后序，画二叉树

首先
后序的意思是：左-->右-->中
中序的意思是：左-->中-->右

分析

01 后序：abcdefgh 说明根节点为 h
02 中序：aedbchgf 由于根节点为 h , 所以 aedbc 在 h 的左子树上，gf 在 h 的右子树上

先考虑 h 的左子树

03 后序：abcde 说明根节点为 e
04 中序：aedbc 由于根节点为 e，所以 a 是 e 的左节点，dbc 在 e 的右子树上

再考虑 e 的右子树

05 后序：bcd 说明根节点为 d
06 中序：dbc 由于根节点为 d，所以 bc 在 d 的右子树上

再考虑 d 的右子树

07 后序：bc 说明根节点为 c
08 中序：bc 由于根节点为 c，所以 b 是 c 的左节点

再考虑 h 的右子树

09 后序：fg 说明根节点为 g
10 中序：gf 由于根节点为 g，所以 f 为 g 的右节点

总结：

由 01 可知，根节点为 h

由 03 可知，h 的左节点为 e
由 09 可知，h 的右节点为 g

由 04 可知，e 的左节点为 a
由 05 可知，e 的右节点为 d

由 10 可知，g 的右节点为 f

由 07 可知，d 的右节点为 c

由 08 可知，c 的左节点为 b

画个图：

           h
          / \
         e   g
        / \   \
       a   d   f
            \
             c
            /
           b