第6章树和二叉树6.1 知识点概述树（Tree）形结构是一种很重要的非线性结构，它反映了数据元素之间的层次关系和分支关系。
在计算机科学中具有广泛的应用。
1、树的定义树（Tree）是n（n≥0）个数据元素的有限集合。
当n＝0时，称这棵树为空树。
在一棵非空树T中：（1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。
（2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。
树T1，T2，…，Tm称为这个根结点的子树。
2、树的基本存储结构（1）双亲表示法由于树中的每一个结点都有一个唯一确定的双亲结点，所以我们可用一组连续的存储空间（即一维数组）存储树中的结点。
每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。
（2）孩子表示法将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。
（3）双亲孩子表示法双亲表示法是将双亲表示法和孩子表示法相结合的结果。
其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。
（4）孩子兄弟表示法这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。
链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。
3、二叉树的定义二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。
当集合为空时，称该二叉树为空二叉树。
在二叉树中，一个元素也称作一个结点。
4、满二叉树定义：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。
5、完全二叉树定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。
6、二叉树的性质性质1 一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。
性质2 一棵深度为k的二叉树中，最多具有2k－1个结点。
性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有： n0＝n2＋1性质4 具有n个结点的完全二叉树的深度k为[log2n]+1。
性质5 对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：1）如果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的结点无右孩子。
7、二叉树的存储结构顺序存储结构和链式存储结构。
（1）顺序存储结构所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。
一般是按照二叉树结点从上至下、从左到右的顺序存储。
（2）链式存储结构所谓二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。
二叉树的链式存储结构通常有下面两种形式。
1）二叉链表存储链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。
2）三叉链表存储每个结点由四个域组成， data、lchild、rchild和parent其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。
这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。
8、二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。
三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。
9、树和二叉树的基本操作：初始化、求根函数、求双亲函数、求孩子结点函数、插入子树操作、删除子树操作、遍历操作等。
10、线索二叉树为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。
这些指向直接前驱结点和指向直接后继结点的指针被称为线索（thread），加了线索的二叉树称为线索二叉树。
11、哈夫曼树（1）哈夫曼树的基本概念最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。
构造哈夫曼树基本思想是：1）由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，…，Tn}；2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F 中；4）重复2）3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
6.2 二叉树的基本操作及应用一、实验目的1、掌握二叉树的存储结构2、掌握二叉树的遍历操作的实现方法3、掌握递归方法能够编写相应的程序解决二叉树应用4、掌握建立Huffman树及求Huffman编码的操作，加深对二叉树应用的理解二、实验内容（一）验证实验1、已知二叉树用下面的顺序结构存储＃define Max=20struct nodes{char data; //存结点值int lc,rc; //存左右孩子下标，0表示无左、右孩子}A[Max];2、写出前序、中序和后序遍历该二叉树的算法。
①用非递归法实现二叉树的遍历非递归算法中，必须设置堆栈，可以直接用一维数组来代替栈，但必须另外设置栈顶指针。
（二）设计实验1、用非递归法实现二叉树的三种遍历非递归算法中，必须设置堆栈，可以直接用一维数组来代替栈，但必须另外设置栈顶指针。
void preorderl(bitree *root) //先序遍历{bitree *p，*s[100]；//s为堆栈int top=0；//top为栈顶指针p=root；while((p!=NULL)||(top>0)){ while(p!=NULL){cout<<p->data<<””；s[++top]=p；//进栈p=p->lchild；}p=s[top--]；//退栈p=p->rchild；}}void inorderl(bitree*root) //中序遍历{bitree*p，*s[100]；int top=0；p=root；while((p!=NULL)Il(top>O)){ while(p!=NULL){s[++top]=p；p=p->lchild；}{p=s[top--]；cout<<p->data<<“”；p=p－>rchild；｝｝｝void postorderl( bitree *root) //后序遍历(bitree *p *sl[100]；int s2[100]，top=0，b；p=root；do{while(p!=NULL){s1[top]=p；s2[top++]=0；p=p->lchild；)if(top>0)(b=s2[--top]；p=s1[top]；if(b==0){sl[top]=p；s2[top++]=l；p=p->rchild；}else{cout<<p->data<<””;p=NULL；} }}while(top>0)；}2、实现二叉树的层次遍历用一个一维数组代替队列，实现二叉树的层次遍历。
#include<iostream.h>typedef char elemtype；struct bitree{elemtype data；//结点信息bitree *lchild，*rchild；//左右孩子};//按层次遍历二叉树(建立二叉链表同前)void lorder(bitree *t){ bitree q[100]，*p；//q代表队列int f,r; //f，r类似于队列头、尾指针q[1]=t；f=r=l；cout<<”按层次遍历二叉树的结果为：”;while if<==r){ p=q[f]；f++；//出队cout<<p->data<<””;if(P->lchild!=NULL){ r++；q[r]=p->lchild；} //入队if p->rchild!=NULLl．{ r++；q[r]=p->rchild;} //入队}cout<<endl；}void main(){bitree *t；t=create0；//需要自己设计该函数，建立二叉链表lorder(t)；//：按层次遍历二叉树}3、根据Huffman编码原理，编写一个在用户输入结点权重的基础上建立的Huffman编码程序。
程序设计思路：构造一棵Huffman树，由此得到的二进制前缀便为Huffman编码由于Huffman树没有度为1的结点，则一棵有n 个叶子结点的Huffman树共有2n-1个结点，设计一个结构数组，存储2n-1个结点的值，包括权重、父结点、左结点和右结点等参考程序：#include <stdio.h>#define MAX 21typedef struct{char data;int weight;int parent;int left;int right;}HuffNode;typedef struct{char cd[MAX];int start;}HuffCode;void main(){HuffNode ht[2*MAX];HuffCode hcd[MAX],d;int i,k,f,j,r,n=0,c,m1,m2;printf("请输入元素个数(1->%d):",MAX-1); scanf("%d",&n);if(n>MAX-1||n<1)return;for(i=0;I<n;I++){printf("第%d个元素=>\n\t结点值:",i+1); scanf("%c",&ht[i].data);printf("\t权重:");scanf("%d",&ht[i].weight);}for(i=0;i<2*n+1;i++)ht[i].parent=ht[i].left=ht[i].right=0;for(i=n;i<2*n-1;i++){m1=m2=0x7fff;j=r=0;for(k=0;k<i;k++)if(ht[k].parent==0)if(ht[k].weight<m1){m2=m1;r=j;m1=ht[k].weight;j=k;}else if(ht[k].weight<m2){m2=ht[k].weight;r=k;}ht[j].parent=i;ht[r].parent=i;ht[i].weight=ht[j].weight+ht[r].weight;ht[i].left=j;ht[i].right=r;}for(i=0;I<n;I++){d.start=n;c=i;f=ht[i].parent;while(f!=0){if(ht[f].left==c)d.cd[--d.start]='0';elsed.cd[--d.start]='1';c=f;f=ht[f].parent;}hcd[i]=d;}printf("输出Huffman编码:\n");for(i=0;i<n;i++){printf("%c:",ht[i].data);for(k=hcd[i].start;k<n;k++)printf("%c",hcd[i].cd[k]);printf("\n");}}实验结果：元素个数：6第一个元素a：权重：7第二个元素b：权重：9第三个元素c：权重：12第四个元素d：权重：22第五个元素e：权重：23第六个元素f：权重：27输出Huffman编码：a:1110b:1111c:110d:00e:01f:10三、思考题1、如何把二叉树的递归算法改为非递归算法2、结合二叉树的遍历，实现统计一颗二叉树的结点数的函数6.3 小结掌握二叉树的存储结构，掌握二叉树的三种遍历操作的实现方法，掌握哈夫曼树的构造方法，能够编写相应的程序解决实际问题。