《数据结构与算法分析》课件第5章-树

第五章图

树是以分支关系定义的层次结构，是一类重要的非线性数据结构。树的基本概念二叉树的应用——哈夫曼树树及二叉搜索树二叉树的特点及存储结构二叉树的遍历树的基本概念

定义树(tree)是n(n≥0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)。其余结点可分为m(m>0)个互不相交的子集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。特点非空树中至少有一个结点——根树中各子树是互不相交的集合树的基本概念A只有根结点的树ABCDEFGHIJKLM有子树的树根子树树的基本概念基本术语结点(node)

:树中元素，包括数据项及若干指向其子树分支。结点的度(degree)

:结点拥有的子树数。叶子结点(leaf)

:度为0的结点。孩子结点(child)

:结点子树的根称为该结点的孩子结点。双亲结点(parents)

:孩子结点的上层结点称该结点的双亲结点。兄弟结点(sibling)

:同一双亲的孩子结点。树的度:树中最大的结点度数。结点的层次(level)

:根为第一层，其孩子结点为第二层……。深度(depth)

:树中结点的最大层次数。森林(forest

):

m(m

0)棵互不相交的树的集合。树的基本概念【例1】ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4二叉树的基本概念

定义特点n(n0)个结点的有限集，或为空树(n=0)，或由根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。每个结点至多有二棵子树(即不存在度大于2的结点)。二叉树的子树有左、右之分，且其次序不能任意颠倒。基本形态AB右子树为空AB左子树为空A只有根结点

空二叉树ABC左、右子树均非空二叉树的基本概念几种特殊形态的二叉树完全二叉树满二叉树深度为k，有n个结点的二叉树。当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。深度为k且有2k－1个结点的二叉树。每一层结点数都是最大结点数。abcdefg满二叉树abcdeg非完全二叉树abcde完全二叉树二叉树的性质证明：用归纳法

在二叉树的第i层上至多有2i-1

个结点（i≥1）。

设对所有j(1j<i)命题成立，即第j层上至多有2j-1个结点，那么，第i-1层至多有

个结点

i=1时，只有一个根结点

又二叉树每个结点的度至多为2i-2第i层上最大结点数是第i-1层的2倍，即

2·2i-2

=2i-12性质1二叉树的性质性质2

深度为k的二叉树至多有2k-1个结点（k≥1）。证明：由性质1，可得深度为k的二叉树最大结点数是

性质3若终端结点数为n0,度为2的结点数为n2

，则：n0=n2+1于是，n=B+1=n1+2n2+1=n0+n1+n2

n0=n2+1又：B=设B为分支总数，则：证明：设n1为二叉树T中度为1的结点数，则n=n0+n1+n2n=B+1n1+2n2二叉树的性质性质4因而可推出：同样利用2k-1－1＜n≤2k－1有2k-1＜n+1≤2k

证明：由完全二叉树定义可知，一个k层完全二叉树的前k-1层

共有2k-1-1个结点2k-1－1＜n≤2k－1因为k为整数，故有2k-1≤n＜2k

取对数后可得：k-1≤log2n＜k即：k=取对数后得：k-1＜log2(n+1)≤k因而：k=第k层上还有若干结点，故结点数n满足关系：有n个结点的完全二叉树的深度为log2n+1

或log2(n+1)

。

log2n

+1k-1=log2n

log2(n+1)二叉树的存储实现顺序存储

将二叉树的结点，按一定的顺序化方式，存储到一片连续的存储单元中。结点的顺序应反映出结点之间的逻辑关系。关键：找到二叉树结点的排列顺序（反映结点的逻辑关系）ABEFCD完全二叉树的结点按上->下，从左->右排列，可得到唯一的排列次序！结点的排列：ABCDEF二叉树的存储实现完全二叉树的结点编号规则若i=1，则i结点是根结点；若i>1，则结点的双亲为i/2

。若2i>n，则i结点无左孩子，i结点是终端结点；若2i≤n，则2i是结点i的左孩子。若2i+1>n，则i结点无右孩子；若2i+1≤n，则2i+1是结点i的右孩子。若i为奇数且不等于1时，结点i的左兄弟是i-1，否则结点i没有左兄弟。若i为偶数且小于n时，结点i的右兄弟是i+1，否则结点i没有右兄弟。二叉树的存储实现增设虚结点构成n个结点的完全二叉树。按自上而下，从左至右的方式对结点顺序编号，即得到结点之间关系的线性序列，并依此将各结点存储到n+1个单元的向量中。存储方法结点的存储：编号01234567结点值

ABC@@@D二叉树的存储实现类型描述#defineMAXSIZE1024typedefintDatatype;typedefstruct{Datatypedata[MAXSIZE];intlast;//最后一个结点在表中的位置}SequenTree;二叉树的存储实现链式存储链式存储是二叉树的一种自然链接方法。每个结点至少包括三个域：结点数据域(data)、左孩子指针域(lchild)和右孩子指针域(rchild)。typedefintDatatype;typedefstructnode

{

Datatypedata;structnode*lchild,*rchild;}Bitree;Bitree*root;类型描述二叉树的存储实现存储示例二叉树二叉链表三叉链表二叉树的存储实现算法关键点双亲结点与左、右链接完→出队

front指向下一待链接双亲结点根在队列中第一个单元。rear偶数->是双亲的左孩子

奇数->是双亲的右孩子指针数组队列存放输入结点（地址）:bitree*Q[MAX]

rear队尾——当前输入结点

front队头——双亲结点先建立的结点，孩子结点也先建立(按完全二叉树层次输入)应保存所建立结点的地址，直至完成与其孩子结点的链接二叉树的存储实现二叉链表的建立按完全二叉树的层次顺序，依次输入结点信息来建立二叉链表。如此反复进行，直到输入结束标志“＃”为止。

若新结点是第1个结点，则令其为根结点，否则将新结点作为孩子链接到它的双亲结点上；依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点；二叉树的存储实现算法实现//初始化

Bitree*creatree()

{

//函数返回指向根结点的指针

charch；

//结点信息变量

Bitree *Q[maxsize]；//指针类型数组来构成队列

int

front,rear；//队头和队尾指针变量

bitree

*root,*s；//根结点指针和中间指针变量

root=NULL；

//二叉树置空

front=1;

//设置队列指针变量初值

rear=0;

二叉树的存储实现while((ch=getchar())!='#'){//不是结束符时

s=NULL;

if(ch!=‘@’){//当不是虚结点则建立新结点

s=(bitree*)malloc(sizeof(bitree));

s→data=ch;s→lchild=NULL;s→rchild=NULL;

}

rear++;Q[rear]=s;

if(rear==1)root=s;

else{

if(s&&Q[front])//孩子和双亲结点都不是虚结点

if(rear%2==0)Q[front]→lchild=s;

elseQ[front]→rchild=s;if(rear%2==1)

front++;//两个孩子处理完毕，出队列

}

}

returnroot;二叉树的遍历遍历方法

按一定的规律和次序走遍二叉树的每一个结点，使得每个结点被访问一次且仅被访问一次。先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点DLRDLR、LDR、LRDRDL、RLD、DRL二叉树的遍历【例2】二叉树的遍历。-+/a*b-efcd先序遍历：-+a*b-cd/ef中序遍历：-+a*b-cd/ef后序遍历：-+a*b-cd/ef层次遍历：-+a*b-cd/ef二叉树的遍历遍历算法voidpreorder(Bitree*p){//p指向二叉树的根结点

if(p!=NULL){

printf(“%c”,p→data);

//访问p所指结点

preorder(p→lchild);

//先序遍历左子树

preorder(p→rchild);

//先序遍历右子树}return;}

先序遍历递归算法二叉树的遍历先序遍历过程先序遍历算法执行过程二叉树的遍历中序遍历递归算法voidinorder(Bitree*p){

//p指向二叉树的根结点

if(p!=NULL)

{

inorder(p→lchild);//中序遍历左子树

printf(“%c”,p→data);

//访问p所指结点

inorder(p→rchild);//中序遍历右子树}

return;}二叉树的遍历后序遍历递归算法voidpostorder(Bitree*p){

//p指向二叉树的根结点

if(p!=NULL)

{

postorder(p→lchild);//后序遍历左子树

postorder(p→rchild);

//后序遍历右子树

printf(“%c”,p→data);//访问p所指结点

}

return;}二叉树的遍历层次遍历算法重复至队空为止上层先访问的结点，下层的孩子结点也必然先被访问根→入队；队头出队并访问；孩子结点入队Bitree*Q[maxsize];voidLayer(Bitree*p){

Bitree*s;if(p!=NULL){rear=1;front=0;

Q[rear]=p;

while(front<rear){front++;

s=Q[front];printf(“%c”,s->data);if(s->lchild!=NULL){rear++;Q[rear]=s->lchild;}

if(s->rchild)!=NULL){rear++;Q[rear]=s->rchild;}}

}}二叉树的遍历中序遍历非递归算法任何一种遍历方式，都只能从树的根结点开始，并按照不同的遍历次序访问相应结点。在该过程中，需保存树中结点的地址。①通过双亲结点，才能找到孩子结点②双亲结点的地址需保留至孩子结点处理完毕③后保存的节点其孩子节点先处理完用栈保存结点地址二叉树的遍历设栈stack[n]来保存访问结点的地址。top为栈顶指针，指针s指向当前访问的结点。(2)s结点非空：结点地址进栈，使s=s→lchild(3)s结点空：退栈顶元素送s，访问该结点，使s=s→rchild过程重复至s==NULL，且top==-1(1)初始时s=root算法基本思想二叉树的遍历算法实现Bitree*stack[N];//N为所设栈的最大容量voidninorder(Bitree*root){//root指向二叉树的根结点

Bitree*s;

if(root!=NULL){top=-1;s=root;

while((top!=-1)||(s!=NULL)){while(s!=NULL){if(top==N-1){printf("overflow");return;}

else{top++;stack[top]=s;s=s→lchild;}}}s=stack[top];top--;printf(“%c”,s→data);s=s→rchild;}}}二叉树的遍历由遍历序列恢复二叉树

已知先序遍历序列、中序遍历序列二叉树或已知后序遍历序列、中序遍历序列二叉树【例3

】已知二叉树的先序序列为A,B,D,G,C,E,F,H，中序序列为D,G,B,A,E,C,H,F，确定对应的二叉树。由先序和中序序列构造二叉树的过程二叉树的遍历算法分析①先序序列→数组preod[n]中序序列→数组inod[n]②取先序序列的第一个元素作为根结点，并利用中序序列确定根结点的左、右子树结点在先序序列中的位置③用先序序列和中序序列分别对左、右子树进行构造数组preod[n]:ABDECFGij数组inod[n]:DBEACGFklm函数BPI(preod,inod,i,

j,k,l)左子树：BPI

(

preod,

inod,

i+1,

i+m-k,

k,

m-1

)右子树：BPI

(

preod,

inod,

i+m-k+1,

j,

m+1,

l

)二叉树的遍历Datatypepreod[maxsize],inod[maxsize];

//先序、中序序列Bitree*BPI(Datatypepreod[],Datatypeinod[],inti,intj,intk,intl){intm;Bitree*p;p=(Bitree*)malloc(sizeof(Bitree));//构造根结点

p->data=pred[i];m=k;//m记录根结点在中序序列中的位置

while(inod[m]!=preod[i])//在中序序列中查找根

m++;if(m==k)p->lchild=NULL;//左子树空

elsep->lchild=BPI(pred,inod,i+1,i+m-k,k,m-1);if(m==l)p->rchild=NULL;//右子树空

elsep->rchild=BPI(pred,inod,i+m-k+1,j,m+1,l);

returnp;}遍历算法应用——统计叶子结点

递归模型f(p->lchild)+f(p->rchild)

其它0

p==NULLf(p)=1

p->lchild==NULL且p->rchild==NULLintCountLeaf(bitree*p){

if(p==NULL)

return0;

else

if(p→lchild==NULL&&p→rchild==NULL)

return1;

else

returnCountLeaf(p->lchild)+CountLeaf(p→rchild);

}遍历算法应用——求二叉树深度

递归模型intHeight(Bitree*p){intlc,rc;if(p==NULL)return0;lc=Height(p->lchild)+1;rc=Height(p->rchild)+1;returnlc>rc?lc:rc;}

//Height遍历算法应用——表达式生成表达式有三种表达方式：前缀、中缀和后缀表达式。这三种表达式分别对应其表达式树的先序遍历、中序遍历和后序遍历。后缀表达式生成表达式树(1)维护一个操作数栈(2)扫描后缀表达式，若是操作数，则生成操作数结点入栈；若为操作符，则生成操作符结点，并将栈中头两个元素出栈，作为操作符结点的左右子树，然后将新生成的树作为操作数结点入栈。(3)重复(2)的操作直到后缀表达式结束为止。算法的主要思想栈中将仅剩一个结点，即为表达式树遍历算法应用——表达式生成算法关键代码Bitree*CreateExp(char*postexp){Bitreestack[MAXSIZE],t;

intsp=-1;//最顶端的有效数据索引while(*postexp!='\0'){ t=(Bitree*)malloc(sizeof(Bitree));

t->data=*postexp;

t->lchild=t->rchild=NULL;

if(*postexp=='*'||*postexp=='+'){

if(sp<1)returnNULL; t->lchild=stack[sp-1];//遇到操作符则出栈

t->rchild=stack[sp--];

stack[sp]=t; }

elsestack[++sp]=t;

//操作数入栈

postexp++;}if(sp==0)returnstack[0];else returnNULL;}

//CreateExp线索二叉树引入线索二叉树的目的是在遍历二叉树的动态执行过程中得到前趋和后继的信息。线索二叉树在二叉链表中增加前趋指针域和后继指针域，分别指向该结点在某种次序下的前趋结点和后继结点。指向前趋和后继的称为线索。线索二叉树线索二叉树的结点结构将二叉树变为线索二叉树的过程称为线索化。可利用空指针域存放线索。lchild

ltag

datartagrchild

ltag=0lchild指向结点左孩子

1lchild指向结点的前趋

左线索rtag=0rchild指向结点右孩子

1rchild指向结点的后继

右线索线索二叉树类型描述typedefstructnode{//线索二叉树的结点结构

intltag,rtag;

Datatypedata;

structnode*lchild,*rchild;}Bithptr;Bitthptr

*pre;线索二叉树线索二叉树的建立——线索化在遍历过程中修改空指针。p—正访问结点pre—刚访问结点(2)若结点*p有中序前趋结点*pre（即*pre!=NULL），则：(1)若结点*p有空指针域，则ltag=1或rtag=1①

若pre->rtag==1则令pre->rchild=p②

若p->ltag==1则令p->lchild=pre(3)pre指向刚访问的结点*p(即pre=p)按中序遍历建立线索：ABDCp=NULL1pre1111中序遍历序列:BCAD线索二叉树算法InThread(Bithptr*p){

//线索标志初值为0,pre初值为NULL

if(p!=NULL){

INTHREAD(p->lchild);

//左子树线索化

if(p->lchild==NULL)p->ltag=1;//左线索标志

if(p->rchild==NULL)p->rtag=1;//右线索标志

if(pre!=NULL){

if(pre->rtag==1)//pre无右子树

pre->rchild=p;

//右线索指向*p

if(p->ltag==1)//*p无左子树

p->lchild=pre;//左线索为pre

}

pre=p;INTHREAD(p->rchild);//右子树线索化

}}

//InThread线索二叉树查找结点的前趋和后继

在中序线索二叉树中，求结点*p的中序后继结点：（1）若p->rtag=1，则中序后继结点是*(p->rchild)；（2）若p->rtag=0，则中序后继是*p的右子树中"最左下"的结点。ps线索二叉树算法bithptrINORDERNEXT(bithptr*p){//返回指向中序后继的指针bithptr*q;

if(p->rtag==1)

return(p->rchild);//*p的右子树为空

else{//*p的右子树非空

q=p->rchild;//从*p的右孩子开始查找

while(q->ltag==0)//当*q不是左下结点时，继续查找

q=q->lchild;

return(q);

}}//INORDERNEXT线索二叉树

在中序线索二叉树中，求结点*p的中序前趋结点：（1）若p->ltag=1，则中序前趋结点是*(p->lchild)；（2）若p->ltag=0，则中序前趋是*p的左子树中"最右下"的结点。pt线索二叉树在后序线索二叉树中，求结点*p的后序前趋结点：（1）若p->ltag=1，则后序前趋结点为*(p->lchild)；

（2）若p->ltag=0，则：①当p->rtag=0（右子树非空）则前趋结点为*(p->rchild)；

②当p->rtag=1（右子树为空）则前趋结点为*(p->lchild)。

ABCDEFGHINULL后序序列：DEBHIGFCA线索二叉树

在后序线索二叉树中，求结点*p的后序后继结点：（1）若*p为根，则后继为空；

（2）若*p是其双亲的右孩子，则其双亲即为后序后继结点；

ABCDEFGHINULL（3）若*p是其双亲的左孩子，但*p没有右兄弟时，则*p的后序后继结点是其双亲结点；（4）若*p是其双亲的左孩子，但*p有右兄弟时，则*p的后序后继结点是其双亲的右子树中"最左下"的叶子结点。后序序列：DEBHIGFCA线索二叉树说明后序线索树：找结点*p的后序前趋很容易；而找后序后继则有可能需从根结点开始进行遍历。

中序线索树：找结点*p的中序后继及中序前趋变得容易，不再需要遍历二叉树。

先序线索树：找结点*p的先序后继，仅从*p出发即可找到；但找其先序前趋则必须知道其双亲结点（即需要从根开始进行先序遍历）；线索二叉树线索二叉树的遍历

从该次序下的开始结点出发，反复找到结点在该次序下的后继，直到终端结点为止。（不需用栈来保存信息）voidTRAVINHREAD(Bithptr*p){if(p!=NULL){//非空树

while(p->ltag==0)//找中序序列的开始结点

p=p->lchild;

do{

printf(“%c”,p->data);//访问结点

p=INORDERNEXT(p);//找*p中序后继结点

}while(p!=NULL);

}}

//TRAVINHREAD遍历中序线索二叉树线索二叉树查找后继结点//返回指向中序后继的指针BithptrINORDERNEXT(Bithptr*p){Bithptr*q;

if(p->rtag==1)

return(p->rchild);//*p的右子树为空

else{

//*p的右子树非空

q=p->rchild;//从*p的右孩子开始查找

while(q->ltag==0)//*q不是左下结点时，继续查找

q=q->lchild;

return(q);

}}//INORDERNEXT树和森林树的存储结构双亲表示法为每个结点存储其双亲结点的地址信息。可用链表或顺序存储方式实现。#defineMAXSIZE32//结点数目的最大值加1typedefcharDatatype;//Datatype在此为char型typedefstruct{Datatypedata;//数据域intparent;//双亲结点的下标}Ptree;PtreeT[MAXSIZE];类型描述：树和森林存储示例结点012345678910data

ABCDEFGHIJparent-10111223444双亲表示法树和森林孩子表示法typedefstructcnode{

intchild;//孩子结点序号

structcnode*next;}Link;//孩子链表结点typedefstruct{

Datatypedata;//树结点数据

intparent;//双亲指针

Link*headptr;//孩子链表头指针

}Ctree;CtreeT[MAXSIZE];类型描述：为树中每个结点建立一个孩子链表。树和森林存储示例孩子表示法树和森林孩子兄弟表示法在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域first和next。特点：与二叉树的二叉链表表示相同树和森林树、森林和二叉树之间的转换树转换为二叉树(1)在兄弟之间增加一条连线。(2)对每个结点，除了保留与其左孩子的连线外，应除去与其他孩子之间的连线。(3)以树的根结点为轴心，将整个树顺时针旋转45°。树和森林二叉树转换成树(1)若结点X是双亲Y的左孩子，则把X的右孩子，右孩子的右孩子……都与Y用连线相连。(2)去掉原有的双亲到右孩子的连线。树和森林森林转换成二叉树将森林中的每一棵树转换为二叉树；再将第一棵树的根作为转换后二叉树的根，第一棵树的左子树作为转换后二叉树根的左子树，第二棵树作为转换后二叉树的右子树，第三棵树作为转换后的二叉树根的右子树的右子树如此类推..…哈夫曼树Huffman提出一种不定长编码方法。该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，亦称为最佳编码，通常称Huffman编码。用于设计Huffman编码的二叉树即哈夫曼树(HuffmanTree)。概念路径树中一个结点到另一结点之间的分支构成两结点间的路径。路径长度路径上的分支数。其中：权值

结点到根的路径长度树的路径长度从树根到每一个结点的路径长度之和。树的带权路径长度树中所有叶子结点带权路径长度之和。哈夫曼树设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，则wpl最小的二叉树。Huffman树【例4】4个结点权值分别为7,5,3,4的哈夫曼树。WPL1

=3×2+4×2+5×2+7×2

= 38WPL2= 3×3+4×3+5×2+7

= 38哈夫曼树哈夫曼树的构造④重复上述两步，直到只含一棵树为止，即哈夫曼树。③在树集中删除这两棵树，同时将新得到的二叉树加入树集中；②在树的集合中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和；①根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令其权值为wj；哈夫曼树【例5】

给定4个叶子结点，构造Huffman树。a7b5c2d47ab5c2d46711ab5c2d46a7b5c2d461118哈夫曼树数据结构结点结构一棵有n个叶子结点的huffman树有2n-1个结点

用大小为2n-1的向量存储Huffman树中的结点#defineN4//叶子数目#defineM2*n-1//结点总数typedefstuct{floatweight;chardata;intlchild,rchild,parent;}Hufmtree;Hufmtree

tree[M];parentlchilddataweightrchild哈夫曼树③for(i=n;i<2n-1;i++){//合并n-1次

挑最小、次小权值结点P1、P2；合并P1和P2，并修改相应结点的双亲、左、右域

}②对前0～n-1个(n个叶子）结点赋值：data和权值①初始化数组hufmtree[2n-1]（n——叶子结点个数）算法哈夫曼树voidHuffman(huffmantree[]){inti,j,p1,p2;charch;floatsmall1,small2,f;for(i=0;i<M;i++){tree[i].parent=-1;tree[i].lchild=-1;tree[i].rchild=-1;tree[i].weight=0.0;tree[i].data='0';}for(i=0;i<n;i++){//输入前n个结点的权值

scanf(“%f”,&f);tree[i].weight=f;scanf(“%c”,&c);tree[i].data=ch;

}

哈夫曼树

for(i=N;i<M;i++){//进行n-1次合并,产生n-1个新结点

p1=p2=0;small1=small2=Maxval;

for(j=0;j<=i-1;j++)if(tree[j].parent==-1)if(tree[j].weight<small1){//改变最小值

small2=small1;small1=tree[j].weight;

p2=p1;p1=j;}elseif(tree[j].weight<small2){//改变次小值

small2=tree[j].weight;

p2=j;

}

tree[p1].parent=i;tree[p2].parent=i;

tree[i].lchild=p1;

tree[i].rchild=p2;

tree[i].weight=tree[p1].weight+tree[p2].weight;

}}//Huffman哈夫曼树【例6】权值为0.4、0.3、0.1、0.1、0.02、0.08的6个叶子结点A、B、C、D、E、F，构造对应的哈夫曼树。哈夫曼树哈夫曼编码依据字符出现的频率来构造异字头的平均长度最短的编码方法。等长编码不等长编码编码码字的长短不等，但须是前缀码（为避免多义性），即任一字符的编码都不是另一字符编码的前缀。各字符的二进制码长相同。译码方便，码串长。等长编码：不等长编码：a:0

b:00

c:01

d:1e:10

f:100g:101h:110a:000b:001c:010d:011e:100f:101g:110h:111【例7】电文中出现的字符所有字符为a,b,c,d,e,f,g,h，则，哈夫曼编码存储结构bit[n]bit[n]code[0]startstartstartstartbit[n]bit[n]code[1]code[n-2]code[n-1]

typedefstruct{

charbits[n];

intstart;

}Codetype;

Codetype

code[n];编码过程从叶子tree[i]出发，利用双亲地址找到双亲结点tree[p]，再利用tree[p]的lchild和rchild指针域判断tree[i]是tree[p] 的左孩子还是右孩子，然后决定是分配代码的'0'还是代码'1'，接着以tree[p] 为出发点继续向上回潮，直到根结点为止。哈夫曼编码算法voidHuffmanCode(Codetypecode[],HufmTreetree[]){ inti,c,p; Codetypecd;//缓冲变量

for(i=0;i<N;i++){//n为叶子结点数目

cd.start=N;c=i;

p=tree[c].parent;

while(p!=-1){

cd.start--;

if(tree[p].lchild==c)cd.bits[cd.start]='0';

else cd.bits[cd.start]='1';

c=p;

p=tree[c].parent;

}

code[i]=cd;

}}

//HuffmanCode哈夫曼译码译码过程从根结点出发，逐个读入电文中二进制代码。若代码为0则走向左孩子；否则走向右孩子。一旦到达叶子结点，便可译出代码所对应的字符。重新从根结点开始继续，直到电文结束。DCBA0101017524

-1A7-16-1B5-15-1C2

-14-1D4-142‘0’6351‘0’1146

0‘0’185-10123456lchilddata

weightparentrchild电文：1101110译码：C

D

A哈夫曼译码算法voidHuffmanDecode(Codetypecode[],HufmTreetree[]){ inti,c,p,b,endflag=-1;

//电文结束标志取-1

i=m-1;//从根结点开始向下搜索

scanf("%d",&b);//读入一个二进制代码

while(b!=endflag){

if(b==0)i=tree[i].lchild;//走向左孩子

elsei=tree[i].rchild;//走向右孩子

if(tree[i].lchild==-1){//tree[i]是叶子结点

putchar(code[i].data);

i=m-1;//回到根结点

}

scanf("%d",&b);//读入下一个二进制代码

} if((tree[i].lchild!=0)&&(i!=m-1))//电文读完尚未到叶子结点

printf("\nERROR\n");}

//HuffmanDecode

二叉排序树定义二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。特点：中序遍历二叉排序树可得到递增序列。二叉排序树二叉排序树的插入否则，与根结点比较，并在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子。若二叉排序树为空，则插入结点应为新的根结点；二叉排序树的生成从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。二叉排序树二叉排序树的构造过程(1)令R1为二叉树的根。(2)若R2<R1，令R2为R1左子树的根结点；否则R2为R1右子树的根结点。(3)对于R3，…，Rn结点，依次与前面生成的结点比较以确定输入结点的位置。二叉排序树【例8】

已知结点{10,18,3,8,12,2,7,3}，试构造二叉排序树。二叉排序树构造算法——

结点插入Bstnode*INSERTBST(Bstnode*t,Bstnode*s)

{//t根指针

Bstnode*f,*p;

p=t;

if(p==NULL)returns;

while(p!=NULL)

{

f=p;//f将指向*p结点的双亲

if(s->key==p->key)

returnt;//树中已有结点*s

if(s->key<p->key)

p=p->lchild;

elsep=p->rchild;

}

if(s->key<f->key)

f->lchild=s;

elsef->rchild=s;

returnt;}二叉排序树构造算法——

生成算法Bstnode*creatbst(){

Bstnode*t,*s;

intkey,endflag=0;//endflag为结点结束标志

t=NULL;//设置二叉排序树的初态为空树

scanf(“%d”,&key);//读入一个结点的关键字

while(key!=endflag)

{

s=(bstnode*)malloc(sizeof(bstnode));

s→lchild=s→rchild=NULL;//赋初值

s→key=key;

t=INSERTBST(t,s)；//将新结点插入树t中

scanf(“%d”,&key)//读入下一个结点的关键字

}

returnt;

}二叉排序树结点的删除删除二叉排序树中的*p结点，*f为其双亲结点：

p左、右子树均非空p只有左子树或右子树p为叶子结点f->lchild=NULL或f->rchild=NULLf→lchild（或f→rchild)=p→lchild或f→lchild（或f→rchild)=p→rchild令*p的左子树为*f的左（或右）子树，而*p的右子树接到*p的中序前趋结点*s的右指针上。二叉排序树结点的删除删除二叉排序树中的*p结点，*f为其双亲结点：

p左、右子树均非空p只有左子树或右子树p为叶子结点f->lchild=NULL或f->rchild=NULLf→lchild（或f→rchild)=p→lchild或f→lchild（或f→rchild)=p→rchild令*p的左子树为*f的左（或右）子树，而*p的右子树接到*p的中序前趋结点*s的右指针上。二叉排序树【例9】

二叉排序树的结点删除示例1。二叉排序树【例10】

二叉排序树的结点删除示例2。二叉排序树结点删除算法Bstnode*DelBstNode(Bstnode*t,Keytypek){

Bstnode*p,*q,*s,*f;

p=t;

q=NULL;

while(p!=NULL){//查找关键字为k的待删结点

if(p->key==k)break;

q=p;

if(p->key>k) p=p->lchild;

elsep=p->rchild;

}

if(p==NULL)returnt;//找不到结点，返回原树

if(p->lchild==NULL){// p所指结点的左子树为空

if(q==NULL)t=p->rchild;//p为原树的根

elseif(q->lchild==p)q