第六章 二叉树和树 6.1树的基本概念 6.2二叉树 6.3二叉树遍历 6.4线索二叉树 6.5树和森林 6.6树的应用（霍夫曼树及其编码）

6.1树的基本概念 6.1.1树的定义见6.5

6.2二叉树 6.2.1二叉树的定义和基本术语 二叉树（binary Tree） 二叉树的元素又称结点 左孩子，右孩子，父亲，兄弟，堂兄弟，祖先，子孙 结点的度：非空子树的个数 叶子结点：左右子树均空的结点；度为零 层次：根的层次为1，层次为k的结点其孩子层次为k+1 二叉树的深度：二叉树中叶子结点的最大层次数

满二叉树（full binary tree）：所有结点度为2，叶子结点在同一层次 完全二叉树（complete binary tree）：深度h，h-1为满二叉树，h层的结点都集中在左侧 二叉树的基本操作 InitBiTree(&T) DestroyBiTree(&T) CreateBiTree(&T,definition) BiTreeEmpty(T) BiTreeDepth(T) Parent(T,e) LeftChild(T,e) RightChild(T,e) LeftSibling(T,e) RightSibling(T,e) InsertChild(T,p,LR,C) DeleteChild(T,p,LR) Traverse(T)

6.2.2二叉树的几个基本性质 性质1 在二叉树的第i层的结点个数最多 2 (i-1) 性质2 深度为k 的二叉树的最大结点数为2k-1 性质3 任一二叉树T，如果其叶子结点数为n0， 度为2的结点数为n2，则n0=n2+1 n0+n1+n2=n=2n2+n1+1 性质4 具有n个结点的完全二叉树深度为[logn]+1

性质5 如果对一个有n个结点的完全二叉树T的结点按层序（从第一层到第[logn]+1层，层内从左到右）从1开始编号，则对任意一个编号为i(1<=i<=n)的结点有： 如果i＝1，则该结点是二叉树的根，无双亲；如果i>1，，则其双亲结点Parent(i)的编号为[i/2] 如果2i>n，则编号为i 的结点没有左孩子，为叶子结点；否则其左孩子LChild(i)的编号为2i 如果2i+1>n，则编号为i 的结点没有右孩子；否则其右孩子RChild(i)的编号为2i+1

6.2.3二叉树的存储结构 顺序存储结构 Const MAXSIZE＝100 typedef struct{ ElemType *data; int nodenum; }SqBiTree

链式存储结构 二叉链表 包涵data，lchild，rchild三个域，找父亲必须从根开始 三叉链表 包涵data，lchild，rchild，parent四个域，找父亲容易       typedef BiTNode{ ElemType data; struct BiTNode *lchild,*rchild[,*parent]; }BiTNode,*BiTree;

6.3二叉树遍历 6.3.1问题的提出 二叉树遍历 对所有结点进行访问，且仅被访问一次 LDR、LRD、DLR、DRL、RLD、RDL六种次序 先序（根）DLR、中序（根）LDR、后序（根）LRD 例：右图得三种遍历序列 先序遍历：ABDEC 中序遍历：DBEAC 后序遍历：DEBCA A B C D E

6.3.2遍历算法的描述 算法 递归实现 算法 非递归实现 算法 递归实现 void preorder(BiTree T,void (* visit)(BiTree)) 算法 非递归实现 typedef enum {Travel=1,Visit=0} TaskType; typedef struct { BiTree ptr; TaskType task; }SElemType; void InOrder_iter (BiTree BT,void (* visit)(BiTree)) 用栈实现遍历

非递归实现 e.ptr=p->rchild;e.task=Travel;Push(s,e); Void InOrder(BiTree BT,void (*visit)(BiTree T)){ InitStack(S); e.ptr=BT;e.task=travel; if(BT)push(S,e); while(!StackEmpty(S)){ Pop(S,e); if(e.task=Visit) visit(e.ptr); else if(e.ptr){ p=e.ptr; e.ptr=p->rchild;e.task=Travel;Push(s,e); e.ptr=p;e.task=Visit;Push(s,e); e.ptr=p->lchild;e.task=Travel;Push(s,e); }//if }//while }//InOrder

算法6.4可以实现后序遍历吗？ typedef strunct {BiTree T; int flag;} SElemType ; Void postorder(BiTree){ InitStack(S); while(T||!StackEmpty(S)){ while(T){ //左子树 e=(T,0);Push(S,e);T=T->lchild; } if(!StackEmpty(S)){pop(S,e); //回溯 if(e.flag==0){e.flag=1;Push(S,e); T=e.T->rchild;} if(e.flag==1){visit(T->data);T=NULL;}

6.3.3二叉树应用举例 例 建立二叉树的存储结构(先序扩展二叉树序列) void CreateBiTree(BiTree &T) 递归 先序 { cin>>ch; if（ch==‘#’)T=NULL; else{ T=new BiTNode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }

例 复制二叉树 递归算法 后序 Bitree CopyTree(BiTree T){ if(!T)return NTLL; 例 复制二叉树 递归算法 后序 Bitree CopyTree(BiTree T){ if(!T)return NTLL; newlp=CopyTree(T->lchild); newrp=CopyTree(T->rchild); newnode=new BiTNode; newnode->data=T->data; newnode->lchild=newlp; newnode->rchild=newrp; return newnode; }

例 求二叉树的结点数和叶子结点数 （先序） void Count(BiTree T,int &C1, int &C2) { if(!T)return; C1++; if(T->lchild==NULL && T->rchild==NULL)C2++; count(T->lchild,C1,C2); count(T->rchild,C1,C2); }

例6.2输出二叉树每个结点的层次数 void level(BiTree,int lev){ //lev=1调用 if(!T) return; cout<<T->data<<“:”<<lev<<endl; level(T->lchild,lev+1); level(T->rchild,lev+1); } void numb(BiTree,int &lev){ //对比 输出的还是层次吗？ lev++; numb (T->lchild,lev); numb (T->rchild,lev);

例6.3求二叉树的深度 递归算法 例6.5求存于二叉树中的数学表达式的值 int Depth(BiTree T) 后序 例6.3求二叉树的深度 递归算法 int Depth(BiTree T) 后序 void Depth2(BiTree T,int h,int &depth)先序 { if(!T) return; if(h>depth)depth=h; Depth2(T->lchild,h+1,depth); Depth2(T->rchild,h+1,depth); } 例6.5求存于二叉树中的数学表达式的值 算法6.10 double Calculate(BiTree ) 单目运算符有问题吗？ -a+b*(c-d)-(-f)

6.4线索二叉树 在二叉链表的结点中增加两个指针域，分别指向“前驱”和“后继”，该指针称线索。加上线索的二叉树成为线索二叉树 typedef BiTHrNode{ ElemType data; struct BiTHrNode *lchild,*rchild; struct BiTHrNode *pred,*succ; }BiTHrNode,*BiThrTree;

线索二叉树的遍历 Void InOrder(BiThrTree H,void (* visit)(BiTree)) p=H->succ; while(p!=H) { visit(p); p=p->next; }

线索二叉树的中序建立 Void InOrderThreading(BiThrTree &H, BiThrTree T){ H=new BiThrNode; H->lchild=T;H->rchild=NULL; if(!T){H->pred=H->succ=H;} else{ pre=H; InThreading(T,pre); pre->succ=H;H->pred=pre; } }//InOrderThreading

Void InThreading(BiThrTree p, BiThrTree &pre) { //p是当前指针，pre是跟随指针，比p慢一个结点 if(!p) return; Inthreading(p->lchild,pre); pre->succ=p; p->pred=pre; pre=p; Inthreading(p->rchild,pre); } //InThreading

6.5树和森林 6.5.1树和森林的定义 树的定义 （无序树） 森林的定义 n(n>=0)个数据元素（结点）的有限集D，若D为空集，则为空树。否则： 在D中存在唯一的称为根的数据元素 当n>1时，其余结点可分为m（m>0）个互不相交的有限子集T1，T2，......，Tm，其中每个子集本身又是一颗树，并成为根的子树 森林的定义 是m(m>=0)颗互不相交的树的集合

树的基本操作： InitTree（&T） DestroyTree（&T） CreateTree(&T,definition) TreeEmpty(T) TreeDepth(T) Parent(T, e) LeftChild（T，e） Rightsibling(T,e) InsertChild（&T,&p,i,C） DeleteChild（&T,&p,i） Traverse（T）

6.5.2 树和森林的存储结构 1、双亲表示法 Const MAX_TREE_SIZE=100 typedef struct PTNode{ Elem data; int parent; }PTNode; typedef struct { PTNode nodes[MAX_TREE_SIZE]; int r,n; }PTree; 例：前图的双亲存储示意图 r=0 n=11

data parent A -1 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K A B C D E F A -1 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K A B C D E F G H I J K

2、孩子表示法 1)孩子链表示法 例：前图孩子链表示，r=0,n=11 typedef struct CTNode{ int child; struct CTNode *next; }CTNode,*Childptr; typedef struct { Elem data; Childptr firstchild; }CTBox; CTBox nodes[MAX_TREE_SIZE]; int n,r; }CTree; 例：前图孩子链表示，r=0,n=11

data pare A 1 B 2 C ^ 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K 1 2 3 ^ 4 5 6 ^ A B C D E F G H I J K 7 8 ^ 9 10 ^

2）树的多重链表表示法 typedef struct TNode{ Elem data; struct TNode *child[MAX_NODE]; }TNode,*Tree; 3、孩子双亲表示法 结合了双亲表示法和孩子链表示法 4、树的二叉链表（孩子－兄弟）表示法 typedef struct CSNode{ struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree;

A A B C D E F G H I J K B E C D F J G H I K

树与二叉树的变换 以树的结点为二叉树结点 树根与最左子树的父－子关系改为父－左子关系，去除根与其他子树的父－子关系 将其他各子树根（除最右子树）到其右兄弟之间的隐含关系以父－右子关系表示。 对于无右子树的二叉树可以实施逆变换

森林到二叉树的变换：F(T1,T2.....Tn)-> B 若森林F空，则二叉树B空。 由森林中的第一颗树的根结点ROOT（T1）作为二叉树的根，其子树转换为二叉树的左子树。 由森林中其余树构成的森林{T2，T3......Tn}转化得到的二叉树B的右子树 二叉树到森林的变换：B -> F（T1，T2......Tn） 若二叉树B空，则森林F空。 二叉树的根为森林中的第一颗树的根结点ROOT（T1），二叉树的左子树转化为T1的子树 二叉树的右子树转化为森林{T2，T3......Tn}

6.5.3 树和森林的遍历 树遍历的三种搜索路径（右图） 对森林遍历的两种方法：（右图） 先根次序遍历 ABCEHDFG 后根次序遍历 BHECFGDA 按层次序遍历 ABCDEFGH 对森林遍历的两种方法：（右图） 先序遍历：(ABCDEFGHIJ) 若森林非空 访问森林中的第一颗树根结点 先序遍历第一颗树中根结点的子树森林 先序遍历除去第一颗树之后剩余树构成的森林 中序遍历：(BCDAFEHJIG) 若森林非空 中序遍历第一颗树中根结点的子树森林 中序遍历除去第一颗树之后剩余树构成的森林 A B C D E F G H A B C D E F G H I J

树的先根遍历和后根遍历可利用二叉树的先序和中序遍历算法实现 森林的先序遍历和中序遍历即是对应二叉树的先序和中序遍历

例求森林的深度 int TreeDepth(CsTree T) 后序 { if(!T)return 0; h1=TreeDepth(T->firstchild); h2=TreeDepth(T->nextsibling); return (h1+1>h2)?h1+1:h2; }

递归用来遍历左分支，即真正的孩子 while循环用来遍历右分支几兄弟 栈底到栈顶为一条路径 例 输出树中从根结点到所有叶子结点的路径 void OutPath(CSTree T,Stack &S) { while(T){ Push(S,T->data); if(!T->firstchild)StackTraverse(S); else OutPath(T->firstchild,S); Pop(S,e); T=T->nextsibling; } 递归用来遍历左分支，即真正的孩子 while循环用来遍历右分支几兄弟 栈底到栈顶为一条路径

例 建立树的存储结构――孩子－兄弟链表 void CreateTree(CSTree T) { T=NULL; for(cin>>fa>>ch;ch!=‘#’;cin>>fa>>ch){ p=new CSNode; p->data=ch;p->firstchild=p->nextsibling=NULL; EnQueue(Q,p); if(fa==‘#’)T=p; else{ while(GetHead(Q,s) && s->data!=fa){DeQueue(Q,s);} if(!s->firstchild){s->firstchild=p;r=p;}; else{r->nextsibling=p;r=p;} }//else }//for } //CreateTree

6.6树的应用 6.6.1堆排序的实现 排序的实现： typedef SqTable HeapType; 调整为堆 ，从结点[n/2]到1依次调整 交换数据，再调整堆顶元素，恢复成堆 typedef SqTable HeapType; void HeapAdjust(HeapType &H,int s,int m) 调整H.r[s..m]为大顶堆,其中仅H.r[s]不满足大顶堆条件 void HeapSort(HeapType &H) 从结点[n/2]到1依次调整，使H为大顶堆 交换堆顶与堆底记录，再利用HeapAdjust重新调整为堆 重复进行第二步，直到所有元素有序

void HeapAdjust(HeapType &H,int s,int m){ //调整H.r[s..m]为大顶堆,其中仅H.r[s]不满足条件 rc=H.r[s]; for(j=2*s;j<=m;j*=2){ if(j<m && H.r[j].key<H.r[j+1].key)++j; if(rc>=H.r[j].key)break; H.r[s]=H.r[j];s=j; }//for H.r[s]=rc; }

堆排序 void HeapSort(HeapType &H){ for(i=H.length/2;i>0;--i) HeapAdjust(H,i,H.length); w=H.r[1];H.r[1]=H.r[H.length];H.r[H.length]=w; for(i=H.length-1;i>1;--i){ //i为2交换后无需调整 HeapAdjust(H,1,i); w=H.r[1];H.r[1]=H.r[i];H.r[i]=w; }//for }//HeapSort

6.6.2二叉排序树 二叉排序树定义： 或空树，或满足如下特征 若左子树不空，则左子树上的所有结点值均小于根结点值 若右子树不空，则右子树上的所有结点值均大于或等于根结点值 左右子树分别也是二叉排序树 typedef TelemType RcdType; typedef KeyType int; void Insert_BST(BiTree &T, TElemType e) 在二叉排序树中插入一个结点

void Insert_BST(BiTree &T, TElemType e) { s=new BiTNode; s->data=e;s->lchild=s->rchild=NULL; if(!T)T=s; //第一个结点 else{ p=T; while(p) if(e.key<p->data.key){f=p;p=p->lchild;} else {f=p;p=p->rchild;} if(e.key<f->data.key)f->lchild=s; else f->rchild=s; }//else }

利用二叉排序树排序 void BSTSort(SqTable &L) { BiTree=NULL; for(i=1;i<L.length;i++); Insert_BST(T,L.r[i]); i=1; InOrder(T,Output(T,L,i)); } //BSTSort Void Output(BiTree T,SqTable L,int &i){ L.r[i++]=T->data; }

补充：求排序二叉树的最大元素 keytype getmax(BiTree &T) { if(!T) errormessage(“NULL Tree,Can’t get value!”); return -1; } p=T; while(p->rchild)p=p->rchild; return p->data.key;

6.6.3霍夫曼(huffman)树及其应用 路径：树中一个结点到另一结点之间的分支 路径长度：路径上分支的数目 树的路径长度：树根到每个结点的路径长度之和 结点带权路径长度：从树根到该结点之间的路径长度与该结点上所带权值的乘积 树的带权路径长度：WPL＝Σωklk (叶子结点) 最优二叉树（霍夫曼树）: n个叶子构成的所有二叉树中，其中WPL最小的二叉树称霍夫曼树。

例 将百分制转换为五分制 分数 0~59 60~69 70~79 80~89 90~100 比例 0.05 0.15 0.40 0.30 0.10 <60 <80 不及 <70 <70 <90 及格 <80 <60 中 良 优 中 <90 不及 及格 良 优 10000个输入数据，左图需要判断31500次，右图为22000次

霍夫曼树算法 1)根据给定的n个权值{w1,w2......wn}，构成n颗二叉树的集合F＝{T1,T2......Tn}，每个二叉树只有一个带权Wi的根结点。 2)在F中选取两颗根结点的权值最小的树作为左右子树，构造一个新二叉树，且置其根结点的权值为两个子树根结点权值之和。 3)在F中删除这两颗树，同时在F中加入新树。 4)重复2）、3）直至F只含一颗树为止

霍夫曼树存储结构 创建霍夫曼树 typedef struct{ int weight; int parent,lchild,rchild; }HTNode; typedef HTNode *HuffmanTree; 创建霍夫曼树 void CreateHuffman(HuffmanTree &HT, int *w,int n)

例 有8个字符a、b、c、d、e、f、g、h，出现频率为5%、29%、7%、8%、14%、23%、3%、11%，设计霍夫曼编码 前缀编码： 任一字符的编码都不是另一字符编码的前缀 霍夫曼编码： 以n种字符出现的概率（频率）为权，设计一个赫夫曼树，由此得到的二进制前缀编码 例 有8个字符a、b、c、d、e、f、g、h，出现频率为5%、29%、7%、8%、14%、23%、3%、11%，设计霍夫曼编码 先序遍历 void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC, int n)