数据结构（c语言描述） 教学课件 作者 库波 第6章 树.ppt

《数据结构（c语言描述） 教学课件 作者 库波 第6章 树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（C#）主编：库波第6章树6.1树的结构定义与基本操作6.2二叉树6.3遍历二叉树6.4哈夫曼树6.1树的结构定义与基本操作树的定义及相关术语1．树的定义树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0时，称这棵树为空树。在一棵非树T中：（1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。（2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。2相关术语在二叉树中介绍的有关概念在树中仍然适用。除此

2、之外，再介绍两个关于树的术语。（1）有序树和无序树。如果一棵树中结点的各子树丛左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。（2）森林。零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林。树的表示1．直观表示法2．嵌套集合表示法3．凹入表示法4．广义表表示法树的基本操作树的基本操作通常有以下10种：1、Root()：求树的根结点，如果树非空，返回根结点，否则返回空；2、Parent(t)：求结点t的双亲结点

3、。如果t的双亲结点存在，返回双亲结点，否则返回空；3、Child(t,i)：求结点t的第i个子结点。如果存在，返回第i个子结点，否则返回空；4、RightSibling(t)：求结点t第一个右边兄弟结点。如果存在，返回第一个右边兄弟结点，否则返回空；5、Insert(s,t,i)：把树s插入到树中作为结点t的第i棵子树。成功返回true，否则返回false；6、Delete(t,i)：删除结点t的第i棵子树。成功返回第i棵子树的根结点，否则返回空；7、Traverse(TraverseType)：按某种方式遍历树；8、Clear()：清空树；9、IsEmp

4、ty()：判断树是否为空树。如果是空树，返回true，否则返回false；10、GetDepth()：求树的深度。如果树不为空，返回树的层次，否则返回0。6.2二叉树二叉树的定义二叉树（BinaryTree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。二叉树的性质性质1一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。性质2一棵深度为k的二叉树中，最多具有2k－1个结点。性质3对于一棵非空的二叉树，如

5、果叶子结点数为n0，度数为2的结点数为n2，则有:n0＝n2＋1。性质4具有n个结点的完全二叉树的深度k为[log2n]+1。性质5对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：（1）如果i>1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i＝1，则序号为i的结点是根结点，无双亲结点。（2）如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i的结点无左孩子。（3）如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1

6、；如果2i＋1>n，则序号为i的结点无右孩子。二叉树的存储结构1．顺序存储结构2．链式存储结构（1）二叉链表存储（2）三叉链表存储6.3遍历二叉树1、先序遍历先序遍历的递归过程为：若二叉树为空，遍历结束。否则，访问根结点；先序遍历根结点的左子树；先序遍历根结点的右子树。2、中序遍历中序遍历的递归过程为：若二叉树为空，遍历结束。否则，（1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。3、后序遍历后序遍历的递归过程为：若二叉树为空，遍历结束。否则，（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树。（3）访问根结点；4、层次

7、遍历所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。层序遍历的基本思想是：由于层序遍历结点的顺序是先遇到的结点先访问，与队列操作的顺序相同。所以，在进行层序遍历时，设置一个队列,将根结点引用入队，当队列非空时，循环执行以下三步：（1）从队列中取出一个结点引用，并访问该结点；（2）若该结点的左子树非空，将该结点的左子树引用入队；（3）若该结点的右子树非空，将该结点的右子树引用入队；6.4哈夫曼树哈夫曼树的的定义最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点

8、，构造的具有最小带权路径长度的二叉树。构造哈夫曼树——哈夫曼算法结