乐趣区

关于javascript:已知一棵二叉树如果先序遍历的节点顺序是-KDCEFGHB-中序遍历是-CDFEGHKB-则后续遍历结果为

二叉树遍历

题目形容

(单选)已知一棵二叉树,如果先序遍历的节点程序是:KDCEFGHB, 中序遍历是:CDFEGHKB, 则后续遍历后果为()

  • [] A. CFHGEBDK
  • [] B. CDFEGHBK
  • [] C. FGHCDEBK
  • [x] D. CFHGEDBK

树遍历规定:(按根的地位记忆)

  • 先序:(根 左 右)根优先
  • 中序:(左 根 右)根两头
  • 后序:(左 右 根)根最初

思路:

  1. 先确定根节点
  2. 在确定左子树和右子树
    2.1 从左子树中找到左子树的根,回到步骤 1
    2.2 从右子树中找到右子树的根, 回到步骤 1
  3. 直至查找完,建设树

详细分析:

先序遍历第一个肯定是树根, 那么 K 为根;
那么中序遍历中 K 的俩边别离是左子树和右子树;
左子树为 CDFEGH 右子树为 B

        K
CDFEGH     B

左子树中先序遍历为 DCEFGH 中 D 在最后面,所有 D 是左子树的根;

C 是左子树,FEGH 是右子树

      K
  D        B
C   FEGH

FEGH 子树中,先序遍历是 EFGH, 所有 E 是子树根

F 是左子树,GH 是右子树

      K
  D        B
C    E
   F   GH

GH 子树中,先序遍历 GH, 所以 G 是根,H 是右子树

      K
  D        B
C    E
   F   G
         H

所以后续遍历为:

C F H G E D B K

退出移动版