1 第六章 树和二叉树
一．选择题
1. 以下说法错误的是 。
A.树形结构的特点是一个结点可以有多个直接前趋
B.线性结构中的一个结点至多只有一个直接后继
C.树形结构可以表达(组织)更复杂的数据
D.树(及一切树形结构)是一种"分支层次"结构
2. 如图6-2所示的 4 棵二叉树中， 不是完全二叉树。
图6-2 4 棵二叉树
3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是 。
A. t->left == NULL B. t->ltag==1
C. t->ltag==1 且 t->left==NULL D .以上都不对
4. 以下说法错误的是 。
A.二叉树可以是空集
B.二叉树的任一结点最多有两棵子树
C.二叉树不是一种树
D.二叉树中任一结点的两棵子树有次序之分
5. 以下说法错误的是 。
A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B.在三叉链表上，二叉树的求双亲运算很容易实现
C.在二叉链表上，求根，求左、右孩子等很容易实现
D.在二叉链表上，求双亲运算的时间性能很好
6. 如图6-3所示的 4 棵二叉树， 是平衡二叉树。 2
图6-3 4 棵二叉树
7. 如图6-4所示二叉树的中序遍历序列是 。
A. abcdgef B. dfebagc C. dbaefcg
D. defbagc
图6-4 1 棵二叉树
8. 已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是 。
A. acbed B. decab C. deabc D. cedba
数据结构(一)
目 录
第1章 序论 ................................................................................................ 1
1.1 什么是数据? .......................................................................................... 1
1.2 什么是数据元素? ...................................................................................... 1
1.3 什么是数据结构及种类? ................................................................................ 1
1.4 数据的逻辑结构 ....................................................................................... 1
1.5 数据的物理结构 ....................................................................................... 1
1.6 算法和算法分析 ....................................................................................... 1
1.7 算法的五个特性 ....................................................................................... 1
..WORD完美格式..
..专业知识编辑整理..
第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）
习 题
一、选择题
1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( )。
A.向量 B.树 C图 D.二叉树
2．树最合适用来表示( )。
A.有序数据元素 B元素之间具有分支层次关系的数据
C无序数据元素 D.元素之间无联系的数据
3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。
A. la (2b (3d,3e),2c) B. a(b(D,e),c)
C. a(b(d,e),c) D. a(b,d(e),c)
4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。
A. 2h_l B.h C．2h-1 D. 2h
5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。
A. 2i B. 2i-l C. 2i+l D. 2i+2
6.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为 ( )。
A.3 B.4 C.5 D.6
7.深度为5的二叉树至多有( )个结点。
A. 31 B. 32 C. 16 D. 10
数据结构
Date
Time
1 第6章 树和二叉树
内容概要：本章主要介绍树，二叉树，最优二叉树的相关概念和操作，存储结构和相应
的操作，并在综合应用设计中，给出了对应算法的C语言实现。
教学目标
1．理解各种树和森林与二叉树的相应操作。
2．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其他操作。
3．熟练掌握二叉树和树的各种存储结构及其建立的算法。
4．掌握哈夫曼编码的方法。
5．通过综合应用设计，掌握各种算法的C语言实现过程。
基本知识点： 树和二叉树的定义、二叉树的存储表示、二叉树的遍历以及其它操作的
实现、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码
重点：二叉树的性质、二叉树的遍历及其应用，构造哈夫曼树。
难点：编写实现二叉树和树的各种操作的递归算法。
本章知识体系结构：
课时安排：
6个课时 树的定义
树 树的性质 树的逻辑表示法 树形表示法
树的存储结构 双亲存储结构 文氏表示法
凹入表示法
括号表示法 孩子存储结构
孩子双亲存储结构
二叉树 二叉树的定义
二叉树的性质
二叉树的逻辑表示法（采用树的逻辑表示法）
二叉树的存储结构 二叉树的顺序存储结构
先序遍历
中序遍历
后序遍历 二叉树的遍历 二叉树的链式存储结构（二叉链）
由先序序列和中序序列构造二叉树
由中序序列和后序序列构造二叉树 二叉树的构造
二叉树的线索化
哈夫曼树 二叉树和树之间的差别
二叉树与树、森林之间的转换 二叉树和树
数据结构
Date
Time
2
课程 数据结构 教学教具 多媒体课件
学时 2 班级 06网络 教学日期/课时 /2课时
教学单元 第6章 树和二叉树
教学方法 讲授（PPT）
教学目标 掌握树、二叉树的基本概念和术语，二叉树的性质
教学重点 二叉树的定义、二叉树的性质、链式存储结构
教学难点 二叉树的性质、链式存储二叉树的基本操作
组
织
教
学 一、树的定义
