数据结构第6章树与二叉树

数据结构（C语言版）第6章树与二叉树本章主要知识点树、二叉树的基本概念二叉树的存储结构二叉树的多种遍历方式二叉树的线索化最优二叉树哈夫曼树树

1.树的定义

树：n（n≥0）个结点的有限集合。n＝0时，称为空树。任意一棵非空树满足以下条件：⑴有且仅有一个特定的称为根(root)的结点；⑵当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为该根结点的子树。2.树的表示法

树形表示法：用自然界倒长的树来表示，根在上，叶子在下；

集合表示法：用集合的形式来表示；(A(B(D)(E(I)(J)(F))(C(G)(H)))

凹入表示法：类似于书的编目，不同长度代表了不同层次，相同长度代表相同层次；嵌套括号表示法：用广义表表示；3基本术语(1)树的结点：由一个数据元素和若干指向其子树的分支组成。(2)结点的度：结点所拥有的子树的个数即分支数称为该结点的度。(3)叶子结点：度为0的结点称为叶子结点，或者称为终端结点。(4)分支结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶子结点外，其余的都是分支结点。(5)孩子、双亲、兄弟：树中一个结点的子树的根结点称为这个结点的孩子；这个结点称为它孩子结点的双亲；具有同一个双亲的孩子结点互称为兄弟。(6)路径、路径长度：如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（1≤i<k）,就把n1,n2,…,nk称为一条由n1至nk的路径。路径长度是指路径上经过的边的数量，所以这条路径的长度是k-1。(7)祖先、子孙：在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。(8)结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。(9)树的深度：树中所有结点的最大层数称为树的深度。(10)树的度：树中各结点度的最大值称为该树的度。(11)有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，不能交换的，称这棵树为有序树；反之，称为无序树。(12)森林：m(m≥0)棵互不相交的树的集合。(13)同构：对两棵树，若通过对结点适当重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。(14)层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给它们编以从1开始的连续自然数。4树的遍历从根结点出发，按照某种次序依次访问树中所有结点，使得每个结点被访问一次且仅被访问一次。树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式。(1)前序（根）遍历若树为空，则空操作返回；否则a.访问根结点；b.按照从左到右的顺序以前序遍历方式遍历根结点的每一棵子树。(2)后序（根）遍历若树为空，则空操作返回；否则a.按照从左到右的顺序以后序遍历方式遍历根结点的每一棵子树；b.访问根结点。(3)层序（次）遍历从树的第一层（即根结点）开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。5树的存储结构

(1)双亲表示法用一维数组来存储树的各个结点（一般按层序存储），数组中的一个元素对应树中的一个结点，该元素包含结点的数据信息以及该结点的双亲在数组中的下标。typrdefstructtnode{datatypedata;intparent;}tree[n](2)孩子表示法树中结点可能含有多个孩子，一般采用多重链表来表示，链表中的每个结点都包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。a.同构：按结点的度的最大值（即树的度）来设置指针域数量，即1个数据域和d（树的度）个指针域b.异构：按结点各自的度设置指针域数量，即结点有几棵子树就设几个指针。为了综合上述结构存在的各种问题，把每个结点的孩子排列起来，形成单链表形式的孩子链表，n个结点共有n个孩子链表。每个孩子链表均有1个头指针，共有n个头指针，这n个头指针又可以组成一个顺序存储结构的线性表。将存放n个头指针的数组和存放n个结点的数组结合起来，构成孩子链表的表头数组。typrdefstructtagnode/*表结点*/{intchild;structtagnode*next;}node,*link;typedefstruct/*头结点*/

{datatypedata;linkfirstchild;}headnode;typedefheadnodechildlink[maxnode];/*表头数组*/带双亲的孩子链表表示法：typedefstruct/*头结点*/{datatypedata;intparent;linkfirstchild;}headnode;(3)孩子兄弟表示法以二叉链表作存储结构，结点的两个指针域分别指向该结点的第一个孩子和右边的兄弟

typedefstructtreenode{datatypedata;structtreenode*firstchild,*rightsib;}treenode,*tree;二叉树定义与性质

二叉树的基本概念

二叉树（BinaryTree）是一种树形结构，是一个有限元素的集合，该集合可以为空、也可以由一个称为根(root)的元素和两棵互不相交的、被分别称为左子树和右子树的二叉树组成。二叉树具有五种基本形态:满二叉树:在一棵二叉树中，如果所有分支结点都有左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。满二叉树

非满二叉树

满二叉树中只有度为0和2的结点，没有度为1的结点。

完全二叉树：一棵深度为k的有n个结点的二叉树，将树中的结点按照从上往下、从左至右的顺序依次进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树非完全二叉树特点：(1)叶子结点只能出现在最下层和次下层，且最下层的叶子结点均集中在二叉树的左部;(2)深度为k的完全二叉树在k-1层上一定是

满二叉树；(3)至多只有一个度为1的结点。一棵满二叉树必定是一棵完全二叉树，而完全二叉树不一定是满二叉树，称满二叉树是完全二叉树的特例。

斜树所有结点都只有左子树的二叉树称为左斜树；所有结点都只有右子树的二叉树称为右斜树；左斜树和右斜树统称为斜树，也称为单枝二叉树。特点：（1）在斜树中，每一层只有一个结点；（2）斜树的结点个数与其深度相同；（3）斜树中不存在度为2的结点。2二叉树的主要性质性质1一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。证明用数学归纳法来证明：当i=1时，第1层只有一个根结点，而2i-1=20=1，结论显然成立。假定i=k时结论成立，即第k层上至多有2k-1个结点，则i=k+1时，因为第k+1层上的结点都是第k层上结点的孩子，而二叉树中每个结点至多有2个孩子，所以在第k+1层上最大结点个数为第k层上的最大结点个数的2倍，即2×2k-1＝2k。结论成立。性质2一棵深度为k的二叉树中，最多具有2k－1个结点。证明设第i层的结点数为mi（1≤i≤k），深度为k的二叉树的结点数为N，由性质1知第i层的结点数mi最多为2i-1，则有：N＝mi≤2i-1＝2k-1性质3对于一棵非空的二叉树，设叶子结点数为n0，度为2的结点数为n2，则有:n0＝n2＋1。证明设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：n＝n0＋n1＋n2在二叉树中，除根结点外，其余结点都有双亲，所以这些结点都有唯一的一个分支来指向。设B为二叉树中的分支数，那么有：B＝n－1B所代表的这些分支都是由度为1和度为2的结点发出的，一个度为1的结点发出1个分支，一个度为2的结点发出2个分支，所以有：B＝n1＋2n2

综上所述，可以得到：n0＝n2＋1性质4具有n个结点的完全二叉树的深度k为[log2n]+1。证明根据完全二叉树的定义和性质2可知，当一棵完全二叉树的深度为k、结点个数为n时，有2k－1－1<n≤2k-1即2k－1≤n<2k对该不等式取对数，有k－1≤log2n<k即log2n<k≤log2n+1由于k是整数，所以有k＝[log2n]+1。性质5对于具有n个结点的完全二叉树，如果按照从上往下和从左至右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：如果i>1，则序号为i的结点的双亲结点的序号为i/2；如果i＝1，则序号为i的结点是根结点，无双亲结点。(2)如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i的结点无左孩子。(3)如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1>n，则序号为i的结点无右孩子。二叉树的存储与基本操作

二叉树的存储

顺序存储结构

用一组连续的存储单元来存放二叉树中的结点，存储二叉树结点时一般按照从上往下、从左至右的顺序存储。

结点在存储位置上的关系能否与它们逻辑上的父子关系一一对应呢？

不一定。完全二叉树和满二叉树采用顺序存储比较合适，因为根据性质5可知，完全二叉树和满二叉树都可以通过结点的序号来找到它的双亲和孩子，唯一地反映出结点之间的逻辑关系。对于一般的二叉树，数组元素下标之间的关系并不能够反映出二叉树中结点之间的逻辑关系，此时必须增加一些并不存在的虚结点，使之演变成为一棵完全二叉树的形式一般二叉树完全二叉树(2)链式存储结构采用链表的方式来表示一棵二叉树，元素间的逻辑关系可以通过链结点的指针来指示。a二叉链表存储方式

typedefstructBTNode{datatypedata;structBTNode*lchild;*rchild;/*左右孩子指针*/}BTNode,*BiTree;b三叉链表存储方式用二叉链表来存储二叉树，找结点的左右孩子较方便，但要寻找该结点的双亲则相对比较麻烦，需要从头结点出发来顺着左右孩子指针域向下搜索。为了能方便找到双亲结点，可以设计成三叉链表的存储方式，每个结点由四个域组成:二叉树的基本操作

建立二叉树Create（root，lbt，rbt）：建立一棵以root为根结点的data域信息，以二叉树lbt和rbt分别为左右子树的二叉树：

BiTreeCreate（datatyperoot，BiTree

lbt，BiTree

rbt）

{

BiTreep;if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)returnNULL;p->data=root;p->lchild=lbt;p->rchild=rbt;returnp;}(2)作为左孩子插入二叉树InsertL（bt，e，par）：将值为e的结点插入到二叉树bt中作为结点par的左孩子结点。如果结点par原来有左孩子结点，则将结点par原来的左孩子结点作为结点e的左孩子结点：BiTreeInsertL（BiTreebt，datatypee，BiTreepar）{BiTreep;if(par==NULL){printf(“\n插入出错”)；returnNULL;}if((p=(BTNode*)malloc(sizeof(BTNode)))==NULL)returnNULL;p->data=e;p->lchild=NULL;p->rchild=NULL;if(par->lchild==NULL)par->lchild=p;else{p->lchild=par->lchild;par->lchild=p;}returnbt;}(3)删除左子树DeleteL（bt，par）：在二叉树bt中删除结点par的左子树。当par或par的左孩子结点为空时删除失败。删除成功时返回根结点指针；删除失败时返回空指针:BiTreeDeleteL（BiTreebt，BiTreepar）{/*在二叉树bt中删除结点par的左子树*/BiTreep;if(par==NULL||par->lchild==NULL){printf(“删除出错，失败”)；returnNULL’}p=par->lchild;par->lchild=NULL;if(p->lchild==null)&&(p->rchild==null)free(p);/*当p为叶子结点时，释放所删结点p的空间，*/else{……}/*当p为非叶子结点时，需要删除左子树分支中的各结点，可借助遍历操作来实现。*/returnbr;}二叉树的遍历

二叉树的遍历是指按照给定的某种顺序来依次访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。一棵二叉树由根结点、根结点的左子树和根结点的右子树三部分组成。所以，只要依次遍历完这三部分，就相当于遍历了整个二叉树。若以D、L、R分别表示根结点、左子树和右子树，按习惯限定先左后右的话，则只有三种方式，即DLR（称为前序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。

1．前序遍历（DLR）若二叉树为空，遍历结束。否则，（1）访问根结点；（2）前序遍历根结点的左子树；（3）前序遍历根结点的右子树。递归算法

voidPreOrder（BiTreebt）{if(bt==NULL)return;visite（bt->data）;PreOrder（bt->lchild）;PreOrder（bt->rchild）;}非递归算法：#definemaxsize100typedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidPreOrderUnrec(Bitreebt){SqStacks;

StackInit(s);

p=bt;

while(p!=NULL||!StackEmpty(s))

{

while(p!=NULL)

{

visite(p->data);/*访问根结点*/

push(s,p);

p=p->lchild;

/*遍历左子树*/

}

if(!StackEmpty(s))

{

p=pop(s);/*根结点出栈*/

p=p->rchild;

/*遍历右子树*/

}

}}

2．中序遍历（LDR）若二叉树为空，遍历结束。否则，（1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。递归算法：voidInOrder（BiTreebt）{if(bt==NULL)return;InOrder（bt->lchild）;visite（bt->data）;InOrder（bt->rchild）;}非递归算法:#definemaxsize100typedefstruct{

BitreeElem[maxsize];

inttop;}SqStack;voidMidOrderUnrec(Bitreebt){

SqStacks;

InitStack(s);

p=bt;

while(p!=null||!StackEmpty(s))

{

while(p!=null)

/*遍历左子树*/

{

push(s,p);

p=p->lchild;

}

if(!StackEmpty(s))

{

p=pop(s);

visite(p->data);

/*访问根结点*/

p=p->rchild;

}

}}3．后序遍历（LRD）若二叉树为空，遍历结束。否则，（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树；（3）访问根结点。递归算法：voidPostOrder（BiTreebt）{if(bt==NULL)return;PostOrder（bt->lchild）;PostOrder（bt->rchild）;visite（bt->data）;}非递归算法：#definemaxsize100typedefstruct{Bitreeptr;

intflag;}stacknode;typedefstruct{stacknodeElem[maxsize];

inttop;}SqStack;voidPostOrderUnrec(Bitreebt){SqStacks;stacknodex;StackInit(s);p=bt;while(p!=NULL||!StackEmpty(s)){if(p!=NULL)/*结点第一次进栈*/{x.ptr=p;x.flag=1;

push(s,x);p=p->lchild;/*找该结点的左孩子*/}else{x=pop(s);if(x.flag==1)/*结点第二次进栈*/{x.flag=2;/*标记第二次出栈*/p=x.ptr;push(s,x);p=p->rchild;}else{visite(p->data);/*访问该结点数据域值*/p=NULL;}}}}

4．层次遍历除了上述三种遍历方式外，还可以对二叉树进行层次遍历。即按照二叉树的层次顺序，从二叉树的第一层（根结点）开始，从上往下逐层遍历，而在同一层中，则按从左至右的顺序对结点逐个访问。遍历过程中，先访问过的结点其左右孩子也会先被访问，符合“先进先出”的特性，该特性与队列的操作特性吻合。遍历时先将根结点指针入队，然后从队列中每取一个元素，执行下述两步操作：（1）访问该元素所指结点；（2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子和右孩子结点顺序入队。重复上述两步，直至队列为空，二叉树的层次遍历结束。voidLevelOrder（BiTreebt）{BiTreeQue[MAXSIZE];intfront,rear;if(bt==NULL)return1;front=-1;rear=0;Que[rear]=bt;while(front!=rear)/*队列不为空*/

{front++;Visite(Que[front]->data);/*访问队首结点的数据域*/if(Que[front]->lchild!=NULL)/*将队首结点的左孩子结点入队列*/{rear++;Que[rear]=Que[front]->lchild;}if(Que[front]->rchild!=NULL)/*将队首结点的右孩子结点入队列*/{rear++;Que[rear]=Que[front]->rchild;}}}从遍历序列推导二叉树

若已知结点的前序遍历序列和中序遍历序列，能否确定这棵二叉树呢？二叉树的前序遍历是先访问根结点，再按前序遍历方式遍历根结点的左子树，最后按前序遍历方式遍历根结点的右子树。在前序遍历序列中，第一个结点一定是该二叉树的根结点。而中序遍历是先中序遍历左子树，然后访问根结点，最后再中序遍历右子树。在中序遍历序列中根结点会将该遍历序列分割成两个子序列，根结点之前的那一个子序列是根结点的左子树的中序遍历序列，而根结点之后的那一个子序列是根结点的右子树的中序遍历序列。对于这两个子序列，可以使用同样的方法找到左子树的根结点和右子树的根结点。左子树和右子树的根结点又可以在其对应中序遍历序列中分别把左子序列和右子序列划分成两个子序列，如此递归操作下去，便可以得到一棵二叉树。若已知结点的后序遍历序列和中序遍历序列，能否确定这棵二叉树呢？后序遍历序列的最后一个结点，与前序遍历序列的第一个结点一样也是根结点，利用它可将中序遍历序列分成两个子序列，分别为这个结点的左子树的中序遍历序列和右子树的中序遍历序列，再将左子树对应的中序遍历序列和后序遍历序列依上法继续进行分解，如此递归操作下去，便可以得到一棵二叉树。只知道二叉树的前序遍历序列和后序遍历序列，能否唯一地确定一棵二叉树呢?不可以。因为利用二叉树的前序遍历序列和后序遍历序列都只能准确找到该二叉树的根结点，至于左右子树对应的遍历序列是哪一部分则无法确定，所以也就无法唯一地确定一棵二叉树了。线索二叉树

1．线索二叉树的定义

对二叉树进行遍历，可以把二叉树中所有非线性结构结点排列出一个线性序列，直接前驱结点和直接后继结点的关系在二叉树的存储结构中并没有反映出来，只有在对二叉树遍历的过程中才能得到这些信息。

可以利用二叉树的现有二叉链表存储结构中的空指针域来指示前驱和后继，用来指向直接前驱结点和直接后继结点的指针被称为线索（thread），加了线索的二叉树称为线索二叉树。2．线索二叉树的结构

一个具有n个结点的二叉树若采用二叉链表存储结构，必有n＋1个指针域存放的都是NULL。若某结点的左孩子指针域（lchild）为空，利用它来指出该结点在某种遍历序列中的直接前驱结点的存储地址，若某结点的右孩子指针域（rchild）为空，利用它来指出该结点在某种遍历序列中的直接后继结点的存储地址；非空的指针域，仍存放指向该结点左、右孩子的指针。这样，就得到了一棵线索二叉树。为每个结点增设两个标志位域ltag和rtag，令：3线索二叉树的基本操作typedefstructBiThrNode{datatypedata;structBiThrNode*lchild;structBiThrNode*rchild;unsignedltag:1;unsignedrtag:1;}BiThrNode,*BiThrTree;(1)中序线索二叉树的建立设指针pre始终指向刚刚访问过的结点，即若指针p指向当前结点，则指针pre指向p的前驱，所以pre和p之间是一种前驱和后继的关系。在对一棵二叉树进行线索化时，首先申请一个头结点，然后建立头结点与该二叉树的根结点间的前驱后继等线索指向关系，对二叉树线索化后，再建立中序遍历的最后一个结点与头结点之间的线索指向关系。voidInThread(BiThrTreep){/*中序遍历过程中进行中序线索化*/if(p){InThread(p->lchild);/*左子树线索化*/if(!p->lchild)/*建立p的前驱线索*/{p->ltag=1;p->lchild=pre;}if(!pre->rchild)/*建立pre的后继线索*/{pre->rtag=1;pre->rchild=p;}pre=p;/*确保pre恒指向前驱*/InThread(p->rchild);/*右子树线索化*/}intInOrderThr(BiThrTree*R,BiThrTreeT){if(!(*R=(BiThrNode*)malloc(sizeof(BiThrNode))))return0;(*R)->ltag=0;(*R)->rtag=1;/*建立头结点*/(*R)->rchild=*head;/*头结点R右指针回指*/if(!T)(*R)->lchild=*R;/*若二叉树T为空，则头结点R左指针回指*/else{(*R)->lchild=T;pre=RInThread(T);/*中序遍历二叉树T进行中序线索化*/pre->rchild=*R;pre->rtag=1;/*pre指向最后一个结点，将其线索化*/(*R)->rchild=pre;}return1;}(2)查找中序前驱结点两种情况：如果该结点无左子树，那么它的左标志ltag值为1，则其左孩子指针域lchild所指向的结点便是它的前驱结点；如果该结点有左子树，那么它的左标志ltag值为0，则其左孩子指针域lchild所指向的结点是它的左孩子。BiThrTreeInPreNode（BiThrTreep）{/*在中序线索二叉树上寻找结点p的中序前驱结点*/BiThrTreepre;pre=p->lchild;if(p->ltag!=1)/*左子树存在*/while(pre->rtag==0)pre=pre->rchild;/*寻找最右结点*/returnpre;}(3）查找中序后继结点两种情况：a.如果该结点无右子树，那么它的右标志rtag值为1，则其右孩子指针域rchild所指向的结点便是它的后继结点；b.如果该结点有右子树，那么它的右标志rtag值为0，则其右孩子指针域rchild所指向的结点便是它的右孩子。BiThrTreeInPostNode（BiThrTreep）{/*在中序线索二叉树上寻找结点p的中序后继结点*/BiThrTreepost;post=p->rchild;if(p->rtag!=1)/*右子树存在*/while(post->rtag==0)post=post->lchild;/*寻找最左结点*/returnpost;}(4)查找值为e的结点BiThrTreeLocate(BiThrTreeH,datatypee){BiThrTreep;p=H->lchild;while(p->ltag==0&&p!=H)p=p->lchild;/*找到遍历的第一个结点*/while(p!=H&&p->data!=e)p=InPostNode(p);/*查找后继结点*/if(p==H){printf(“NotFoundthedata!\n”);return0;}elsereturnp;}树、森林与二叉树

树转换为二叉树

⑴加线：树中所有相邻兄弟之间加一条连线。⑵去线：对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。⑶层次调整：以根结点为轴心，将树顺时针转动45度，使之层次分明。

由树转换成的对应二叉树其特点都是没有右子树的。树的前序遍历序列与对应二叉树的前序遍历序列相同，树的后序遍历序列与对应二叉树的中序遍历序列相同。森林转换为二叉树⑴将森林中的每棵树依上述方法转换成二叉树，此时的二叉树都没有右子树；⑵从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子来处理，当所有二叉树依上法连起来后所得到的那一棵二叉树就是由森林转换得到的二叉树。

森林的遍历方式有两种：(1)前序遍历：若森林不空，则访问森林中第一棵树的根结点；前序遍历森林中第一棵树的子树森林；前序遍历森林中(除第一棵树之外)其余树构成的森林。即依次从左至右对森林中的每一棵树进行前序遍历。(2)中序遍历：若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中(除第一棵树之外)其余树构成的森林。即依次从左至右对森林中的每一棵树进行后序遍历。森林的前序遍历序列与对应二叉树的前序遍历序列相同，森林的中序遍历序列与对应二叉树的中序遍历序列相同。二叉树转换为树或森林

⑴加线：若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来；⑵去线：删去原二叉树中所有的双亲结点与右孩子结点的连线；⑶层次调整：整理由⑴、⑵两步所得到的树或森林，以根结点为轴心，将树逆时针转动45度，使之层次分明。二叉树遍历算法的应用

1查找数据元素查找数据元素操作实现时须与二叉树中各结点进行比较，为了找到各结点，可借助遍历算法来实现。查找成功时返回该结点的指针；查找失败时返回空指针。BiTreeLocate（BiTreebt，datatypee）{/*在bt为根结点指针的二叉树中查找数据元素e*/BiTreep;if(bt->data==e)returnbt;/*查找成功返回*/if(bt->lchild!=NULL)return(Locate(bt->lchild,e));

/*在bt->lchild为根结点指针的二叉树中查找数据元素e*/if(bt->rchild!=NULL)return(Locate(bt->rchild,e));

/*在bt->rchild为根结点指针的二叉树中查找数据元素e*/returnNULL;/*查找失败返回*/}2显示二叉树在屏幕上显示二叉树，需要搜索到一个结点就显示一个结点，所以可以在遍历的过程中来完成显示操作，此时的visite就是完成显示的操作。voidprinttree(Bitreebt,intn)/*从第n层开始中序遍历分层显示二叉树bt*/{inti;if(bt==NULL)return1;printtree(bt->lchild,n+1);/*中序遍历屏幕显示n+1层二叉树bt-->lchild*/for(i=0;i<n-1;++i)/*光标移过前n-1层*/printf(“”);if(n>=1)printf(“---”);/*屏幕显示第n层连接线*/printf(“%d\n”,bt->data);/*显示第n层数据域值*/printtree(bt->rchild,n+1);/*中序遍历屏幕显示n+1层二叉树bt-->rchild*/}3统计叶子结点数目要统计二叉树中叶子结点的数目，可以先分别计算出二叉树的左子树和右子树上的叶子结点数量，相加后即得。同样可以用遍历的思想来辅助实现。intCountLeaf（BiTreebt）{intcount;if(bt==NULL)return0;if(bt->lchild==NULL&&bt->rchild==NULL)return1;count=CountLeaf(bt->lchild)+CountLeaf(bt->rchild);returncount;}4求二叉树深度二叉树的深度是在求出其左右子树的深度后取两者间的最大值，然后考虑到还有根结点这一层，所以再加上1即得。因此必须先求出左右子树的深度，再考虑根这一层，与后序遍历的思想非常类似。5创建二叉树二叉树的创建同样可以参考遍历算法来实现。若以前序的方式来创建二叉树，可以按二叉树的前序遍历序列次序输入结点值，结点值类型为字符型。该次序中涉及到的每个有效结点都要看成有左右孩子的。所以如果某结点无左或右孩子，那么对应于它的左或右孩子要以特殊符号‘#’表示，并且要按对应遍历次序序出现在遍历序列中。

voidCreateBinTree(BiTreebt){/*按加入结点的前序遍历序列输入，构造二叉链表*/charch;scanf("\n%c",&ch);if(ch=='#')bt=NULL;else{bt=(BTNode*)malloc(sizeof(BTNode));

bt->data=ch; CreateBinTree(bt->lchild);CreateBinTree(bt->rchild); }}哈夫曼树

给定n个权值作为n个叶子结点，构造一棵二叉树，若该棵二叉树带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。1基本概念

路径和路径长度:在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

结点的权:若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。如果二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应叶结点权值的乘积之和叫做二叉树的带权路径长度，记为：

给4个叶结点，其权值分别为2，4，6，8，可以构造出形状不同的多棵二叉树。其带权路径长度WPL各不相同：

WPL＝2×2＋4×2＋6×2＋8×2＝40

WPL＝2×3＋4×3＋6×2＋8×1＝38WPL＝8×3＋6×3＋4×2＋2×1＝52

具有相同权值的一组叶子结点，但所构成的二叉树可以有不同的形态和不同的带权路径长度

一棵二叉树如果想要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，从而缩短它的路径长度，而权值越小的叶结点越远离根结点，虽然路径长度增加了，但因为结点权值小，对总的带权路径长度的影响不大。构造算法（1）由给定的n个权值{w1，w2，…，wn}构造n棵只有一个结点的二叉树，该结点既是根结点，也是叶子结点，从而得到一个二叉树的集合F＝{T1，T2，…，Tn}；（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树（不约定顺序）构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；（3）在集合F中删除作为左、右子树的两棵二叉树，并将新构造的二叉树加入到集合F中，F中二叉树的数量减少了一棵；（4）重复（2）（3）两步，当F中最终只剩下一棵二叉树时，这棵二叉树便是所要构造的哈夫曼树。设置一个结构体数组HuffmanNode保存哈夫曼树中各结点的信息，大小设置为2n－1，数组元素的结构如下：weight域保存该结点的权值；lchild和rchild域分别保存该结点的左、右孩子结点在数组中的序号；parent域保存其双亲结点在数组中的序号，某结点的parent域的值不是-1，就表示该结点已加入哈夫曼树；

#defineMAXWeight10000#defineMAXLeaf40#defineMAXNodeMAXLeaf*2-1typedefstruct{intweight;intparent;intlchild;intrchild;}HNode;voidHuffmanTree(HNodeHuffmanNode[]){inti,j,a1,a2,b1,b2,n;scanf(“%d”,&n);for(i=0;i<2*n-1;i++){HuffmanNode[i].weight=0;HuffmanNode[i].parent=-1;HuffmanNode[i].lchild=-1;HuffmanNode[i].rchild=-1;}for(i=0;i<n;i++)scanf(“%d”,&HuffmanNode[i].weight);for(i=0;i<n-1;i++)