第六树和二叉树

会计学1第六树和二叉树思考

你见过家族谱系图吗？试以图形表示从你的祖父起的家族成员关系。侄儿伯父父亲叔父堂兄堂姐自己堂弟祖父用关系表示的家族谱系图<祖父，伯父>，<祖父，父亲>，

<祖父，叔父>，<伯父，堂兄>，

<伯父，堂姐>，<父亲，自己>，

<叔父，堂弟>，<堂兄，侄儿>第1页/共110页

树型结构是一类重要的非线性结构，是以分支关系定义的层次结构。第2页/共110页IndexRootChildernnode1中国河南2中国北京3中国广东IndexRootChildernnode1北京通州2河南郑州3河南开封4广东深圳5广东广州IndexRootChildernnode1深圳宝安区2深圳沙田区3郑州金水区4郑州二七区中国河南北京广东开封郑州深圳广州金水二七宝安沙田第3页/共110页树的抽象数据类型定义ADTTree{

数据对象：D是具有相同特性的数据元素的集合。

数据关系：

若D为空集，则称为空树；

若D中仅含一个数据元素，则关系R为空集；

否则R={H}，

(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；

(2)当n>1时，其余数据元素可分为m(m>0)个互不相交的(非空)

有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根root的子树，每一棵子树的根xi都是根root

的后继，即<root,xi>∈H,i=1,2,…,m第4页/共110页在这13个数据元素之间存在下列关系：R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,

<D,H>,<D,I>,<D,J>,<F,K>,<F,L>,<J,M>}第5页/共110页树结构的表现形式嵌套集合表示法凹入表表示法：类似于目录形式广义表表示法：（A,(B,(C),(D),(E)),(F,(G),(H))）图形表示法：ACDEFBGH第6页/共110页基本术语

分支：根和子树根之间的连线

结点：一个数据元素及若干指向其子树的分支

结点的度：结点拥有的子树个数

叶子(终端结点)：度为0的结点

非终端结点(分支结点)：度不为0的结点

树的度：树内各结点度的最大值

孩子：指结点的子树的根,相应的,该结点称为孩子的双亲

兄弟：同一双亲的孩子之间互称兄弟

祖先：一个结点的祖先指从根到该结点所经分支上的所有结点

AIDBEHCFGKJ第7页/共110页子孙：以某结点为根的子树中的任一结点都称为该结点的子孙结点的层次：令根为第一层，根的孩子为第二层。若某结点 处在第l层，其子树的根就在l+1层。堂兄弟：双亲在同一层的结点互称堂兄弟树的深度：指树中结点的最大层次有序树：树中结点的各子树从左至右有序（即不能互换）， 否则称为无序树森林：指m(m≥0)棵互不相交的树的集合AIDBEHCFGKJ第8页/共110页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结点F，G为堂兄弟结点A是结点F，G的祖先第9页/共110页基本操作：

{结构初始化}

InitTree(&T); //构造空树T

CreateTree(&T,definition); //按definition构造树T

{销毁结构}

DestroyTree(&T); //销毁树T

第10页/共110页{引用型操作}TreeEmpty(T); //若T为空树，则返回TRUE，否则返回FALSE

TreeDepth(T);//返回T的深度

Root(T);//返回T的根

Value(T,cur_e);//返回cur_e的值

Parent(T,cur_e);//若cur_e是T的非根结点，则返回它的双亲，否则返回"空"。

LeftChild(T,cur_e);//若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回"空"

RightSibling(T,cur_e);//若cur_e有右兄弟，则返回它的右兄弟，否则返回"空"

TraverseTree(T,visit());//按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦

//visit()失败，则操作失败。 第11页/共110页{加工型操作}

Assign(T,cur_e,value); //结点cur_e赋值为value ClearTree(&T);

//将树T清为空树

InsertChild(&T,&p,i,c);

//插入c为T中p所指结点的第i棵子树

DeleteChild(&T,&p,i); //删除T中p所指结点的第i棵子树}ADTTree

第12页/共110页线性结构树结构存在唯一的没有前驱的"首元素"存在唯一的没有前驱的"根结点"存在唯一的没有后继的"尾元素"存在多个没有后继的"叶子"其余元素均存在唯一的"前驱元素"和唯一的"后继元素"其余结点均存在唯一的"前驱(双亲)结点"和多个"后继(孩子)结点"线性结构和树结构中数据元素之间关系对比表第13页/共110页二叉树的类型定义ADTBinaryTree{

数据对象：D是具有相同特性的数据元素的集合。

数据关系：

若D为空集，称BinaryTree为空二叉树；否则关系

R={H}：

(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；

(2)D中其余元素必可分为两个互不相交的子集L和

R，每一个子集都是一棵符合本定义的二叉树，并分别为root的左子树和右子树,如果左子树L不空,则必存在一个根结点xl,它是root的”左后继”,如果右子树R

不空,则必存在一个根结点xr,它是root的”右后继”第14页/共110页第15页/共110页基本操作P：{结构初始化} InitBiTree(&T);//构造空二叉树T CreateBiTree(&T,definition); //按definition构造二叉树T{销毁结构} DestroyBiTree(&T);//销毁二叉树T

第16页/共110页{引用型操作} BiTreeEmpty(T); BiTreeDepth(T); Root(T); Value(T,e); Parent(T,e); LeftChild(T,e);

RightChild(T,e); LeftSibling(T,e); RightSibling(T,e); PreOrderTraverse(T,visit()); //先序遍历T，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败

InOrderTraverse(T,vsit()); //中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败

PostOrderTraverse(T,visit()); //后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败

LevelOrderTraverse(T,visit()); //层序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败第17页/共110页{加工型操作} ClearBiTree(&T);

//将二叉树T清为空树

Assign(&T,&e,value);

//结点e赋值为value InsertChild(&T,p,LR,c);

//根据LR为0或1，插入c为T中p所指结点的左或右

//子树。p所指结点原有左或右子树成为c的右子树

DeleteChild(&T,p,LR); //根据LR为0或1，删除T中p所指结点的左或右子树}ADTBinaryTree第18页/共110页二叉树和树是两种不同的树型结构，二叉树不等同于度为2的有序树。

Why?第19页/共110页具有三个结点的树的棵数：ACBCBA具有三个结点的二叉树的棵数：ACBCBACBACBACBA第20页/共110页二叉树的五种形态空树，结点数为0单节点二叉树，只有一个结点左子树为空，右子树不空右子树为空，左子树不空左右子树均不空第21页/共110页二叉树的几个特性一、在二叉树的第i层上至多有2i-1

个结点(i≥1)二、深度为k的二叉树中至多含有2k-1个结点，

(k≥1)。三、对任何一棵二叉树T，如果其终端结点数为

n0，度为2的结点数为n2，则：

n0=n2+1

第22页/共110页证明：

由于二叉树中只有三种结点，假设n1为二叉树T

中度为1的结点数，则二叉树中结点总数为

n=n0+n1+n2

①

再看二叉树中的分支数目。除了根结点外，其余结点都有一个分支进入，假设B为分支数，则

n=B+1。从另一角度看，这些分支是由度为1或2

的结点射出的，所以又有

B=n1+2n2

即n=n1+2n2+1②

综合以上①和②两个等式便可得到

n0=n2+1第23页/共110页思考：若一棵树的度为4，其中，度为1的结点有4个，度为2的结点有2个，度为3的结点有1个，度为4的结点有1个，则该树中叶子有多少个？第24页/共110页两种特殊形式的二叉树若二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。

对满二叉树从上到下从左到右进行从1开始的编号，则任意一棵二叉树都可以和同深度的满二叉树对比

第25页/共110页假如一棵包含n个结点的二叉树中每个结点都可以和满二叉树中编号为1至n的结点一一对应，则称这类二叉树为完全二叉树。在满二叉树的最下层从右到左连续地删除若干个结点所得到的二叉树。显然一棵深度为h的完全二叉树中，前h-1层中的结点都是“满”的。满二叉树本身也是完全二叉树。第26页/共110页1231145891213671014151231145891267101234567123456第27页/共110页二叉树的几个特性四、具有n个结点的完全二叉树的深度为五、如果对一棵有n个结点的完全二叉树的结点按层序从1

开始编号，则对任一编号为i的结点(1≤i≤n)，有：

(1)如果i=1，则编号为i的结点是二叉树的根；如果

i>1，则其双亲结点parent(i)的编号是

(2)如果2i>n，则编号为i的结点无左孩子（编号为i的结点为叶子结点）；否则其左孩子结点lChild(i)的编号是2i。

(3)如果2i+1>n，则编号为i的结点无右孩子；否则其右孩子结点rChild(i)的编号是结点2i+1。第28页/共110页二叉树的存储结构----顺序存储结构用一组地址连续的存储单元存储二叉树中的数据元素

二叉树的顺序存储结构的定义如下：

constMAXSIZE=100;

//定义二叉树中结点数的最大值为100

typedefstruct

{

ElemType*data;

//存储空间基址(初始化时分配空间)

intnodeNum;

//二叉树中结点数

}SqBiTree;

//二叉树的顺序存储结构

SqBiTreebt;第29页/共110页为了能在存储结构中反映出结点之间的逻辑关系，必须将二叉树中结点依照一定规律安排在这组存储单元中。对于完全二叉树，只要从根起按层序存储即可。将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中

0123456789abcdefghij第30页/共110页根据二叉树的特性五，可推出顺序存储结构中“双亲”和“孩子”的关系：

假设bt.data[i]是完全二叉树上的一个结点若2i+1<bt.nodeNum，则bt.data[2i+1]是它的左孩子，否则它的左子树为空树；若2i+2<bt.nodeNum，则bt.data[2i+2]是它的右孩子，否则它的右子树为空树。0123456789abcdefghij第31页/共110页对于一般的二叉树，可对照完全二叉树的编号进行相应的存储，但在没有结点的分量中需填充空白字符。为此，需要依据实际结点数来分配存储空间，即采用链式存储结构。abcdefgabcde0000fg012345678910第32页/共110页二叉链表二叉链表的结点结构：

LchilddataRchild二叉树的二叉链表存储表示

typedefstructBiTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指针

}BiTNode,*BiTree;

第33页/共110页整个二叉树可用一个指向根结点的指针表示。第34页/共110页BiTreecreate_tree(){ BiTreeq[100]; BiTNode*s,*root=NULL; charch; intrear=0,front=1; ch=getchar(); while(ch!='#') { if(ch!=',') { s=(BiTNode*)malloc(sizeof(BiTNode)); s->data=ch; s->lchild=NULL; s->rchild=NULL; }elses=NULL; q[++rear]=s; if(rear==1) root=s;

else { if(rear%2==0)q[front]->lchild=s;else{q[front]->rchild=s;front++; } }ch=getchar(); }//whilereturnroot;}

第35页/共110页三叉链表三叉链表的结点结构：

parentLchilddataRchild二叉树的三叉链表存储表示

typedefstructTriTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指针

structBiTNode*parent;

//双亲指针

}TriTNode,*TriTree;

第36页/共110页第37页/共110页双亲链表双亲链表的结点结构：

dataparentLRTag二叉树的双亲链表存储表示typedefstructBPTNode{

//结点结构

ElemTypedata;

int*parent;

//指向双亲的指针

charLRTag;

//左、右孩子标志域

}BPTNode

typedefstructBPTree{

//树结构

BPTNode*nodes;

//初始化时分配存储空间

intnodeNum;

//结点数目

introot;

//根结点的位置

}BPTree

第38页/共110页二叉树的双亲链表建表过程constMAXSIZE=100;

//暂定二叉树中结点数的最大值为100cin>>BT.nodeNum;

//输入结点数目

BT.root=0;

cin>>BT.nodes[0].data;

//输入根

BT.nodes[0].parent=-1;

//根的双亲为空

BT.nodes[0].LRTag=‘L’;

for(i=1;i<BT.nodeNum;i++)

{

cin>>BT.nodes[i].data>>F>>BT.nodes[i].LRtag;

k=i-1;

while(k>=0&&BT.nodes[k].data!=F)k--;//查询双亲

if(k<0)returnFALSE;

//没有找到双亲

BT.nodes[i].parent=k;

returnTRUE;

}第39页/共110页二叉树的输入数据为：

6,A,(B,A,L),(C,B,R),(D,A,R),(E,D,R),(F,E,L)

建立的双亲链表如下所示：第40页/共110页二叉树的遍历

“遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。因此进行遍历应该确定一条搜索路径，使得结构中的每个数据元素都出现在这条搜索路径上，才能确保每个数据元素都被访问到。

二叉树中每个结点都有两个后继，可以有三条搜索路径：

1)先左(子树)后右(子树)；

2)先右(子树)后左(子树)；

3)按层次从上到下。

第41页/共110页先左后右的遍历第一次走到根结点即“访问”为“先序遍历”，从左子树回来再“访问”为“中序遍历”，从右子树回来再"访问"为"后序遍历"第42页/共110页根据对二叉树进行遍历的先左后右的搜索路径，可得以下三个遍历二叉树的算法先序遍历二叉树中序遍历二叉树后序遍历二叉树若二叉树为空，则空操作；

否则

(1)访问根结点

(2)先序遍历左子树

(3)先序遍历右子树若二叉树为空，则空操作；

否则

(1)中序遍历左子树

(2)访问根结点

(3)中序遍历右子树若二叉树为空，则空操作；

否则

(1)后序遍历左子树

(2)后序遍历右子树

(3)访问根结点按照遍历过程中先后访问的次序将二叉树中的结点排列起来可分别得到二叉树的先序序列、中序序列和后序序列。第43页/共110页voidPreOrder(BiTreeT，void(*visit)(BiTree))

{

//先序遍历以T为根的二叉树

if(T){ //T=NULL时，二叉树为空树，不做任何操作

visit(T);

//通过函数指针*visit访问根结点

Preorder(T->Lchild,visit); //先序遍历左子树

Preorder(T->Rchild,visit); //先序遍历右子树

}//if

}第44页/共110页voidInOrder(BiTreeT，void(*visit)(BiTree))

{

//中序遍历以T为根的二叉树

if(T){ //T=NULL时，二叉树为空树，不做任何操作

InOrder(T->Lchild,visit); //中序遍历左子树

visit(T);

//通过函数指针*visit访问根结点

InOrder(T->Rchild,visit); //中序遍历右子树

}//if

}第45页/共110页voidPostOrder(BiTreeT，void(*visit)(BiTree))

{

//后序遍历以T为根的二叉树

if(T){ //T=NULL时，二叉树为空树，不做任何操作

PostOrder(T->Lchild,visit); //先序遍历左子树

PostOrder(T->Rchild,visit); //先序遍历右子树

visit(T);

//通过函数指针*visit访问根结点

}//if

}第46页/共110页遍历算法例题1假设访问二叉树T的结点的操作是打印结点的值，请分别写出下图所示的二叉树的先序、中序和后序序列ACBDFGHEJIAABF

ABCDEFGHIJ

ALARFLBLBRFRFBALARBLBRFLFRALAR第47页/共110页-+/a*b-efcd先序遍历：中序遍历：后序遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef用二叉树可以表示数学表达式，例如：

a+b*(c-d)-e/f表达式的前缀表示表达式的中缀表示表达式的后缀表示第48页/共110页遍历算法例题2已知二叉树的先序和中序序列如下，试构造出相应的二叉树。先序：ABCDEFGHIJ

中序：CDBFEAIHGJ原理：先序序列的第一个节点是根节点中序序列根结点处于左右子树的中序序列之间注意：二叉树的先序和后序序列不能唯一确定一棵二叉树，但由先序和中序或后序和中序序列能唯一确定一棵二叉树。先序：ABCDEFGHIJ中序：CDBFEAIHGJBCDEFCDBFEGHIJIHGJACDCDEFFEHIIHJJAGBAJECBFDGHI第49页/共110页非递归算法——中序遍历BoolInOrder(BiTreeT,bool(*visit)(ElemTypee)){//采用二叉链表存储结构，中序遍历二叉树T的非递归算法

InitStack(S);Push(S,T);//根指针进栈

while(!StackEmpty(S)){while(Gettop(S,p)&&p)Push(S,p->lchild);//找最左下结点

Pop(S,p);//空指针退栈

if(!StackEmpty(S)){Pop(S,p);visit(p->data);//访问结点

Push(S,p->rchild);//访问右子树

}//if}//whilereturnOK;}//InOrder第50页/共110页非递归算法——先序遍历BoolPreOrder(BiTreeT,bool(*visit)(ElemTypee)){//采用二叉链表存储结构，中序遍历二叉树T的非递归算法

InitStack(S);Push(S,T);//根指针进栈

while(!StackEmpty(S)){Gettop(S,p)if(p){visit(p->data);//访问结点

Push(S,p->lchild);}else{Pop(S,p);//空指针退栈

if(!StackEmpty(S)){Pop(S,p);Push(S,p->rchild);//访问右子树

}}//else}//whilereturnOK;}//InOrder第51页/共110页二叉树算法举例建立二叉树的存储结构--二叉链表设二叉树中结点的元素均为一个单字符，并以“#”表示空树。假设二叉树以由“根”、“左子树串”和“右子树串“联接而成的字符串表示，则建立二叉链表的算法应该是一个“先序遍历”的过程，并且遍历过程中“访问”的操作应是识别输入的字符并作相应操作

第52页/共110页例如，空树以“#”表示，只有一个根结点A的二叉树以"A##"表示，下列二叉树则以"AB#CD###E#F##“表示。

第53页/共110页在输入数据正确的前提下，由此建立二叉链表的算法为：

若输入的字符是'#'，则建立空树；

否则

建立根结点；

递归建立左子树的二叉链表；

递归建立右子树的二叉链表。

第54页/共110页voidCreateBiTree(BiTree&T)

{

//在先序遍历二叉树的过程中输入二叉树的“先序字符

//串”，建立根指针为T的二叉链表存储结构。在先序

//字符串中，字符‘#’表示空树，其它字母字符为结点

//的数据元素

cin>>ch；

if(ch==‘#’)T=NULL;

//建空树

else{

T=newBiTNode;

//“访问”操作为生成根结点

T->data=ch;

CreateBiTree(T->Lchild);

//递归建(遍历)左子树

CreateBiTree(T->Rchild);//递归建(遍历)右子树

}//else

}//CreateBiTree第55页/共110页

先序序列为：ABDEGHCFIJ

中序序列为：DBGEHACIJF

后序序列为：DGHEBJIFCA

第56页/共110页二叉树的线索链表如果将在第一次遍历过程中得到的前驱和后继信息保存起来，那么在以后需要再次对二叉树进行“遍历”时就可以将二叉树视作线性结构进行访问操作第57页/共110页如何保存在遍历过程中得到的前驱和后继信息？最简单的办法是在结点中增加两个指针域分别指向该结点的前驱和后继。一个含n个结点的二叉链表中有n+1个链域的值为“NULL”，可以利用这些空的指针域存放指向前驱和后继的信息，由此得到的二叉树的存储结构称作“线索链表”，其中指向前驱或后继的指针称作"线索"。

第58页/共110页二叉树的二叉线索链表存储表示

typedefenumPointerType{Link=0,Thread=1};

//定义指针类型，以Link表示指针，Thread表示线索

typedefstructBiThrNode{

ElemTypedata;

structBiThrNode*Lchild,*Rchild;

//左右指针

PointerTypeLTag,RTag;

//左右指针类型标志

}*BiThrTree;

第59页/共110页若结点的左指针类型标志为“Link”，则Lchild指向它的左子树根结点，否则指向它的“前驱”；若结点的右指针类型标志为“Link”，则Rchild指向它的右子树根结点，否则指向它的"后继"。

第60页/共110页中序线索链表第61页/共110页在线索链表中添加了一个“头结点”，头结点的左指针指向二叉树的根结点，其右线索指向中序序列中的最后一个结点，中序序列中的第一个结点的左线索和中序序列中的最后一个结点的右线索均指向头结点。第62页/共110页以中序线索链表为存储结构的中序遍历如何在中序线索链表上进行遍历，关键问题有二：

一是如何找到访问的第一个结点？

二是如何找到每个结点在中序序列中的后继？

第63页/共110页如何找到访问的第一个结点？中序遍历访问的第一个结点必定是"其左子树为空“的结点。若根结点没有左子树，则根结点即为中序遍历访问的第一个结点，若根结点的左子树不空，则访问的第一个结点应该是其左子树中“最左下的结点“，即从根结点出发，顺指针Lchild找到其左子树直至某个结点的指针Lchild为“线索”止，该结点必为中序序列中的第一个结点。第64页/共110页如何找到每个结点在中序序列中的后继？

若结点没有右子树，即结点的右指针类型标志Rtag为“Thread”，则指针Rchild所指即为它的后继若结点有右子树，则它的后继应该是其右子树中访问的第一个结点。和前面所述找二叉树的第一个结点一样，就应该从它的右子树根出发，顺指针Lchild直至没有左子树的结点为止，该结点即为它的后继。

第65页/共110页例如：找结点B的后继。结点B的RTag=Link，则顺指针Rchild找到它的右子树根E，因为结点E的LTag=Link，则顺指针Lchild找到它的左子树根G，因为结点G的Ltag=Thread，说明G是结点B的右子树中“最左下”的结点，所以结点G是结点B的后继。第66页/共110页voidInOrderTraverse_Thr(BiThrTreeThead,void(*Visit)(ElemTypee))

{

//Thead指向中序线索链表中的头结点，头结点的左指针Lchild

//指向二叉树的根结点，头结点的右线索Rchild指向中序遍历

//访问的最后一个结点。本算法对此二叉树进行中序遍历，对

//树中每个数据元素调用函数Visit进行访问操作

p=Thead->Lchild;

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

while(p!=Thead){

//空树或遍历结束时，p==Thead

while(p->LTag==Link)p=p->Lchild;

Visit(p->data);

//访问其左子树为空的结点

while(p->RTag==Thread&&p->Rchild!=Thread){

p=p->rchild;Visit(p->data);

//访问"右线索"所指后继结点

}//while

p=p->Rchild;

//p进至其右子树根

}//while

}//InOrderTraverse_Thr第67页/共110页线索链表的生成由于线索链表上保存的是“遍历”过程中得到的前驱和后继的信息，显然，线索链表应该在遍历过程中建立，即在遍历过程中改变二叉链表中结点的“空指针“以及相应的”指针类型标志“。若结点没有左子树，则令其左指针指向它的“前驱“并将左指针类型标志改为“Thread”，若结点没有右子树，则令它的右指针指向它的“后继”并将右指针类型标志改为“Thread”。为了获取“前驱”的信息，需要在遍历过程中添加一个指向其前驱的指针pre。

第68页/共110页建立线索链表的过程即为将遍历过程中对结点进行下列"访问"操作(指针p指向当前访问的结点，pre指向在它之前“刚刚”访问过的结点)：

if(!pre->Rchild){

pre->RTag=Thread;

pre->Rchild=p;

}

if(!p->Lchild){

p->LTag=Thread;

p->Lchild=pre;

}

pre=p;第69页/共110页voidInThreading(BiThrTreep，BiThrTree&pre)

{

//对p指向根结点的二叉树进行中序遍历，遍历过程中进行“中序线索

//化”。若p所指结点的左指针为空，则将它改为“左线索”，若pre

//所指结点的右指针为空，则将它改为“右线索”。指针pre在遍历

//过程中紧随其后，即始终指向p所指结点在中序序列中的前驱。

if(p){

InThreading(p->Lchild,pre);

//对左子树进行线索化

if(!p->Lchild)

{p->LTag=Thread;p->Lchild=pre;}

//建前驱线索

if(!pre->Rchild)

{pre->RTag=Thread;pre->Rchild=p;}//建后继线索

pre=p;

//保持pre指向p的前驱

InThreading(p->Rchild,pre);

//对右子树进行线索化

}//if

}//InThreading第70页/共110页voidInOrderThreading(BiThrTree&Thead,BiThrTreeBT)

{

//BT为指向二叉树根结点的指针，由此二叉链表建立二叉树

//的中序线索链表，Thead指向线索链表中的头结点。

BiThrTreepre;

if(!(Thead=newBiThrNode))exit(1);//存储分配失败

Thead->LTag=Link;Thead->RTag=Thread;

//建头结点

Thead->Rchild=Thead;

//右指针回指

if(!BT)Thead->Lchild=Thead;

//若二叉树空，则左指针回指

else{

Thead->Lchild=BT;pre=Thead;

InThreading(BT,pre);

//中序遍历进行中序线索化

pre->Rchild=Thead;pre->RTag=Thead;

//对中序序列中最后一个结点进行线索化

Thead->Rchild=pre;

//建非空树的头结点的"右线索"

}//else

}//InOrderThreading第71页/共110页树的存储结构——树的双亲表示法树的双亲链表存储表示

constMAX_TREE_SIZE=100;

typedefstruct{

//结点结构

ElemTypedata;

intparent;

//双亲位置域

}PTNode;

typedefstruct{

//树结构

PTNodenodes[MAX_TREE_SIZE];

intr,n;

//根的位置和结点数

}PTree;

第72页/共110页A-1B0E1H2I2J2C0D0F7G7K9该树的双亲链表如下所示

01532648710911第73页/共110页树的孩子表示法让每个结点的“子树根”构成一个线性表，以链表作它的存储结构，令其头指针和结点的数据元素构成一个结点，并将所有这样的结点存放在一个地址连续的存储空间里，所构成的树的存储结构称为树的孩子链表。第74页/共110页树的孩子链表存储表示

typedefstructCTNode{

//孩子结点

intchild;

structCTNode*next;

}*ChildPtr;

typedefstruct{

ElemTypedata;

//结点的数据元素

ChildPtrfirstchild;

//孩子链表头指针

}CTBox;

typedefstruct{

CTBoxnodes[MAX_TREE_SIZE];

intn,r;

//结点数和根结点的位置

}CTree;第75页/共110页第76页/共110页树和森林的孩子兄弟表示法树和森林的二叉链表(孩子-兄弟）存储表示

typedefstructCSNode{

ElemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;

树中每个结点都设有两个指针：

firstchild：指向该结点的“第一个”子树根结点

nextsibling：指向它的"下一个"兄弟结点

第77页/共110页第78页/共110页可将上图所示的二叉链表看成是下列二叉树的存储结构由此，通过存储结构的一致性作为“媒介”，可建立森林和二叉树之间一一对应的关系

第79页/共110页森林和二叉树的转换假设森林

F={T1,T2,…,Tn}可按如下规则转换成一棵二叉树

B=(LBT,Node(root),RBT)

若森林F为空集，则二叉树B为空树；否则，由森林中第一棵树的根结点ROOT(T1)复制得二叉树的根Node(root)，由森林中第一棵树的子树森林转换得到二叉树中的左子树LBT，由森林中删去第一棵树之后由其余树构成的森林{T2,T3,…,Tn}转换得到二叉树中的右子树RBT第80页/共110页第81页/共110页反之，对于任意一棵二叉树B=(LBT,Node(root),RBT)可转换得到由n棵树构成的森林F={T1,T2,…,Tn}

若二叉树B为空树,则与其对应的森林F为空集；否则，由二叉树的根结点Node(root)复制得森林中第一棵树的根结点ROOT(T1)，由二叉树中的左子树LBT转换构造森林中第一棵树的子树森林，由二叉树中的右子树RBT转换构造森林中其余树构成的森林{T2,T3,…,Tn}第82页/共110页树的遍历树的遍历：从根结点出发，对树中各个结点进行一次且仅进行一次访问对树进行遍历可有两条搜索路径：一条是从左到右；另一条是按层次从上到下

第83页/共110页对树进行从左到右遍历的过程中要途径根结点两次，由对根的访问时机不同可得下列两个算法：

一、先根(次序)遍历树

若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树；ABEHIJCDFGK

二、后根(次序)遍历树若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点；HIJEBCFKGDA

第84页/共110页森林的遍历一、先序遍历森林

若森林不空，则可依下列次序进行遍历

(1)访问森林中第一棵树的根结点；

(2)先序遍历第一棵树中的子树森林；

(3)先序遍历除去第一棵树之后剩余的树构成的森林。

第85页/共110页二、中序遍历森林

若森林不空，则可依下列次序进行遍历：

(1)中序遍历第一棵树中的子树森林；

(2)访问森林中第一棵树的根结点；

(3)中序遍历除去第一棵树之后剩余的树构成的森林。

第86页/共110页容易看出，树的先根遍历即森林的先序遍历可对应到二叉树的先序遍历，树的后根遍历即森林的中序遍历可对应到二叉树的中序遍历。

第87页/共110页最优树和赫夫曼编码最优树：又称赫夫曼树（HuffmanTree）是一类带权路径长度最短的树路径：从树的根结点到其余结点的分支构成的一条路径路径长度：路径上的分支数目树的路径长度：指的是从树根到树中其余每个结点的路径长度之和结点的带权路径长度：从树根到该结点之间的路径长度与该结点上所带权值的乘积第88页/共110页树的带权路径长度：树中所有叶子结点的带权路径长度之和假设树上有n个叶子结点，且每个叶子结点上带有权值为wk(k=1,2,…,n)，则树的带权路径长度为

其中lk为带权wk的叶子结点的带权路径长度

第89页/共110页

假设有n个权值{w1，w2，…wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为

wi。显然，这样的二叉树可以构造出多棵，其中必存在一棵带权路径长度WPL取最小的二叉树，称该二叉树为最优二叉树。

第90页/共110页右图中的四棵二叉树，都有5个叶子结点且带相同权值5、6、2、9、7，它们的带权路径长度分别为

WPL=7×3+9×3+5×2+6×2+2×2=74

WPL=2×1+6×3+7×4+9×4+5×2=94

WPL=6×2+7×2+5×3+2×3+9×2=65

WPL=2×1+5×3+7×3+9×3+6×3=83

第91页/共110页最优树的构造方法赫夫曼最早给出了一个构造最优树的带有一般规律的算法，俗称赫夫曼算法根据给定的n个权值{w1,w2,…wn}，构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中

重复(2)和(3)，直到F只含一棵树为止。这棵树便是所求的赫夫曼树。第92页/共110页最优前缀编码赫夫曼二叉树在通讯编码中的一个应用是利用它构造一组最优前缀编码。在某些通讯场合，需将传送的文字转换成由二进制字符组成的字符串第93页/共110页

例如，假设需传送的电文为“ABACCDA”，它只有

A、B、C和D四种字符，可设它们的编码分别为

00、01、10和11，则上述七个字符的电文便为“000100101100”，总长14位。显然这样的等长编码便于译码，对方接收时，可按两位一分进行译码。

第94页/共110页通常有两类二进制编码：一类为等长编码，这类编码的二进制串的长度取决于电文中不同的字符个数，假设需传送的电文中只有四种字符，只需两位字符的串便可分辨，但如果电文中可能出现26种不同字符，则等长编码串的长度为5。另一类是