数据结构-第四章-层次结构-树

第四章层次结构——树1.树的描述有唯一的结点没有前缀其余结点都有且只有一个前缀从根结点可以按后继关系到达其余各结点

4.1、树的概念4.1树的概念4.2二叉树4.3树的应用主要内容2.树的表示表(a(b(e(k,l),f),(c(g)),(d(h,i,j)))凸凹图集合图树形图4.1树的概念树的凹凸图表示abekIfcgdhij树的集合表示ghijaklbefcd树的树形表示3.树的术语根、叶、分支结点父子、兄弟、祖孙关系高度度子树、森林有序树

4.1树的概念结点的名称根：树中没有前缀的结点成为根叶子：树中没有后继的结点成为叶子分支节点：除根和叶子之外的结点结点的关系双亲和孩子：若结点a是结点b的前缀，则称a是b的双亲，b是a的孩子兄弟：若结点a也是c的双亲，则c是b的兄弟，b也是c的兄弟祖先和子孙：若b又是e的前缀，则称a是e的祖先，e是a的子孙结点的层次：即结点所在的层数，对于一棵树，从根算起，根是第一层，根的孩子为第二层，依此类推高度：结点的层次，也叫做结点的高度。树中结点高度最大者，为树的高度。度：结点的度，指的是该节点孩子的个数，树中所有结点中度最大者，为该树的度。提问：叶子节点的度是多少？子树：由树的一部分结点组成，并保持原树中的父子关系，其结构也是一棵树，成为原树的子树。森林：m棵互不相交的树的集合有序树：若树中各结点的子树从左到右是有次序地，不能交换则成该树为有序树4.树的存储结点结构根指针:链头指针空间利用率：4.1树的概念返回树中结点有多个后继，所以不能使用顺序结构，采用链接结构，每个结点中有多个指针域，指向孩子、双亲、兄弟等datachild1child2……childn存储空链域太多，空间利用率低ab∧c∧∧de∧f∧∧∧g∧∧∧h∧∧∧i∧∧∧j∧∧∧k∧∧∧l∧∧∧t4.2二叉树二叉树的概念性质二叉树的存储二叉树的运算1、二叉树的概念二叉树是一种特殊的树。其结点个数可以为0，这是称其为空二叉树。如果二叉树不为空，则具有以下特征：每个结点最多只有两棵子树两棵子树有左右之分，其次序不能任意颠倒（即是有序树）二叉树的五种基本形态图5.1二叉树的五种基本形态

二叉树中关系的一些定义左子结点:左子树的根结点，称为左孩子右子结点：右子树的根节点，称为右孩子兄弟结点：具有同一个父结点的，相互之间称为兄弟结点叶结点：没有孩子结点的结点称为叶结点，也称为终端结点一般的树用二叉树表示左手抱孩子，右手抱兄弟满二叉树和完全二叉树如果一棵二叉树每层的结点数目都达到最大，则这棵二叉树称作满二叉树(fullbinarytree)。如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的连续位置上，则此二叉树称作完全二叉树(completebinarytree)。1523456789114131211102345678911110完全二叉树完全二叉树的特点是：其叶结点只可能在层次最大的两层出现完全二叉树中由根结点到各个结点的路径长度总和在具有同样结点个数的二叉树中达到了最小，即任意一棵二叉树中根结点到各结点的最长路径一定不短于结点数目相同的完全二叉树中的路径长度目录

2、二叉树的主要性质性质1.在二叉树中，第i层上最多有2i-1个结点（i≥1）

证明：利用数学归纳法当i=1时，2i-1=1，只有一个根结点，正确。现在假设对所有的j，1≤j＜

i，命题成立，即第j层上之多有2j-1个结点。下面证明当就j=i时结论也成立。由归纳假设，第i-1层上最多有2i-2个结点。由于二叉树每个结点的度数最大为2，所以第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2i-1个。二叉树的主要性质性质2.高度为k的二叉树至多有

2k-1个结点（k≥0）。其中高度(depth)定义为二叉树中层数最大的叶结点的层数。证明：由性质1可知，第i层的最大结点数为2i-1，所以二叉树的主要性质性质3.任何一棵二叉树，若其终端结点数为n0

，度为2的结点数为n2，则n0=n2+1

。

证明：设n1为二叉树中度为1的结点数。该二叉树的结点总数n为度分别为0，1，2的结点数之和，即n=n0+n1+n2（5.1）

除根结点外，其余结点都有一条边进入，设边数为e，有n=e+1。由于这些边是由度为1或2的的结点射出的，所以又有e=n1+2n2，于是得

n=e+1=n1+2n2+1 （5.2）由公式5.1和5.2得n0+n1+n2=n1+2n2+1，即n0=n2+1

二叉树的主要性质性质4.满二叉树定理：非空满二叉树树叶数目等于其分支结点数加1。

证明：满二叉树定理由性质3可直接推出。

性质5.满二叉树定理推论：一个非空二叉树的空子树数目等于其结点数加1。

证明：设二叉树为T，度为1的结点下空子树数目为1，度为0的节点空子树数目为2，所以空子树的数目为n1+2n0 根据性质3，n=n1+n2+n0=n1+2n0-1 我们有：n1+2n0=n+1

二叉树的主要性质性质6.有n个结点（n>0）的完全二叉树的高度为[log2(n+1)]。其中二叉树的高度(height)定义为二叉树中层数最大的叶结点的层数。证明：假设高度为h，则根据性质2和完全二叉树的定义，有或不等式中各项取对数，于是得到。因为h为整数，所以h＝[log2(n+1)]。

二叉树的主要性质性质7.对于具有n个结点的完全二叉树，结点按层次由左到右编号，则对任一结点i（1≤i≤n）有

（1）如果i=1，则结点i是二叉树的根结点；若i＞1，则其父结点编号是[i/2]。（2）当2i≤n时，结点i的左子结点是2i，否则结点i没有左子结点。当2i+1≤n时，结点i的右子结点是2i+1，否则结点i没有右子结点。

二叉树的主要性质证明：对于i=1，由完全二叉树的定义，其左孩子的编号是2，如果2>n，即不存在编号为1的结点，此时结点i没有左孩子。其右孩子的编号只能是3，如果3>n，此时结点i没有右孩子。对于i>1分两种情况讨论：(1)设第j层的第一个结点编号为i(此时有i=2j-1)，则其左孩子必为第j+1层的第一个结点，其编号为2j=2i，如果2i>n，那么i没有左孩子；其右孩子必为第j+1层第二个结点，其编号为2i+1。(2)假设第j层的某个结点编号为i，若它有左孩子，那么它的左孩子必然是第j+1层中的第2[i-2j-1]个，那么其左孩子的编号就是2j+2[i-2j-1]=2i；如果结点i有右孩子，那么其右孩子的编号必是2i+2。目录

3、二叉树的存储通常采用链接的形式lchild指向左孩子，rchild指向右孩子lchilddatarchildlchildparentdatarchild5.3.1二叉树的链式存储结构图5.8

图5.5中二叉树的二叉链表存储结构

容易看出，在含有n个结点的二叉链表中有n+1个空链域。可以利用这些空链域存储其它的有用信息，形成其它的链式存储结构。图5.5二叉树示例结点类型typedef

struct

BiTreeNode

{

BiTreeNode*lchild;

BiTreeNode*rchild;

ElemTypedata;}BiTree;

4、运算遍历（也叫周游）插入、删除（1）遍历遍历广度优先遍历——水平遍历深度优先遍历——前序遍历、中序遍历、后序遍历①水平遍历概念：按照层次从小到大，从左到右访问二叉树的所有结点水平遍历结果：ABCDEFGHI①水平遍历思路：访问结点的过程中应该将其孩子结点存储起来，等处理下一层时再取出来处理。从左到右遍历，处理下一层时，结点遍历的顺序和存储的顺序一致所以采用队列①水平遍历算法初始化；当队不空时，重复做：出队；处理；如果有左子，左子进队；如果有右子，右子进队；voidLevelOrder(BiTree*r){

if(r==NULL) return;

linkQue

aQue;

CreatlnkQueue(aQue);

BiTree*p=r;

enQueue(aQue,p);//根入队

while(!QueisEmpty(aQue)) {

deQueue(aQue,p);//队头出队

visit(p);//访问

if(p->lchild!=NULL)

enQueue(aQue,p->lchild);//左孩子入队

if(p->rchild!=NULL)

enQueue(aQue,p->rchild);//右孩子入队 }

DellnkQueue(aQue);}②前序遍历概念：先处理根，然后遍历左子树，最后遍历右子树前序遍历结果：ABDEGCFHI思路为了保证遍历的持续，

需使用表临时存储

一些结点的地址。保存和取出的次序为先进后出。故应使用栈。算法初始化当未遍历完，重复做：如果当前结点非空，处理，进栈，取左子；否则，出栈，取右子。voidPreOrder(BiTree*r){

if(r==NULL) return;

lnkStack*s=NULL;

BiTree*p;

p=r;

while(!StackIsEmpty(s)||p) {

if(p) {

visit(p);

push(s,p); p=p->lchild; } else {

pop(s,p); p=p->rchild; } }}③中序遍历概念：先遍历左子树，然后处理根，最后遍历右子树中序遍历结果：DBGEACHFI思路在前序遍历的基础上，将处理结点的语句后移。voidInOrder(BiTree*r){

if(r==NULL) return;

lnkStack*s=NULL;

BiTree*p=r;

while(!StackIsEmpty(s)||p) {

if(p) {

push(s,p); p=p->lchild; } else {

pop(s,p);

visit(p); p=p->rchild; } }}④后序遍历概念：先遍历左子树，然后遍历右子树，最后处理根后序遍历结果：DGEBHIFCA思路需要两次访问栈顶结点。前者是为了处理其右子树，后者是为了处理该结点。算法取栈顶结点；如果是第一次访问，设标记，取右子；否则，出栈，处理。voidPostOrder(BiTree*r){

if(!r) return;

lnkStack*s=NULL;

BiTree*p=r;

PostOrderNodetag;

while(!StackIsEmpty(s)||p) {

while(p!=NULL) {

tag.p=p;

tag.isLeft=1;

push(s,tag); p=p->lchild; }

pop(s,tag);

if(tag.isLeft) {

tag.isLeft=0; p=tag.p;

push(s,tag); p=p->rchild; } else {

visit(tag.p); p=NULL; } }}深度优先递归算法【算法1】

深度优先前序遍历voidPreOrder(BiTree*root){ //前序周游二叉树或其子树

if(r!=NULL){

Visit(r); //访问当前结点

PreOrder(r->lchild); //前序周游左子树

PreOrder(r->rchild); //前序周游右子树 }}深度优先递归算法【算法2】

中序遍历voidInOrder(BiTree*r){ if(r!=NULL){

InOrder(r->lchild); //中序周游左子树

Visit(r); //访问当前结点

InOrder(r->rchild);//中序周游右子树 }}深度优先递归算法【算法3】后序遍历voidPostOrder(BiTree*r){ //后序周游二叉树或其子树

if(r!=NULL){

PostOrder(r->lchild()); //后序周游左子树

PostOrder(r->rchild()); //后序周游右子树

Visit(r); //访问当前结点 }}深度优先遍历二叉树对于有n个结点的二叉树，遍历完树的每一个元素都需要O(n)时间只要对每个结点的处理（函数Visit的执行）时间是一个常数，那么遍历二叉树就可以在线性时间内完成所需要的辅助空间为周游过程中栈的最大容量，即树的高度最坏情况下具有n个结点的二叉树高度为n，则所需要的空间复杂度为O(n)目录

5、二叉树的运算例1：求二叉树结点个数思路：将原有遍历算法中访问结点的函数从打印结点内容改为计数即可例2求二叉树中值为v的结点的父结点值思路一：在遍历算法中，访问结点变为比较结点的孩子值是否为V。思路二：采用后序遍历。栈顶元素即为父结点例4.3已知二叉树root，要求按层输出各结点值思路：按层处理，采用水平遍历，用计数器记录每层入队时结点的个数，出队时计数器值为0时，该层结束，换行voidLevelOrderInLine(BiTree*r)//例4.3{

if(r==NULL) return;

linkQue

aQue;

CreatlnkQueue(aQue);

BiTree*p=r;

enQueue(aQue,p);

intcount=1;

int

dcount=0;

while(!QueisEmpty(aQue)) {

if(dcount==0) {

dcount=count; count=0; }

deQueue(aQue,p);

dcount--;

visit(p);

if(dcount==0)

cout<<endl;

if(p->lchild!=NULL) {

enQueue(aQue,p->lchild); count++; }

if(p->rchild!=NULL) {

enQueue(aQue,p->rchild); count++; } }

DellnkQueue(aQue);}4.2.6二叉树的其他存储及运算①数组存储②带逆存储③穿线存储①数组存储Struct

arrTree{ElemTypedata;int

lchildint

rchild}arrTree

a[n];0A121B342C-153D-1-14E6-15F786G-1-17H-1-18I-1-1②带逆存储对于经常求父结点的问题，结点在存储时，可以存储父结点lchildparentdatarchild③穿线存储穿线存储的二叉树，也叫穿线树、或线索二叉树。利用结点中空闲的左右子链域：若作子链域空，则存储制定遍历下的前缀结点的地址；若右子链域空，则存储指定遍历下后继结点的地址构造方法

写出遍历序列画出穿线链修改相应链域:为了区别是否是穿线链，加标记前序遍历穿线树ABDEGCFHI中序穿线树DBGEACHFI后序遍历：DGEBHIFCA4.3树的应用1.二叉排序树2.堆排序3.哈夫曼树4.决策树5.博弈树1、二叉排序树二叉搜索树中的每个非空结点表示一个记录某结点左子树不空，则左子树上所有结点的值均小于该结点的关键码值若其右子树不为空，则右子树上所有结点的值均大于该结点的关键码值树中各结点的关键码必须是唯一的二叉搜索树可以是一棵空树，任何结点的左右子树都是二叉搜索树,按照中序周游整个二叉树得到一个由小到大有序排列1、二叉排序树对于关键码集合K={50，19，35，55，20，5，100，52，88，53，92}，二叉排序树的生成过程如图所示：5051955355220100539288查找插入删除二叉排序树的查找二叉排序树的高效率在于继续检索时只需要查找两棵子树之一：将给定值key与根结点的关键码比较，如果key小于根结点的值，则只需要检索左子树如果key大于根结点的值，就只检索右子树这个过程一直持续到key被匹配成功或者遇到叶结点为止如果遇到叶结点仍没有发现key，那么key就不在这棵二叉搜索树中查找运算

无需遍历算法效率与树的高度相关二叉排序树的插入算法：插入运算

要点：保持二叉排序树的特性插入位置的选择二叉排序树的插入算法：需要运用检索方法，查找待插入关键码是否在树中如果存在则不允许插入重复关键码如果直到找到空结点还没有发现重复关键码，那么就把新结点插入到待插入方向作为新的叶结点对于给定的关键码集合，可以从一个空的二叉搜索树开始，按照检索路径搜索这棵二叉树，将关键码一个个插入到相应的叶结点位置，从而动态生成二叉搜索树二叉排序树插入操作：将待插入结点的关键码与根结点的关键码相比较，若待插入的关键码小于根结点的关键码，则进入左子树，否则进入右子树。按照同样的方式沿检索路径直到叶结点，确定插入位置，把待插入结点作为一个新叶结点插入到二叉搜索树中。二叉排序树的删除设pointer，temppointer是指针变量，其中pointer表示要删除的结点。首先找到待删除的结点pointer，删除该结点的过程如下：若结点pointer没有左子树，则用pointer右子树的根代替被删除的结点pointer；若结点pointer有左子树，则在左子树里找到按中序周游的最后一个结点temppointer，把temppointer的右指针置成指向pointer的右子树的根，然后用结点pointer左子树的根代替被删除的结点pointer。

二叉排序树的删除图5.12二叉搜索树的删除示例图5.11二叉搜索树二叉排序树的删除改进的二叉搜索树结点删除算法的思想为：若结点pointer没有左子树，则用pointer右子树的根代替被删除的结点pointer若结点pointer有左子树，则在左子树里找到按中序周游的最后一个结点temppointer（即左子树中的最大结点）由于temppointer没有右子树，删除该结点只需用temppointer的左子树代替temppointer，然后用temppointer结点代替待删除的结点pointer二叉搜索树的删除图5.13改进的二叉搜索树的删除图5.11二叉搜索树52.552.5堆排序相关概念满二叉树完全二叉树堆排序堆：是这样的二叉树，他的每个结点的值都大于它的两个孩子（如果存在）的值，这就是堆最大堆：如果结点的值都大于孩子的值最小堆：如果结点的值都小于孩子的值302510201755421355941746堆的性质从逻辑的角度来讲，堆是一种树形结构，而且是一种特殊的完全二叉树。此完全二叉树的每个结点对应于序列中的一个关键码，根结点对应于关键码K0，按层次从左至右依次类推。说其特殊，主要是因为堆序只是局部有序，即最小堆对应的完全二叉树中所有内部结点的值均不大于其左右孩子的关键码值，而一个结点与其兄弟之间没有必然的联系。最小堆不像二叉搜索树那样实现了关键码的完全排序。相比较而言，只有当结点之间是父子关系的时候，才可以确定这两个结点关键码的大小关系。堆排序思路：将一个顺序表看作是顺序存储的完全二叉树将其调整为堆，则得到最大结点最大结点离堆，剩下结点调整成堆，次大结点离堆重复上述过程，直到只剩下一个结点（46，94，13，42，55，17，10，70）4694131017554270建堆算法从最后一个非叶结点开始逐个筛for(p=n/2;p>=1;p--)

sift(p,n);n/2筛一个结点的算法当p有孩子时将p较大的孩子=>k如果s[p]<s[k]则交换s[p],s[k]

否则结束（46，94，13，42，55，17，10，70）4694131017554270堆排序算法

set_heap(s,n)for(i=n;i>=2;i--)swap(s[1],s[i])sift(1,i-1)时间效率建堆算法：筛n/2个结点，log2n次比较选择排序：n-1遍，log2n次比较

O(nlog2n) 3、哈夫曼树

Huffman树

Huffman编码Huffman树假设有n个权值分别为w1，w2，…，wn(n≥2)的结点，求带权路径长度就是要构造一棵二叉树，每一个叶子结点ki取wi作为它的权，li表示该叶子结点的路径长度，则带权路径长度可记作WPL(T)WPL(T)=,其中带权路径长度最小的二叉树称为Huffman树。

Huffman树例如，图中表示了三棵具有4个叶结点的二叉树，各叶结点的权值分别为6，2，3，4。它们的带权路径长度分别为：(a)6×2+2×2+3×2+4×2=30(b)6×2+2×3+3×3+4×1=31(c)6×1+2×3+3×3+4×2=29其中，5.18(c)中所示的二叉树带权路径长度最小。可以验证，它就是一棵Huffman树，也就是说，这棵树在所有的具有6，2，3，4权值的叶结点的二叉树中带权路径长度最小。图5.18具有不同带权外部路径长度的二叉树3、Huffman树建立Huffman编码树：(1)对于给定的n个权值w1，w2，…，wn(n≥2)，构成n棵二叉树的集合T={T1，T2，…，Tn}，使得每一棵二叉树只具有一个带权为wi的根结点。(2)构造一棵新的二叉树，在集合T中找出两个权值最小的树作为新树根结点的左右子树，把新树根结点的权值赋为其左右子树根结点的和。(3)在集合T中删除这两棵树，并把得到的新二叉树加入到集合中。(4)重复步骤(2)、(3)的操作，直到集合T中只含有一棵树为止。5.6.1Huffman树Huffman树的构造过程236495152364（1）HT是权值越大的越靠近根结点；（2）HT不唯一，但WPL一定相等。5915typedef

struct

HuffmanNode{

intweight;//权值

intparent;//双亲下标

int

lchild,rchild;//左右孩子下标}HTree;HTree*intHTree(int*Element,int

n,int&cursize,int&size){//初始化，将权值Element赋给哈夫曼树为叶结点

inti;

HTree*list; size=2*n-1;//树中结点的个数

list=newHTree[size];

for(i=0;i<n;i++) {

list[i].weight=Element[i]; }

for(i=0;i<size;i++) {

list[i].parent=-1;

list[i].lchild=list[i].rchild=0; }

cursize=n; returnlist;}bool

FindMinTwo(HTree*list,int

cursize,int&f,int&s){

inti;

for(i=0;i<cursize;i++) {

if(list[i].parent==-1) { f=i; break; } }

if(i>=cursize) returnfalse;

for(++i;i<cursize;i++) {

if(list[i].parent==-1) { s=i; break; } }

if(i>=cursize) returnfalse;

if(list[f].weight>list[s].weight) {

int

tmp;

tmp=f; f=s; s=tmp; }

for(++i;i<cursize;i++) {

if(list[i].parent==-1&&list[i].weight<list[f].weight) { s=f; f=i; } elseif(list[i].parent==-1&&list[i].weight<list[s].weight) { s=i; } } returntrue;

}voidCreatHuffmanTree(HTree*&list,int

size,int&cursize){

int

f,s;

while(FindMinTwo(list,cursize,f,s)) {

list[cursize].weight=list[f].weight+list[s].weight;

list[cursize].lchild=f;

list[cursize].rchild=s;

list[f].parent=cursize;

list[s].parent=cursize;

list[cursize].parent=-1;

cursize++; }}5.6.2Huffman编码Huffman编码过程如下：用d1，d2，…，dn作为外部结点构造具有最小路径长度的二叉树把从每个结点引向其左子结点的边标上号码0，从每个结点引向其右子结点的边标上号码1从根结点到每个叶结点路径上的编号连接起来就是这个外部结点所代表字符的编码。得到的二进制前缀码就称作Huffman编码图5.20

Huffman编码示例5.6.2Huffman编码用Huffman算法构造出的二叉树给出了各字符的编码，同时也用来译码从二叉树的根开始，把二进制编码每一位的值与Huffman树边上标记的0，1相匹配，确定选择左分支还是右分支，直至确定一条到达树叶的路径。一旦到达树叶，就译出了一个字符。然后继续用这棵二叉树继续译出其它二进制编码AACBACBAABAABCDCACADAACCA定长编码：A:00;B:01;C:10;D:11编码长度：50

哈夫曼编码AACBACBAABAABCDCACADAACCA不定长编码：A:12;B:4;C:7;D:2A:0;B:01;C:1;D:11编码长度：31001010101...AACBACBAABAABCDCACADAACCA不定长编码：A:12;B:4;C:7;D:2A:0;B:101;C:11;D:100编码长度：440011101011101…返回voidCode(HTree*list,char**Hc,intn){

int

start,pi,j,i=0; char*s=newchar[n];

while(i<n){ s[n-1]='\0'; start=n-1; pi=list[i].parent; j=i;

while(pi!=-1){

if(list[pi].lchild==j) s[--start]='0'; elses[--start]='1'; j=pi; pi=list[pi].parent; }

strcpy(Hc[i],&s[start]); i++; } delete[]s;}5.6.2Huffman编码

例如，在一个数据通信系统中使用的字符是a，b，c，d，e，f，g，对应的频率分别为15，2，6，5，20，10，18。各字符的二进制编码为：a：00b：11110c：1110d：11111e：10f：110g