软件技术-树与二叉树

第2章常用数据结构及其运算8、树与二叉树一、树的基本概念1、树的定义树（Tree）是n（n≥0）个结点的有限集合。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n

1时，其余结点可分为m（m

0）个互不相交的有限集合T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树（Subtree）。2、树的基本术语结点的度：一个结点拥有的子树数称为该结点的度。叶子结点：度为0的结点称为叶子（Leaf）或终端结点。非终端结点：度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度：树内各结点的度的最大值称为树的度。树中结点之间的关系：在描述结点之间的关系时，通常用家族关系来形象的称呼结点之间的联系。结点的子树的根称为该结点的孩子（Child），相应的，该结点称为孩子的双亲（Parents）或父结点。同一个双亲的孩子之间称为兄弟（Sibling）。结点的层次（Level）：一棵树从根开始定义起，根为第一层，根的孩子为第二层，…，依此类推。若某结点在第i层，则其子树的根就在第i＋1层。其双亲在同一层的结点互为堂兄弟。树的深度（Depth）：树中结点的最大层次称为树的深度或高度。森林（Forest）：m（m≥0）棵互不相交的树的集合称为森林。对树中每个结点而言，其子树的集合即为森林。因为树是一种非线性结构，所以不能简单地用一维数组或单链表来存储树。为了存储树，必须把树中每个结点之间存在的关系反映在存储结构之中，才能如实的表现一棵树。二、树的存储结构1、双亲表示法（顺序存储结构）这种表示法要求用一维数组来存储树的有关信息，每个结点对应一个数组元素，它包含两个域：一个是数据域（data），存放该结点所包含的数据；一个是指针域（parent），指出该结点的双亲结点的位置（整数）。#defineMAX_TREE_SIZE100/*设树中结点总个数为100*/typedef

struct{anytypedata；/*假设anytype为树中结点的数据类型*/

intparent；

}node；nodetree[MAX_TREE_SIZE]；/*用数组tree存放树的信息*/树的双亲表示法的结点类型2、孩子表示法由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点。一种办法是把每个结点的孩子结点排列起来，构成一个单链表，则n个结点有n个孩子链表（叶子的孩子链表为空）。而n个头指针又组成一个线性表，为了查找方便，可采用顺序存储结构。每个结点只要掌握了这个单链表的表头，就容易找到它的全部孩子。在树的孩子表示法中，寻找任意结点的孩子是比较容易的，但寻找它的双亲却比较困难。我们可以将双亲表示法和孩子表示法合在一起。3、孩子兄弟表示法（链式存储结构）这种表示法又称为二叉链表表示法，或二叉树表示法。即以二叉链表作为树的存储结构，链表中每个结点设有两个链域，一个指向该结点的第一个孩子，一个指向该结点的下一个兄弟结点。结点类型定义如下：

structnode{anytypedata；

structnode*firstchild，*nextsibling；

}；三、二叉树1．二叉树的基本概念

二叉树（Binarytree）是另一种树型结构，或是空集或是由互不相交的子集构成。它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树有五种基本形态：2．二叉树的基本性质

(1)性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。(2)性质2：深度为k的二叉树至多有2k－1个结点(k≥1)。(3)性质3:对任何一棵二叉树T，设n0，n2分别是叶结点个数和度为2的结点个数，则：n0＝n2＋1。一棵深度为k且有2k－1个结点的二叉树称为满二叉树。深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。(4)性质4:

具有n个结点的完全二叉树的深度为

log2n

＋1。3、几种特殊的二叉树满二叉树：深度为K，且存在2K-1个结点的二叉树。完全二叉树：至多只有最下面两层上的结点度数可以小于2，并且最下层结点都集中在该层最左边的位置。平衡二叉树：或是一棵空树，或是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。例：二叉树结点计算

教材P104习题2.294、

二叉树的存储结构顺序存储结构：用一组连续的存储单元存储二叉树的数据元素，可用一维数组（bt）实现，即将完全二叉树上编号为i的结点元素存储在一维数组下标为i的元素中（bt[i]）。数组定义如下：

anytype

bt[MAX_TREE_SIZE+1];对一般二叉树，为了体现结点之间的关系，也必须按完全二叉树的形式来存储。由此可见，这种顺序存储结构比较适用于完全二叉树或满二叉树的存储，对于一般二叉树会成存储空间的浪费。因为，在最坏的情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）需要一维数组的长度为2k－1。链式存储结构对于一般二叉树，根据它的定义，最适合于使用一种二叉链表结构（非线性链表）来存储它。在这种链表中，每个结点至少包含三个域，即：数据域和左、右指针域，分别用data，lchild和rchild表示。其中数据域存放该结点所包含的数据，左、右指针域分别指向该结点的左孩子和右孩子，当孩子结点不存在时，相应的指针域为空。有时为了便于找到结点的双亲，可再设一个指向该结点双亲的指针域parent，这就变为三叉链表了5、二叉树的遍历所谓遍历二叉树（TraversingBinaryTree）就是指按一定的规则和次序访问树中的每个结点，使每个结点被访问且仅只被访问一次。1）二叉树的中序遍历（LDR）若二叉树为空，则返回。否则：（1）中根遍历左子树；（2）访问根结点；（3）中根遍历右子树；（4）返回。2)

二叉树的先序遍历(DLR)先根遍历二叉树的操作可定义为：若二叉树为空，则返回。否则（１）访问根结点；（２）先根遍历左子树；（３）先根遍历右子树；（４）返回。其递归算法如下：

voidpreorder(t)

structnode*t；

{if(t！＝NULL){visite(t－>data)；

preorder(t－>lchild)；

preorder(t－>rchild);}}3)

二叉树的后序遍历(LRD)与前面两种遍历方法一样，后根遍历的算法也可归纳为四个步骤，如下描述：若二叉树为空，则返回。否则：（1）按后根次序遍历左子树；（2）按后根次序遍历右子树；（3）访问根结点；（4）返回。根据以上的递归定义，我们有如下的递归算法：voidpostorder(t)structnode*t；{ift！＝NULL{postorder(t－>lchild)；

postorder(t－>rchild)；

visite(tT－>data)；

}}例：二叉树的遍历

P104习题2.30四、二叉排序树的应用1、二叉排序树的定义二叉排序树（也称二叉查找树）是二叉树的一个重要应用。二叉排序树（或二叉排序树）是利用二叉树的结构特点和结点关键值有规则的出现来实现排序，还可以有效地解决动态变化时的查找问题。二叉排序树或者是一棵空树，或者是具有以下性质的二叉树：（1）若根结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若根结点的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；（3）根结点的左、右子树也分别为二叉排序树。2、二叉排序树的建立

当给出一组无序的数据序列后，依次输入每一个元素，按二叉排序树所要求的结点规律，将所给数据逐个插入到二叉排序树中。其构造过程是：每输入一个元素，就建立一个新结点，然后按下列原则把结点插入到已建立的二叉排序树中去；若二叉排序树是空树，则该结点成为二叉排序树的根结点；若二叉排序树非空，则将新结点中的关键值与根结点比较，若小于根结点的值，则插入到左子树中；否则插入到右子树中去。每次插入一个结点的递归算法structnode{anytypedata;

structnode*lchild;

structnode*rchild;}*root;voidinsnode(t,d)

structnode*t;

anytyped;

/*在以t为根结点的二叉查找数中插入关键字为d的结点*/{structnode*r,*p;r=(structnode*)malloc(sizeof(structnode));if(r==NULL) {printf("outofmemory\n");exit(0);}else{r->data=d; r->lchild=NULL; r->rchild=NULL;}if(t==NULL)root=r;elsewhile(t!=NULL) if(d<t->data) if(t->lchild==NULL) {t->lchild=r;t=NULL;} elset=t->lchild; else if(t->rchild==NULL) {t->rchild=r;t=NULL;} elset=t->rchild;}

voidcreat(){inti,n,d;root=NULL;printf("\ninputn\n");

scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&d);

insnode(root,d);}}3、在二叉排序树上删除结点（1）若*p结点为叶子结点，即PL­和PR均为空树。由于删去叶子结点不会破坏整棵树的结构，则只需修改其双亲结点的指针即可。（2）若*p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可。显然，作此修改也不会破坏二叉排序树的特性。（3）若*p结点的左子树和右子树均不为空。五、哈夫曼树的应用1、什么是哈夫曼树假设有n个权值{w1，w2，…，wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权wi，则其中带权路径长度WPL最小的二叉树称作最优二叉树或哈夫曼树。2、哈夫曼树的构造根据n个权值{w1，w2，…，wn}构造哈夫曼树的过程如下：(1)根据给定的n个权值{w1，w2，…，wn}构造n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空；(2)在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子