2019考研计算机：数据结构遍历二叉树复习重点

考研网

《数据结构(C语言版)》复习重点在二、三、六、七、九、十章，考试内容两大类：概念，算法，自从计算机专业课统考以后，专业课考试题型分为2类，一类选择题，一类综合应用题。接下来是新东方在线整理的数据结构(C语言版)遍历二叉树复习重点。
    　　遍历二叉树：
    1、根据二叉树写遍历结果：
    二叉树如下，请写出写遍历结果：
   

    a) 先序遍历(先根遍历)：DLR
    - + a * b - c d / e f
    b) 中序遍历(中根遍历)：LDR
    a + b * c - d - e / f
    c) 后序遍历(后根遍历)：LRD
    a b c d - * + e f / -
    2、根据遍历结果画二叉树：
    一棵二叉树的先序、中序和后序序列分别如下，其中有部分未给出，试求出空格处的结点字符，并画出该二叉树。
    先序：__B__EHI__FG__K
    中序：D__HEIA__CJG__
    后序：__H__EBF__KG__A
    根据先后中序画出二叉树结果如下：
   

    解题思路：
    a) 由先序或后序确定根结点;如本题后序最后一个为A，根结点为A，所以先序第一个空就为A。
    b) 在中序找出根结点，根结点左侧为左子树，右侧为右子树;如本题D__HEI为左子树，__CJG__为右子树。
    c) 由先序确定紧跟在根结点后的左子树根;如本题紧跟在A后的是B，B为左子树根，中序根结点的左子树只有一个空，所以为B。
    d) 继续由中序确定左子树根的左右子树，左侧为左子树，右侧为右子树;如本题B的左子树为D，右子树为HEI，所以先序第二个空为D。
    e)
重复c)、d)步骤确定整棵左子树;如本题先序中紧跟在D后的是E，E为B的右子树，由中序中看出E左子树为H，右子树为I，补充后序填空，前两空分别为D和I。
    f)
由后序确定右子树根的左子树，再由中序确定右子树根;如本题紧跟在B后的是F，F为右子树根的左子树，已知中序__CJG__为右子树，F只可能第一个空，那第二个空为K，补全先序、中序、后序填空并可画出二叉树。