11

已知一棵二叉树，如果先序遍历的节点顺序是： KDCEFGHB, 中序遍历是： CDFEGHKB, 则后...

 3 years ago
source link: https://segmentfault.com/a/1190000040700166
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

二叉树遍历

（单选）已知一棵二叉树，如果先序遍历的节点顺序是： 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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK