软件技术--树与二叉树.ppt

第2章常用数据结构及其运算8、树与二叉树一、树的基本概念1、树的定义树（Tree）是n（n≥0）个结点的有限集合。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n?1时，其余结点可分为m（m?0）个互不相交的有限集合T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树（Subtree）。树的深度（Depth）：树中结点的最大层次称为树的深度或高度。森林（Forest）：m（m≥0）棵互不相交的树的集合称为森林。对树中每个结点而言，其子树的集合即为森林。3、几种特殊的二叉树满二叉树：深度为K，且存在2K-1个结点的二叉树。完全二叉树：至多只有最下面两层上的结点度数可以小于2，并且最下层结点都集中在该层最左边的位置。平衡二叉树：或是一棵空树，或是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。例：二叉树结点计算教材P104习题2.29例：二叉树的遍历P104习题2.30四、二叉排序树的应用1、二叉排序树的定义2、二叉排序树的建立3、在二叉排序树上删除结点（1）若*p结点为叶子结点，即PL-和PR均为空树。由于删去叶子结点不会破坏整棵树的结构，则只需修改其双亲结点的指针即可。（2）若*p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可。显然，作此修改也不会破坏二叉排序树的特性。（3）若*p结点的左子树和右子树均不为空。五、哈夫曼树的应用1、什么是哈夫曼树2、哈夫曼树的构造3、哈夫曼编码**2、树的基本术语结点的度：一个结点拥有的子树数称为该结点的度。叶子结点：度为0的结点称为叶子（Leaf）或终端结点。非终端结点：度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度：树内各结点的度的最大值称为树的度。树中结点之间的关系：在描述结点之间的关系时，通常用家族关系来形象的称呼结点之间的联系。结点的子树的根称为该结点的孩子（Child），相应的，该结点称为孩子的双亲（Parents）或父结点。同一个双亲的孩子之间称为兄弟（Sibling）。结点的层次（Level）：一棵树从根开始定义起，根为第一层，根的孩子为第二层，…，依此类推。若某结点在第i层，则其子树的根就在第i＋1层。其双亲在同一层的结点互为堂兄弟。因为树是一种非线性结构，所以不能简单地用一维数组或单链表来存储树。为了存储树，必须把树中每个结点之间存在的关系反映在存储结构之中，才能如实的表现一棵树。二、树的存储结构1、双亲表示法（顺序存储结构）这种表示法要求用一维数组来存储树的有关信息，每个结点对应一个数组元素，它包含两个域：一个是数据域（data），存放该结点所包含的数据；一个是指针域（parent），指出该结点的双亲结点的位置（整数）。#defineMAX_TREE_SIZE100/*设树中结点总个数为100*/typedefstruct{anytypedata；/*假设anytype为树中结点的数据类型*/intparent；}node；nodetree[MAX_TREE_SIZE]；/*用数组tree存放树的信息*/树的双亲表示法的结点类型2、孩子表示法由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点。一种办法是把每个结点的孩子结点排列起来，构成一个单链表，则n个结点有n个孩子链表（叶子的孩子链表为空）。而n个头指针又组成一个线性表，为了查找方便，可采用顺序存储结构。每个结点只要掌握了这个单链表的表头，就容易找到它的全部孩子。在树的孩子表示法中，寻找任意结点的孩子是比较容易的，但寻找它的双亲却比较困难。我们可以将双亲表示法和孩子表示法合在一起。3、孩子兄弟表示法（链式存储结构）这种表示法又称为二叉链表表示法，或二叉树表示法。即以二叉链表作为树的存储结构，链表中每个结点设有两个链域，一个指向该结点的第一个孩子，一个指向该结点的下一个兄弟结点。结点类型定义如下：structnode{anytypedata；structnode*firstchild，*nextsibling；