课程：树和二叉树

《课程：树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学要求：掌握树的定义及基本术语，掌握二叉树的定义、性质和存储结构，熟练掌握二叉树的遍历方法及其实现和线索二叉树的构造，掌握树，森林和二叉树之间相互转换的方法，掌握哈夫曼树的定义和哈夫曼算法，了解哈夫曼编码的方法。教学重点与难点：二叉树的存储结构，二叉树的遍历及线索二叉树的构造，树、森林和二叉树之间的相互转换，哈夫曼树的定义和哈夫曼算法。16.1树的定义与基本术语6.2二叉树6.3二叉树的遍历与线索化6.4树、森林和二叉树的关系6.5哈夫曼树及其应用6.6总结与提高第六章树和二叉树26.1树的定义与基本术语1．树的基本概念2．树的图解表示法3．树的相关术语4．树的抽象数据类型36.1树的定义与

2、基本术语树定义：是n（n≥0）个结点的有限集合T。当n=0时，称为空树；当n>0时，该集合满足如下条件：(1)其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。(2)其余n-1个结点可以划分成m（m≥0）个互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，称为根root的子树。每棵子树的根结点有且仅有一个直接前驱，可有零个或多个直接后继。1．树的基本概念4例如：一棵树的逻辑结构图（6.1）为：ABCDGFEHIJKLM从图中可以看出它好象一棵倒栽的树。52．树的图解表示法1）倒置树结构（树形表示法）2）文氏图表示法（嵌套集合形式）图6.23）广义表

3、形式（嵌套扩号表示法）4）凹入表示法图6.3图6.2文氏图表示法ABCDABCD(A(B(D),C))广义表表示法63.树的相关术语：结点：包含一个数据元素及若干指向其它结点的分支信息。结点的度：一个结点的子树个数称为此结点的度。叶结点：度为0的结点，即无后继的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。结点的层次编号：将树中的结点按从上层到下层、同层从左到右的次序排成一个线性序列，依次给它们编以连续的自然数。7树的度：树中所有结点的度的最大值。树的高度（深度）：树中所有结点的层次的最大值。

4、有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。森林：m（m≥0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。同构：对两棵树，通过对结点适当地重命名，就可以使两棵树完全相等（结点对应相等，对应结点的相关关系也像等），则称这两棵树同构。8双亲结点：一个结点的直接前驱称为该结点的双亲结点。上图中A是B、C的双亲。兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。上图中的结点H、I、J互为兄弟结点。孩子结点：一个结点的直接后继称为该结点的孩子结点。如上图的B、C是A的孩子。我们常常借助人类家族树的术语，以便于

5、直观理解结点间的层次关系。堂兄弟：父亲是兄弟关系或堂兄关系的结点称为堂兄弟结点。在图6.1中，结点E、G、H互为堂兄弟。9祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。如结点K的祖先结点是A、B、E。子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点。如结点D的子孙是H、I、J、M。前辈：层号比该结点小的结点，都称为该结点的前辈。后辈：层号比该结点大的结点，都称为该结点的后辈。10ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C

6、，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先11任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林森林(forest)：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF124.树的抽象数据类型数据对象D：一个集合，该集合中的所有元素具有相同的特性。数据关系R：若D为空集，则为空树。若D中仅含有一个数据元素，则R为空集，否则R={H}，H是如下的二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下没有前驱。(2)除root以外，D中每个

7、结点在关系H下都有且仅有一个前驱。13基本操作：(1)InitTree（Tree）：将Tree初始化为一棵空树。(2)DestoryTree（Tree）：销毁树Tree。(3)CreateTree（Tree）：创建树Tree。(4)TreeEmpty（Tree）：若Tree为空，则返回TRUE，否则返回FALSE。(5)Root（Tree）：返回树Tree的根。14(6)Parent（Tree，x