文档介绍：第7章树和二叉树
树
二叉树
以结点类为基础的二叉树设计
二叉树类
二叉树的分步遍历
线索二叉树
霍夫曼树
树的遍历
本章主要知识点:
树的定义、表示方法和存储结构
二叉树的定义、性质和存储结构,满二叉树和完全二叉树的概念
二叉树的前序、中序、后序和层序遍历算法
二叉树中序和层序游标类的设计方法
线索二叉树的基本概念
哈夫曼树和哈夫曼编码,哈夫曼编码的软件设计方法
树与二叉树的转换,树的遍历
树
树的定义
树是由n(n≥0)个结点构成的满足以下条件的结点集合:
(1)当n>0时,有一个特殊的结点称为根结点,根结点没有前驱结点;
(2)当n>1时,除根结点外的其他结点被分成m(m>0)个互不相交的集合T1, T2,…, Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵结构和树结构类同的子树。
树的示例:
只有根结点的树
一般的树
结点:结点由数据元素和构造数据元素之间关系的指针组成。
结点的度:结点所拥有的子树的个数称为该结点的度。
叶结点:度为0的结点称为叶结点,叶结点也称作终端结点。
分支结点:度不为0的结点称为分支结点,分支结点也称作非终端结点。
孩子结点:树中一个结点的子树的根结点称作这个结点的孩子结点。孩子结点也称为直接后继结点。
双亲结点:若树中某结点有孩子结点,则这个结点就称作它的孩子结点的双亲结点。双亲结点也称为直接前驱结点。
兄弟结点:具有相同的双亲结点的结点称为兄弟结点。
树的度:树中所有结点的度的最大值称为该树的度。
结点的层次:从根结点到树中某结点所经路径上的分支数。根结点的层次规定为0,这样其他结点的层次就是他的双亲结点的层次加1.
树的深度:树中所有结点的层次的最大值称为该树的深度。
无序树:树中任意一个结点的各孩子结点的排列没有严格次序的树称为无序树。从前面树的定义可知,树是无序树。
有序树:树中任意一个结点的各孩子结点的排列有严格次序的树称为有序树。后面讨论的二叉树是一种有序树。
森林:m(m≥0)棵树的集合称为森林。一棵树由根结点和m个子树组成,若把树中的根结点删除,则树就变成了包含m棵树的森林。当然,一棵树也可以称为森林。
树的表示方法
1 直观表示法
2 形式化表示法
树的形式化表示法主要用于树的理论描述。树的形式化表示法定义树T为T=(D,R)其中D为树T中结点的集合,R为树T中结点之间关系的集合。当树T为空树时D=￠;当树T不为空树时有D={Root}∪DF,其中Root为树T的根结点,DF为树T的根Root的子树集合,DF可由下式表示:
DF = D1∪D2∪…∪Dm (1≤i,j≤m, Di∩Dj=￠)
3 凹入表示法
直观表示法B图的凹入表示:
树的凹入表示法(或称缩进表示法)是一种结点逐层缩进的表示方法。树的凹入表示法还可以分为横向凹入表示和竖向凹入表示。
树的横向凹入表示