数据结构与算法（c语言版）第2版下ppt

《数据结构与算法（c语言版）第2版下ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法（C语言版）第2版下作者：郭龙源、胡虚怀、何光明、戴仕明第6章树和二叉树本章主要内容6.1树的定义与基本操作6.2二叉树6.3树和森林6.4哈夫曼树与哈夫曼编码6.1树的定义与基本操作6.1.1树的定义与相关术语6.1.2树的抽象数据类型6.1.1树的定义与相关术语树的定义可以有很多种方式，其中最自然的方式是递归定义。树(tree)T是n(n≥0)个点的有限集合，任何一个非空树都满足以下两个条件。(1)有且只有一个特定的称为根(root)的结点。(2)其余结点可分为m(m>0)个互不相交的有限集合T1,T2,…,Tm，其中每个

2、集合本身又是一个树，并称为树的子树(subtree)。下面给出树结构中的一些基本术语。度(degree)：一个树结点中的子树个数称为该结点的度。叶子(leaf)：一棵树中，度为零的结点称为叶子。叶子结点有时又称为终端结点。分支结点：与叶子结点相对应，分支结点是树中度为零的结点。分支结点有时又称为非终端结点。孩子(child)：树中某个结点的子树的根称为该结点的孩子。双亲(parents)：与孩子结点相对应。如果一个结点拥有孩子结点，则这个结点就称为孩子结点的双亲。双亲结点有时又称为父亲。兄弟(brother)：同一个双亲的孩子称为兄弟。路径

3、(path)：若树中存在一个结点序列k1,k2,…,ki，使得ki是ki+1的双亲(1≤i

4、depth)。堂兄弟：如果两个结点的双亲在同一层，则称这两个结点互为堂兄弟。有序树(orderedtree)：若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树。无序树(unorderedTree)：若树中每个结点的各子树是可以互换的，则称该树为无序树。森林(forest)：森林是m(m≥0)棵互不相交的树的集合。树的逻辑特征可以进行以下描述。(1)树中任一结点都可以有零个或多个直接后继(即孩子)结点，但至多只能有一个直接前趋结点，即双亲结点。(2)树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点

5、。(3)祖先与子孙的关系是父子关系的延伸，它定义了树中各结点之间的纵向次序。(4)在有序树中，同一组兄弟结点从左到右有长幼之分。它定义了树中各结点之间的横向次序。6.1.2树的抽象数据类型树的抽象数据类型定义如下：ADTTree{数据对象：D是具有相同性质的数据元素的集合。数据关系：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下的二元关系。(1)在D中存在唯一的称为根的数据元素root，它在关系H中无前驱。(2)在D-{root}≠，则存在D-{root}的一个划分D1,D2,…,Dm(m>0)，对任意

6、j≠k，(1≤j,k≤m)有Di∩Dj=，且对任意的i(1≤i≤m)，存在唯一的数据元素xi∈Di，∈H。(3)对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1，H2，…，Hm(m>0)，对任意i(1≤i≤m)，Hi是Di上的二元关系，(Di，{H})是一棵符合本定义的树，称为根root的子树。6.2二叉树6.2.1二叉树的定义与基本操作6.2.2二叉树的性质6.2.3二叉树的存储结构6.2.4二叉树的遍历6.2.5线索化二叉树6.2.1二叉树的定义与基本操作二叉树(bi

7、narytree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。二叉树存在两种特殊的情形：满二叉树和完全二叉树。如果一棵树树根的深度为1，则深度为k且有2k-1个结点的二叉树称为满二叉树。一棵满二叉树具有下面的两个特征。(1)每一层上的结点数都达到最大值。即对给定的高度，满二叉树是所有二叉树中结点最多的二叉树。(2)满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且叶子结点都在最下一层。若一棵二叉树至多只有最下面的两层上结点的度数可以小

8、于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。满二叉树具有下面的3个特征。(1)满二叉树是完全二叉树，完全二叉树不一定是满二叉树。(2)在满