数据结构3(树形结构)

2.树形结构伍之昂江苏省电子商务重点实验室南京财经大学Email:

zawuster@第一部分：数据结构树的基本概念（1）树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个节点有零个或多个子节点；每一个子节点只有一个父节点；没有前驱的节点为根节点；除了根节点外，每个子节点可以分为m个不相交的子树。例子：家谱

树的基本概念（2）节点的度：一个节点含有的子树的个数称为该节点的度；树的度：一棵树中，最大的节点度称为树的度；叶节点或终端节点：度为零的节点称为叶节点；双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；兄弟节点：具有相同父节点的节点互称为兄弟节点；树的基本概念（3）节点的层次：从根开始定义起，根为第0层，

根的子节点为第1层，以此类推；树的高度：二叉树中层数最大的叶节点的层数加1；树的深度：二叉树中层数最大的叶节点的层数；只有一个根节点的二叉树的高度为1，深度为0。提醒：《数据结构》课程中树和图结构中的顶点称为“节点”；

而《计算机网络》课程中的点称为“结点”，希望同学们不要写错别字！提纲二叉树哈夫曼树堆二叉树二叉树由节点的有限集合构成:或者为空集或者由一个根节点及两棵不相交的、分别称作这个根的左子树和右子树的二叉树(它们也是节点的集合)组成这是个递归的定义。二叉树可以是空集合，因此根可以有空的左子树或右子树，或者左右子树皆为空。注：在二叉树中必须指明儿子节点是“左后继”还是“右后继”，即便该节点只有一个后继。二叉树的五种基本形态

(a)空

(b)独根(c)空右(d)空左(e)左右都不空二叉树的特性在二叉树的第i层上至多有2i个节点(i≥0,根为0层)。深度为k的二叉树中至多含有2k+1-1个节点(k≥0)。用数学归纳法不难证明。

任何二叉树，度为0的节点比度为2的节点多一个证明：设有n个节点的二叉树的度为0、1、2的节点数

分别为=n0，n1，n2，则

n=n0+n1+n2

设边数为e。因为除根以外，每个节点都有一条边进入，故 n=e+1。由于这些边是有度为1和2的的节点射出的，

因此e=n1+2·n2，于是

n=e+1=n1+2·n2+1

因此由公式（1）（2）得n0+n1+n2=n1+2·n2+1

即

n0=n2+1

满二叉树满二叉树：若二叉树中所有的分支节点的度数都为2，且叶子节点都在同一层次上。中国定义，我们以此为准。隐含意思：每层都放满。美国国家标准与技术研究院给出的定义是：如果一颗二叉树上任何节点，或者是树叶，或者恰有两颗非空子树，此二叉树就为满二叉树。国际上却参照此定义。隐含意思：不存在仅含一颗子树的节点。两种满二叉树定义的区别01234567891011121314012345611121314中国定义，课程采用的满二叉树美国及国际定义完全二叉树完全二叉树：假如一棵包含n个节点的二叉树中每个节点都可以和满二叉树中编号为0至n-1的节点一一对应。 一棵深度为h的完全二叉树中，前h-1层中的节点都是“满”的，且第h层的节点都集中在左边。满二叉树本身也是完全二叉树。显然是按照中国定义的满二叉树。0123456789完全二叉树的特性有n(n>0)个节点的完全二叉树的深度为

log2(n+1)-1，高度为log2(n+1)证明：设该二叉树深度为d，该树最多有2d+1-1个节点，我们有：

2d-1<n≤2d+1-1,即：2d<n+1≤2d+1

两边取对数，有：d<log2(n+1)≤d+1,

该不等式表明：若log2(n+1)为整数，log2(n+1)=d+1；

若log2(n+1)不为整数，那么，log2(n+1)>1，

因此，d=log2(n+1)-1，

其中，log2(n+1)

表示向上取整（如：1.5=2）。

显然，高度h=d+1=log2(n+1)

.证毕。完全二叉树编号的规律有n个节点的二叉树，根节点标为0，即：0≤i≤n-1，对编号为i的节点，我们有：若：i=0，则该节点为根节点；若：节点i有左后继，那么，该左后继节点编号为2i+1；若：节点i有右后继，那么，该右后继节点编号为2i+2；若：节点i有父节点，那么，该父节点编号为i/2-1；不做理论证明，请通过右下角图验证。0123456789上述推导的本质是等比数列通项和求和，很多试题都围绕这些内容展开。很多教材从1开始编号，即：根的层次为1，根节点编号为1，上述特性和规律将发生细微变化。请同学们课后仔细推导！二叉树的存储结构顺序存储结构链式存储结构二叉树的存储结构：顺序存储结构用一组地址连续的存储单元存储二叉树中的数据元素，这种方法仅适用于完全二叉树。根节点放到SqBiTree[0]，按照左后继、右后继依次存储；定位按照前面所述编号规律来进行，方便快捷；如果该树不是完全二叉树，将浪费存储空间。const

MAXSIZE=100;

//暂定二叉树中节点数的最大值为100

typedefstruct

{

ElemType*data;

//存储空间基址(初始化时分配空间)

int

nodeNum;

//二叉树中节点数

}SqBiTree;

//二叉树的顺序存储结构

二叉树的存储结构：链式存储结构（1）typedefstructBiTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指针

}*BiTree;

dataRchildLchild二叉树的存储结构：链式存储结构（2）上面链式结构只能从根向下找，无法直接获得节点的父节点我们当然能够增加1个指向父节点的指针。typedefstructTriTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指针

struct

BiTNode*parent;

//双亲指针

}*TriTree;

二叉树的遍历遍历(周游)：系统地访问数据结构中的节点。每个节点都正好被访问到一次。“正好”的含义：当且仅当(ifandonlyif)遍历一棵二叉树的过程实际上就是把二叉树的节点放入一个线性序列的过程，或者说把二叉树进行线性化。树的遍历、图的遍历，是数据结构中最重要的议题。三种遍历策略先序遍历中序遍历后序遍历同样重要，各有用处，有关树的90%的试题都是围绕三种遍历展开。递归定义二叉树是由“根节点”、“左子树”和“右子树”三部分构成，则遍历二叉树的操作可分解为“访问根节点”、“遍历左子树”和“遍历右子树”三个子操作。因此，不难得到三种遍历的递归定义：先序遍历：访问根节点；先序遍历左子树；先序遍历右子树；中序遍历：中序遍历左子树；访问根节点；中序遍历右子树；后序遍历：后序遍历左子树；后序遍历右子树；访问根节点。三种遍历的例子先序遍历：ABDCEGFHI中序遍历：DBAEGCHFI后序遍历：DBGEHIFCA题型：给定两个遍历序列，求树或第三个遍历序列已知7个节点的二叉树的先根遍历是1245637（数字为节点的编号，以下同），后根遍历是4652731，画出这棵树(或问，该树的中序遍历结果是什么？)启示：给定任意两种遍历序列，唯一确定这棵树。先序遍历：递归伪代码template<classT>voidBinaryTree<T>::PreOrder(BinaryTreeNode<T>*root)｛ if(root!=NULL){ Visit(root); //访问根节点

PreOrder(root->leftchild());//访问左子树

PreOrder(root->rightchild());//访问右子树

}｝

注：Visit(root)是个抽象操作，实际上，“访问”可以在该节点上做任何操作。中序遍历：递归伪代码template<classT>voidBinaryTree<T>::PreOrder(BinaryTreeNode<T>*root)｛ if(root!=NULL){

PreOrder(root->leftchild());//访问左子树Visit(root); //访问根节点

PreOrder(root->rightchild());//访问右子树

}｝

后序遍历：递归伪代码template<classT>voidBinaryTree<T>::PreOrder(BinaryTreeNode<T>*root)｛ if(root!=NULL){

PreOrder(root->leftchild());//访问左子树

PreOrder(root->rightchild());//访问右子树Visit(root); //访问根节点

}｝

树遍历的非递归实现递归实现树遍历固然一目了然，但是，很多应用问题难以用递归方法来解决；非递归实现树遍历便于我们更精细的控制遍历过程，灵活实现很多看似复杂的应用问题。栈是实现递归最常用的结构，非递归实现需要用到栈。非递归实现：先序遍历思想遇到一个节点，就访问该节点，并把此节点推入栈中，然后下降去遍历它的左子树；遍历完它的左子树后，从栈顶托出这个节点，并按照它的右链接指示的地址再去周游该节点的右子树结构。非递归实现：先序遍历伪代码注意：先将右子树推进栈非递归实现：中序遍历思想遇到一个节点，就把它推入栈中，并去遍历它的左子树；注意：此时不访问遍历完左子树后，从栈顶托出这个节点并访问之，然后按照它的右链接指示的地址再去遍历该节点的右子树。节点扩展标记位在二叉树node结构里增加1个标记位tag记录该节点状态，初始时：tag=0。tag=0，表示左子树未访问；tag=1，表示左子树已经访问，该访问自己了。dataRchildLchildtagtypedefstructBiTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指针

int

tag=0;

}*BiTree;

非递归实现：中序遍历伪代码非递归实现：后序遍历思想遇到一个节点，把它推入栈中，遍历它的左子树；遍历结束后，还不能马上访问处于栈顶的该节点，而是要再按照它的右链接结构指示的地址去遍历该节点的右子树；遍历遍右子树后才能从栈顶托出该节点并访问之。tag语义略微发生变化tag=0，表示左右子树均未访问；tag=1，表示左子树已经访问，该访问右子树了；tag=2，表示左右子树均已经访问，该访问自己了。非递归实现：后序遍历伪代码树遍历非递归算法总结非递归算法的写法有很多种，我们只是用统一的框架来描述了这三种遍历进栈出栈操作，出栈过程，我们根据需要设置标记位来表明该节点的左(或右)子树是否被遍历。希望同学们理解并熟记该框架，很多应用问题只需要改变Visit(p)操作就可以实现。二叉树遍历应用举例(1)统计二叉树中叶子节点的数量

容易想到，实现这个操作只要对二叉树"遍历"一遍，并在遍历过程中对"叶子节点计数"即可。显然这个遍历的次序可以随意，即先序或中序或后序均可，只是为了在遍历的同时进行计数，需要在算法的参数中设一个"计数器"。统计二叉树中非叶子节点的数量void

CountLeaf(BiTreeT,int&count)

{

//先序遍历二叉树，以count返回二叉树中叶子节点的数目

if

(T){

if((!T->Lchild)&&(!T->Rchild))

count++;

//对叶子节点计数

CountLeaf(T->Lchild,count);

CountLeaf(T->Rchild,count);

}//if

}//CountLeaf

二叉树遍历应用举例(2)求二叉树的深度和高度任何遍历均可，每下去一层，深度加1，但是，注意，将当前最大深度保存下来。intmaxdepth=-1;//当前最大深度void

BiTreeDepth(BiTreeT,intdepth)

{

//

T指向二叉树的根，depth为T所指节点所在层次，初值为0

if

(T){

if

(depth>maxdepth)maxdepth=depth;

BiTreeDepth(T->Lchild,depth+1);

BiTreeDepth(T->Rchild,depth+1);

}//if

}//BiTreeDepth

//全局变量maxdepth最终保存的就是树的深度二叉树遍历应用举例(3)-1输出二叉树中每一棵树中从根到所有叶子节点的路径从树的根节点出发，沿着各个分支可以到达所有叶子节点，由途径所有节点构成的节点序列称为从根到叶的路径，途径分支个数称作路径长度；用递归算法就很难实现了，因为，递归算法不保存中间状态。输出路径：ADFADGK二叉树遍历应用举例(3)-2回忆后序遍历的非递归算法当Visit(p)时，p的节点的所有祖先一定都在栈中，因为，后序决定子节点在父节点之前被访问，因此，p被访问时，他的所有父节点都未被访问，因此，必然在栈中。据此，我们很容易修改Visit(p)函数解决这一问题：判断p是否为叶节点，即p->Lchild==NULL&&p-Rchild==NULL，若是，反序打印栈中所有节点，即为根到p的路径。留为作业，请同学们至少写出伪代码，最好上机验证。广度优先遍历二叉树上述三种遍历本质上是深度优先遍历。广度优先遍历：从二叉树的第一层（根节点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对节点逐一访问。例如：ABCDEFGHI广度优先遍历实现方式广度优先遍历没有递归实现方法，非递归实现依赖于队列下一章，图的广度遍历也是如此！广度优先遍历二叉树：伪代码与先序遍历非递归代码比较，区别有哪些？提纲二叉树哈夫曼树堆Huffman树(哈夫曼树)最优树，又称哈夫曼树（HuffmanTree）是一类带权路径长度最短的树，本节仅限于讨论最优二叉树。 路径：从树的根节点到叶节点的分支构成一条路径。路径长度：路径上的分支数目称路径长度，计算方法为：根节点为0，路径上遇到1个节点路径长度增加1，直到叶节点为止。现在，假设每个叶子节点上带有权值为wk(k=1,2,…,n)，则树的带权路径长度定义为树中所有叶子节点的带权路径长度之和，通常记作

其中：lk为根节点到也节点k的路径长度。例子例如，右图中的四棵二叉树，都有5个叶子节点且带相同权值5、6、2、9、7，它们的带权路径长度分别为 WPL=7*3+9*3+5*2+6*

2+2*2=74(左上图)

WPL=2*1+6*3+7*4+9*4+5*2=94(右上图)

WPL=6*2+7*2+5*3+2*3+9*2=65(左下图)

WPL=2*1+5*3+7*3+9*3+6*3=83(右下图) 最优树构造方法哈夫曼最早给出了一个构造最优树的带有一般规律的算法，故称哈夫曼树。首先，按照“权”(例如频率)将字母排为一列。接着，拿走前两个字母(“权”最小的两个字母)，再将它们标记为Huffman树的树叶，将这两个树叶标为一个分支节点的两个子女，而该节点的权即为两树叶的权之和。将所得“权”放回序列中适当位置，使“权”的顺序保持。重复上述步骤直至序列中只剩一个元素，则Huffman树建立完毕。以上页例子5个节点5、6、2、9、7为例。哈夫曼树应用：前缀编码一个编码集合中，任何一个字符的编码都不是另外一个字符编码的前缀，这种编码叫作前缀编码Why?前缀编码是不等长编码，与等长编码相比，可以使传送电文的字符串的总长度尽可能地短。例如：8个字符组成的字符串“AABACCDA”，如果我们用2位二进制码等长编码，用16位二进制就可以表示这个字符串。若按频率：A:4,C:2,B:1,D:1，构造哈夫曼树，并规定左分支表示字符‘0’，右分支表示字符‘1’，得到编码：A:0,C:11,B:100,D:101，用14位二进制码就可以表示这个字符串。其成功的本质在于：频率高的字符的编码尽量短。这种前缀特性保证了代码串被反编码时，不会有多种可能。A:4,C:2,B:1,D:1的哈夫曼树ACBD010011011100101提纲二叉树哈夫曼树堆堆最小值堆：最小值堆是一个关键码序列

{K0，K1，…Kn-1}，它具有如下特性：Ki≤K2i+1(i=0，1，…，

n/2-1)Ki≤K2i+2类似可以定义最大值堆。堆的性质堆实际上是一个完全二叉树的层次序列，可以用数组表示堆中储存的数是局部有序的节点储存的值与其子女储存的值之间存在某种联系。有两种不同的堆，决定于其关于联系的定义堆中任何一个节点与其兄弟之间都没有必然的联系堆不唯一。从逻辑角度看，堆实际上是一种树型结构建堆过程堆本质上是二叉树，顺序存储；将全部元素全部插入二叉树中，然后从最后一个分支节点逐个向上“调整”假设根的左、右子树都已是堆，并且根的元素名为R。这种情况下，有两种可能：(1)R的值小于或等于其两个子女，此时堆已完成；(2)R