第7章树和二叉树学习指导

《第7章树和二叉树学习指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第7章树和二叉树7.1知识点分析1•树的定义和术语（1）树树是n（n>0）个有限数据元素的集合。在任意一棵非空树T中，有且仅有一个特定的称为树根（Root）的结点（根结点无前驱结点），当n>l时，除根结点Z外的其余结点被分成m（m>0）个互不相交的集合T],T2,Tm,其中每一个集合口（1

2、称为树的深度或高度。2.二叉树（1）二叉树一棵非空的二叉树，每个结点至多只有两棵子树，分别称为左子树和右子树，左、右子树的次序不能任意交换，且左右子树乂分别是一棵二叉树。（2）满二叉树一棵深度为h,且有2h-1个结点的二叉树称为满二叉树。（3）完全二叉树深度为h,有n个结点的二义树，当且仅当每一个结点都与深度为h的满二义树中编号从1至n的结点一一对应时，称此二叉树为完全二叉树。3.关于二叉树的儿个最常用的性质性质1—棵非空二叉树的笫i层上最多有2E个结点（i>1）。性质2深度为h的二叉树中，最多具有2''—1个结点（h>l）o性质3对于一棵有n个结点的完全二叉树，若按满二

3、叉树的同样方法对结点进行编号,则对于任意序号为i的结点，有：（1）若i>l,则序号为i的结点的父结点的序号为i/2；（2）若2i

4、）二叉树后序遍历二义树厉序遍历先厉序遍历左子树，再厉序遍历右子树，最厉访问根结点。（4）层次遍历从根结点开始，按照自上而下，从左到右（同一层）的顺序逐层访问二叉树上的所冇结点，这样的遍历称为按层次遍历。2.线索二叉树n个结点的二义树有n+1个空指针域，可以充分利用二义链表存储结构中的那些空指针域，来保存结点在某种遍历序列屮的直接前驱和直接后继的地址信息。指向直接前驱结点或指向直接后继结点的指针称为线索，带冇线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二义树的过程称为线索化。由于二叉树的遍历方法不同，因此线索二叉树的方法也冇多种。其中以中序线索化用得最多。

5、线索二叉树的画法，先写出二叉树的某种遍历的序列，若左孩子为空，则此线索指针将指向前一个遍历次序的结点，右孩子为空，则此线索指针将指向下一个遍历次序的结点，左右不为空时，则不须画。6•恢复二叉树（1）对于已知二叉树的前序和中序序列，可以根据前序序列确定树的根（首结点），根据中序序列确定左子树和右子树。（2）对于已知二叉树的后序和中序序列，可以根据后序序列确定树的根（尾结点），根据中序序列确定左了树和右了树。7.标识符树将算术表达式用二叉树来表示称为标识符树，也称为二叉表示树。利用标识符树的后序遍历可以得到算术表达式的后缀表达式，是二叉树的一种重要应用。8.哈夫曼树及哈夫曼编

6、码（1）路径长度从树屮的一个结点到另一个结点之问的分支构成两个结点间的路径，路径上的分支数日，称作路径长度。（2）结点的带权路径长度从该结点到树根Z间路径长度与该结点上权的乘积。（3）树的带权路径长度树中所有叶子结点的带权路径长度之和，称为树的带权路径长度。（4）哈夫曼树带权路径长度最小的二叉树，称为最优二叉树，也称为哈夫曼树。（5）哈夫曼编码哈夫曼树从根结点到每个叶结点都有一条唯一的路径，规定哈夫曼树中的左分支代表0,右分支代表1,贝U从根结点到每个叶结点所经过的路径分支组成的0和1的序列即为该结点对应的哈夫曼编码。7.2典型习题分析【例1】度为2的树与二叉树有什么区别

7、？答：一棵度为2的树与一棵二义树的区别在于：对于度为1和度为2的树无须区分左右子树，但对于二叉树则必须区分左右子树，且左右子树不能任意交换。【例2】一般树和二叉树有什么区别？答：一般树（非空）除了根结点之外，每个结点有且仅有一个前驱结点，但每个结点都可以有多个直不相交的子集（厉继结点）。二叉树（非空）除了根结点之外，每个结点有且仅有一个前驱结点，但每个结点至多只有两个后继结点，称为左子树和右子树，左、右子树的次序不能交换，FL左右子树又分別都是二叉树。一般树和二叉树主要有以下区别：（1）二叉树结点的度最人为2,而-•般树结点的