2019考研计算机：数据结构遍历二叉树复习重点
《数据结构(C语言版)》复习重点在二、三、六、七、九、十章，考试内容两大类：概念，算法，自从计算机专业课统考以后，专业课考试题型分为2类，一类选择题，一类综合应用题。接下来是新东方在线整理的数据结构(C语言版)遍历二叉树复习重点。遍历二叉树：
1、根据二叉树写遍历结果：
二叉树如下，请写出写遍历结果：
http://file.koolearn.com/35961544661881.png
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
根据先后中序画出二叉树结果如下：
http://file.koolearn.com/15331544661881.png
解题思路：
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，补全先序、中序、后序填空并可画出二叉树。
页:
[1]