1 树和二叉树
一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）
（ √ ）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（ × ）2.二叉树中每个结点的两棵子树的高度差等于1。
（ √ ）3.二叉树中每个结点的两棵子树是有序的。
（ × ）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（ × ）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点）
（ × ）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1）
（ × ）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（ × ）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）
（ √ ）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
（正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。
（ √ ）10.具有12个结点的完全二叉树有5个度为2的结点。
最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5
二、填空（每空1分，共15分）
1． 由３个结点所构成的二叉树有 5 种形态。
2. 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32
个叶子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
3． 一棵具有２５７个结点的完全二叉树，它的深度为 9 。
a 习题6 树和二叉树
说明：
本文档中，凡红色字标出的题请提交纸质作业，只写题号和答案即可。
6.1 单项选择题
1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法__B__。
A. 正确 B. 错误
2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 B 个。
A．15 B．16 C．17 D．47
3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有__C__种。
A. 3 B. 4 C. 5 D. 6
4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有__C__种。
A. 5 B. 6 C. 30 D. 32
5. 深度为5的二叉树至多有__C__个结点。
A. 16 B. 32 C. 31 D. 10
6. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ B ___。
A. 2h B. 2h-1 C. 2h+1 D. h+1
7. 对一个满二叉树，m个树叶，n个结点，深度为h，则__A__ 。
A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1
8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序__A__。
A.不发生改变 B.发生改变 C.不能确定 D.以上都不对
9. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为__C__。 A. uwvts B. vwuts C. wuvts D. wutsv
10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__A__。
树和二叉树
数据的逻辑结构
树形结构（非线性结构）：1）节点之间有分支；2）具有层次关系。
应用：自然界的树；人类社会的家谱和行政组织机构；计算机中的编译（用树表示源程序的语法结构）、数据库系统（用树组织信息）、算法分析（用树描述执行过程）。
定义：是n（n>=0）个节点的有限集。
若n=0,称为空树；
若n>0，则它满足如下两个条件；
1）有且仅有一个特定的称为根的节点；
2）其余节点可分为m（m>=0）个互不相交的有限集T1,T2,T3.....Tm，其中每一个集合本身又是一棵树，并称为根的子树。
树的其他表示方式：
还可以用广义表的形式表示（A(B(D))(C(E)(F))）。
树的基本术语：
根节点：非空树中无前驱节点的节点。
节点的度：节点拥有的子树数。
树的度：树内各节点的度的最大值。
叶子（终端节点）：度为0的节点
分支节点（非终端节点）：根节点以外的分支节点称为内部节点。
孩子、双亲：节点的子树的根称为该节点的孩子，该节点称为孩子的双亲。 线性结构
（1:1）
非线性结构 字符串、数组（一维）、广义表（非） 队列（特殊线性表） 栈（特殊线性表） 线性表
树形结构（1：n一个节点有多个后继，但只有一个前驱）
图形结构（n：n一个节点有多个后继，也有多个前驱） 兄弟节点：
节点的祖先：从根节点所经分支上的所有节点。
节点的子孙：以某节点为根的子树中的任一节点。
树的深度（高度）：树中最大层次（根节点为第一层）。
有序树：树中节点的各子树从左至右有次序（）
无序树：树中的节点没有次序。
森林：是m（m>=0）棵互不相交的树的集合。一棵树可以看成是一个特殊的森林。给森林中的各子树加上一个双亲节点，森林就变成了树（树一定是森林，森林不一定是树）。
二叉树的性质和存储结构
性质1、在二叉树的第i层上至多有2^(i-1)个节点（i>=1）。至少1个
归纳基：当i=1时，只有一个根节点，2^(i-1)=2^0=1，命题成立。
数据结构
Date
Time
1 第6章 树和二叉树
内容概要：本章主要介绍树，二叉树，最优二叉树的相关概念和操作，存储结构和相应
的操作，并在综合应用设计中，给出了对应算法的C语言实现。
教学目标
1．理解各种树和森林与二叉树的相应操作。
2．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其他操作。
3．熟练掌握二叉树和树的各种存储结构及其建立的算法。
4．掌握哈夫曼编码的方法。
5．通过综合应用设计，掌握各种算法的C语言实现过程。
基本知识点： 树和二叉树的定义、二叉树的存储表示、二叉树的遍历以及其它操作的
实现、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码
重点：二叉树的性质、二叉树的遍历及其应用，构造哈夫曼树。
难点：编写实现二叉树和树的各种操作的递归算法。
本章知识体系结构：
课时安排：
6个课时 树的定义
树 树的性质 树的逻辑表示法 树形表示法
树的存储结构 双亲存储结构 文氏表示法
凹入表示法
括号表示法 孩子存储结构
孩子双亲存储结构
二叉树 二叉树的定义
二叉树的性质
二叉树的逻辑表示法（采用树的逻辑表示法）
二叉树的存储结构 二叉树的顺序存储结构
先序遍历
中序遍历
后序遍历 二叉树的遍历 二叉树的链式存储结构（二叉链）
由先序序列和中序序列构造二叉树
由中序序列和后序序列构造二叉树 二叉树的构造
二叉树的线索化
哈夫曼树 二叉树和树之间的差别
二叉树与树、森林之间的转换 二叉树和树
数据结构
Date
Time
2
课程 数据结构 教学教具 多媒体课件
学时 2 班级 06网络 教学日期/课时 /2课时
教学单元 第6章 树和二叉树
教学方法 讲授（PPT）
教学目标 掌握树、二叉树的基本概念和术语，二叉树的性质
教学重点 二叉树的定义、二叉树的性质、链式存储结构
教学难点 二叉树的性质、链式存储二叉树的基本操作
组
织
教
学 一、树的定义
