第6章树与二叉树

第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）16.1

树的定义和基本术语1.树的定义2.若干术语3.逻辑结构4.存储结构5.树的运算21.树的定义注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是树”的说法，但现在树的定义已修改。注2：树的定义具有递归性，即树的定义中还有树。树（Tree）是n个(n≥0)结点组成的有限集合T。在任何一棵非空树中：（1）有且仅有一个结点称为根（root）；（2）当n>1时，其余的结点可分为m(m>0)个互不相交的有限集合T1,T2，…，Tm。其中，每个集合本身又是一棵树，被称作这个根的子树（SubTree）。3A只有根结点的树ABCDEFGHIJKLM有子树的树根子树4树的抽象数据类型定义（见教材P118-119）ADTTree{数据对象D:数据关系R:基本操作P：}ADTTree若D为空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；否则R={H}，H是如下二元关系：

①在D中存在唯一根元素root，在H下无前驱

②若D-{root}≠Φ，则存在对D-{root}的一个划分，对任意j≠k，有Dj∩Dk=Φ，且<>∈H...

③对应于D-{root}

的划分，H-……有唯一一个划分，对任意j≠k，有Hj∩Hk=Φ。(Di,{Hi})D是具有相同特性的数据元素的集合。//至少有15个5

基本操作：查找类插入类删除类6

Root(T)//求树的根结点

查找类：Value(T,cur_e)//求当前结点的元素值

Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历7InitTree(&T)//初始化置空树

插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树8

ClearTree(&T)//将树清空

删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树9树的表示法有几种：图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子－右兄弟表示法这些表示法的示意图参见教材P120图6.210广义表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)))根作为由子树森林组成的表的名字写在表的左边11左孩子－右兄弟表示法ABCDEFGHIJKLM数据左孩子

右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)))122.若干术语——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点ABCGEIDHFJMLK

根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。132.若干术语（续）——即树的数据元素及其分支——结点挂接的子树数（有几个直接后继就是几度。）结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)ABCGEIDHFJMLK——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值（Max{各结点的度}）——指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝133414ABCDEFGHIJKLM结点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的祖先153.树的逻辑结构

(特点)：一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。4.树的存储结构

讨论1：树是非线性结构，该怎样存储？————仍然有顺序存储、链式存储等方式。

16讨论3：树的链式存储方案应该怎样制定？可规定为：从上至下、从左至右将树的结点依次存入内存。重大缺陷：复原困难（不能唯一复原就没有实用价值）。讨论2：树的顺序存储方案应该怎样制定？可用多重链表：一个前驱指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？

即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。解决思路：先研究最简单、最有规律的树状结构，然后设法把一般的树转化为简单树。二叉树175.树的运算

要明确：1.普通树（即多叉树）若不转化为二叉树，则运算很难实现。2.二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！（遍历——指每个结点都被访问且仅访问一次，不遗漏不重复）。本章重点：二叉树的定义、性质、表示和实现18~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)

根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)196.2二叉树为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转换为唯一的一棵二叉树与其对应，不失一般性。6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构（二叉树的运算见6.3节）206.2.1二叉树的定义定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：

一对二（1：2）

基本特征:①每个结点最多可有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒（有序树）。21二叉树的五种基本形态：root空树只含根结点rootrootrootLRR右子树为空树L左子树为空树左右子树均不为空树22二叉树的抽象数据类型定义（见教材P121-122）ADTBinaryTree{数据对象D:数据关系R:基本操作P：}ADTBinaryTree若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dl∩Dr=Φ//关于子树不相交的说明③……//关于二元关系的说明

④……

//关于左子树和右子树的说明D是具有相同特性的数据元素的集合。//至少有20个23

二叉树的主要基本操作：查找类插入类删除类24

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());25

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);26ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);276.2.2二叉树的性质(3+2)讨论1：第i层的结点数至多是多少？

（利用二叉树的特性可轻松求出）

性质1:

在二叉树的第i层上至多有2i-1个结点（i>0）。性质2:

深度为k的二叉树至多有2k-1个结点（k>0）。2i-1个提问：第i层上至少有

个结点？1讨论2：深度为k的二叉树，至多有多少个结点？

（利用二叉树的特性可轻松求出）2k-1提问：深度为k时至少有

个结点？k28讨论3：二叉树的叶子数n0和度为2的结点数n2之间有关系吗？性质3:

对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1（即n0=n2+1）证明：∵二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数)又∵二叉树中全部结点数n＝B+1

(总分支数＋根结点)（除根结点外，每个结点必有且仅有一个直接前趋，即一个分支进入）而

总分支数B=n1+2n2(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：

n0+n1+n2=

n1+2n2+1,即n0=n2+1实际意义：叶子数＝2度结点数＋1ABCGEIDHFJ29满二叉树：一棵深度为k且有2k-1个结点的二叉树。

（特点：每层都“充满”了结点）完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。AOBCGEKDJFIHNML深度为4的满二叉树深度为4的完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式？因为它们在顺序存储方式下可以复原！解释：完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。

这其实是顺序二叉树的含义。在图论概念中的“完全二叉树”是指n1=0的情况。303.深度为9的完全二叉树中至少有

个结点。最多呢？

Ａ)２9Ｂ)２8Ｃ)９Ｄ)２9－12.深度为k的二叉树的结点总数，最多为

个。

Ａ)２k-1Ｂ)log2kＣ)２k－１Ｄ)２k课堂练习：1.树Ｔ中各结点的度的最大值称为树Ｔ的

。

Ａ)高度Ｂ)层次Ｃ)深度Ｄ)度复习讨论：①二叉树是不是树的特殊情况？答：不是！虽然二叉树也属于一种树结构，但它是另外单独定义的一种树状结构，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。②：满二叉树和完全二叉树有什么区别？答：满二叉树是每一层都是满的二叉树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。√√√31

性质4：

具有n个结点的完全二叉树的深度为log2n+1证明：设完全二叉树的深度为k则根据第二条性质得2k-1≤n<2k

即k-1≤log2n<k

因为k只能是整数，因此，k=log2n

+132课堂讨论：问:设一棵完全二叉树具有1000个结点，则它有

个叶子结点，有

个度为2的结点，有

个结点只有非空左子树，有

个结点只有非空右子树。48948810由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现只有非空右子树的结点(0个)。答：易求出总层数和末层叶子数。总层数k=log2n＋1=10;且前9层总结点数为29-1=511

(完全二叉树的前k-1层肯定是满的)所以末层叶子数为1000-511=489个。33请注意叶子结点总数≠末层叶子数！还应当加上第k-1层（靠右边）的0度结点个数。分析：k层的489个叶子的父结点占上层的245个结点（489/2)上层（k=9)右边的0度结点数还有29-1-245=11个！另一法：可先求2度结点数,再由此得到叶子总数。首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉）另外，末层叶子（刚才已求出为489）所对应的双亲也是度＝2，（共有489/2＝244个）。所以，全部2度结点数为255(k-2层)＋244(k-1层)=499个；总叶子数＝2度结点数＋1=500个。第i层上的满结点数为2i-1所以，全部叶子数＝489(末层)＋11(k-1层)=500个。度为2的结点＝叶子总数－1=499个。34讨论：完全二叉树中双亲结点和孩子结点编号之间有关系吗？12345678910111213141535性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：

(1)若i=1，则该结点是二叉树的根，无双亲；否则，编号为i/2的结点为其双亲结点;

(2)若2i>n，则该结点无左孩子，

否则，编号为2i的结点为其左孩子结点；

(3)若2i+1>n，则该结点无右孩子结点，

否则，编号为2i+1的结点为其右孩子结点。366.2.3二叉树的存储结构一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5）例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。T[0]这里没用37#defineMAX_TREE_SIZE100

//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];

//0号单元存储根结点SqBiTreebt;二叉树的顺序存储表示38讨论：不是完全二叉树怎么办？答：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺点：①浪费空间；②插入、删除不便

39例如:

ABDCEF

012345678910111213ABCDEF140132640二、链式存储结构

用二叉链表即可方便表示。dataleft_childright_childdataleft_childright_child1、二叉链表2、三叉链表3、线索链表一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始）注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。41ADEBCFrootlchilddatarchild结点结构:1.二叉链表ABDCEF42讨论：有n个结点二叉树的二叉链表有多少空链域？

解释1:

2*n-（n-1）=n+1解释2:

2*n0+n1=n0+n1+n2+1=n+1n+1个43typedefstructBiTNode{//结点结构TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言的类型描述如下:44rootADEBCF2．三叉链表parentlchilddatarchild结点结构:ABDCEF45

typedefstructTriTNode{//结点结构TElemTypedata;

structTriTNode*lchild,*rchild;//左右孩子指针

structTriTNode

*parent;//双亲指针

}TriTNode,*TriTree;parent

lchilddatarchild结点结构:C语言的类型描述如下:466.3遍历二叉树和线索二叉树一、遍历二叉树（TraversingBinaryTree）遍历定义——指按某条搜索路线遍访每个结点且不重复（又称周游）。遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

遍历方法——牢记一种约定，对每个结点的查看都是“先左后右”。47遍历规则———二叉树由根、左子树、右子树构成，定义为D、L、RD、L、R的组合定义了六种可能的遍历方案：

DLR,LDR,LRD,DRL,RDL,RLD若限定先左后右，则有三种实现方案：

DLRLDRLRD先

(根)序遍历中

(根)序遍历后(根)序遍历

注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。DLR48例1：先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABCDEABDECDBEACDEBCA口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根49+*A*/EDCB先序遍历+**/ABCDE前缀表示中序遍历A/B*C*D+E中缀表示后序遍历AB/C*D*E+后缀表示层序遍历+*E*D/CAB例2：用二叉树表示算术表达式50二、遍历的递归算法实现：用递归形式格外简单！voidPreorder(BiTreeT,

void(*visit)(TElemType&e)){//

先序遍历二叉树

if(T){

visit(T->data);//访问根结点Preorder(T->lchild,visit);//遍历左子树Preorder(T->rchild,visit);//遍历右子树

}}51先序遍历算法DLR(tree*root){if(root!=NULL){

//非空二叉树printf(“%d”,root->data);//访问DDLR(root->lchild);//递归遍历左子树DLR(root->rchild);//递归遍历右子树

}return(0);}中序遍历算法LDR(tree*root){if(root!=NULL){

LDR(root->lchild);printf(“%d”,root->data);

LDR(root->rchild);}return(0);}后序遍历算法LRD(tree*root){if(root!=NULL)

{

LRD(root->lchild);LRD(root->rchild);printf(“%d”,root->data);}return(0);}结点数据类型自定义typedefstructNode{intdata;structNode*lchild,*rchild；}tree;tree*root;

52三、对遍历的分析：1.从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问＝先序遍历第2次经过时访问＝中序遍历第3次经过时访问＝后序遍历2.二叉树遍历的时间效率和空间效率时间效率:O(n)//每个结点只访问一次空间效率:O(n)//栈占用的最大辅助空间（精确值：树深为k的递归遍历需要k+1个辅助单元！）53ADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列：ABDC先序遍历:54ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历序列：BDAC中序遍历:55ADBCLRDLRDLRD>A>>D>>CLRD后序遍历序列：DBCA后序遍历:B56ABCDEFGHK复习回顾：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

Alchild

data

rchildparent

lchild

data

rchild57voidPreorder(BiTreeT,

void(*visit)(TElemType&e)){//

先序遍历二叉树

if(T){

visit(T->data);//访问根结点Preorder(T->lchild,visit);//遍历左子树Preorder(T->rchild,visit);//遍历右子树

}}58voidpre(BiTreeT){if(T){printf("%d\t",T->data);pre(T->L);pre(T->R);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC59四、遍历二叉树的非递归实现：中序遍历的非递归实现：1、结点（初始时是根结点）进栈，沿左指针查找左孩子。2、若有左孩子，返回第一步。3、若无左孩子，判栈空？空则结束。非空，栈顶结点出栈访问。转向右子树，返回1。例如:BCDELAXW中序：B、L、E、A、C、W、X、DStatusInOrderTraverse(BiTreet,Visit){initstack(s);push(s,t);//t是根结点while(!stackempty(s)){while(Gettop(s,p))&&p)//有值且非空时push(s,p->lchild)；//null值可能进栈pop(s,p);//空指针退栈if(!stackempty(s))//访问结点，向右一步{pop(s,p);visit(p->data);push(s,p->rchild);}}//WhilereturnOK;}//InOrderTraverseStatusInOrderTraverse(BiTreet,Visit){initstack(s);p=T;while(p||!StackEmpty(s)){if(p){push(s,p)；p=p->lchild;}//根指针进栈，遍历左子树else{//根指针退栈，访问根结点，遍历右子树pop(s,p);if(!Visit(p->data))returnERROR;p=p->rchild;}}returnOK;}//InOrderTraverse中序非递归算法演示ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B访问：C(4)61pABCDEFGiP->A访问：CB(5)ABCDEFGiP->AP->D访问：CBp(6)ABCDEFGiP->AP->DP->E访问：CBp(7)ABCDEFGiP->AP->D访问：CBEp(8)62ABCDEFGiP->AP->DP->G访问：CBEP=NULL(9)ABCDEFGiP->A访问：CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)ABCDEFGiP->AP->D访问：CBEGp(10)63ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)ABCDEFGi访问：CBEGDFAp=NULL(15)64五、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法65

以字符串的形式“根左子树右子树”定义一棵二叉树例如:以空白字符“”表示ABCDA(B(,C(,)),D(,))空树只含一个根结点的二叉树A以字符串“A”表示以下列字符串表示66Status

CreateBiTree(BiTree&T)

{scanf(&ch);

if(ch=='')T=NULL;

else{

if(!(T=newBiTNode))

exit(OVERFLOW);T->data=ch;//生成根结点

CreateBiTree(T->lchild);//构造左子树

CreateBiTree(T->rchild);//构造右子树

}

returnOK;

}//CreateBiTree67AB

C

D

ABCD上页算法执行过程举例如下:ATBCD^^^^^scanf(&ch);if(ch=='')T=NULL;else{

if(!(T=newBiTNode))

exit(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);68六、遍历算法的应用举例2、统计二叉树中叶子结点的个数3、求二叉树的深度(后序遍历)4、复制二叉树(后序遍历)5、建立二叉树的存储结构1、查询二叉树中某个结点691)在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回TRUE;2)否则在左子树中进行查找,若找到,则返回TRUE;3)否则继续在右子树中进行查找,若找到,则返回TRUE,否则返回FALSE;1、查询二叉树中某个结点StatusPreorder(BiTreeT,ElemTypex,BiTree&p){//若二叉树中存在和x相同的元素，则p指向该结点并返回OK,否则返回FALSE

}if(T){

if(T->data==x){p=T;returnOK,}

}//if

elsereturnFALSE;else{

if(Preorder(T->lchild,x,p)

returnOK;

else

return(Preorder(T->rchild,x,p));}//else702、统计二叉树中叶子结点的个数算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为:若是叶子，则计数器增1。void

CountLeaf(BiTreeT,int&count){

if(T){

if((!T->lchild)&&(!T->rchild))count++;

//对叶子结点计数

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);

}//if}//CountLeafint

CountLeaf(BiTreeT){//返回指针T所指二叉树中所有叶子结点个数

if(!T)return0;if(!T->lchild&&!T->rchild)return1;else{

m=CountLeaf(T->lchild);

n=CountLeaf(T->rchild);

return(m+n);}//else}//CountLeafintCount

(BiTreeT){//返回指针T所指二叉树中所有结点个数if(!T)return0;if(!T->lchild&&!T->rchild)return1;else{

m=Count

(T->lchild);

n=Count

(T->rchild);

return(m+n+1);}//else}//CountLeaf713、求二叉树的深度(后序遍历)算法基本思想:首先分析二叉树的深度和它的左、右子树深度之间的关系。

从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中访问结点的操作为:求得左、右子树深度的最大值，然后加1。int

Depth(BiTreeT){

//返回二叉树的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

returndepthval;}voidDepth(BiTreeT,intlevel,int&dval){

if(T){if(level>dval)dval=level;

Depth(T->lchild,level+1,dval);

Depth(T->rchild,level+1,dval);}}//调用之前level的初值为1,dval的初值为0.724、复制二叉树(后序遍历)其基本操作为:生成一个结点。根元素NEWT左子树右子树根元素T左子树右子树左子树右子树ABCDEFGHK^D^C^^H^^K^GAnewTF^^BE^73BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr){

if(!(T=newBiTNode))exit(1);

T->data=item;T->lchild=lptr;T->rchild=rptr;returnT;}生成一个二叉树的结点(其数据域为item,左指针域为lptr,右指针域为rptr)BiTNode*CopyTree(BiTNode*T){if(!T)returnNULL;if(T->lchild)newlptr=CopyTree(T->lchild);//复制左子树elsenewlptr=NULL;if(T->rchild)newrptr=CopyTree(T->rchild);//复制右子树elsenewrptr=NULL;newT=GetTreeNode(T->data,newlptr,newrptr);returnnewT;}//CopyTree745、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法(1)以字符串的形式“根-左子树-右子树”定义一棵二叉树例如:A(B(,C(,)),D(,))ABCD以下列字符串表示以空白字符“”表示空树只含一个根结点的二叉树A以字符串“A”表示75StatusCreateBiTree(BiTree&T){scanf(&ch);if(ch=='')T=NULL;else{if(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;//生成根结点

CreateBiTree(T->lchild);//构造左子树

CreateBiTree(T->rchild);//构造右子树}returnOK;}//CreateBiTreeATBCD^^^^^scanf(&ch);if(ch=='')T=NULL;else{

if(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}AB

C

D

ABCD76(2)按给定的表达式建相应二叉树由先缀表示式建树.

例如：已知表达式的先缀表示式:-×+abc/de由原表达式建树.

例如：已知表达式:(a+b)×c–d/e对应先缀表达式-×+abc/de的二叉树abcde-×+/特点：操作数为叶子结点,运算符为分支结点scanf(&ch);if(In(ch,字母集))建叶子结点;else{建根结点;递归建左子树;递归建右子树;}由先缀表示式建树的算法的基本操作：77a+b(a+b)×c–d/ea+b×c分析表达式和二叉树的关系:abba×c+abc(a+b)×c/deabc×+++×-78基本操作:scanf(&ch);if(In(ch,字母集)){建叶子结点;暂存;}elseif(In(ch,运算符集)){和前一个运算符比较优先数;若当前的优先数“高”，则暂存;否则建子树;}79voidCrtExptree(BiTree&T,charexp[]){InitStack(S);Push(S,#);InitStack(PTR);p=exp;ch=*p;while(!(GetTop(S)==#&&ch==#)){

if(!IN(ch,OP))CrtNode(t,ch);//建叶子结点并入栈else{

switch(ch){ case(:Push(S,ch);break; case):Pop(S,c); while(c!=(){CrtSubtree(t,c);Pop(S,c)} break; defult:while(!Gettop(S,c)&&(precede(c,ch))){

CrtSubtree(t,c);Pop(S,c); } if(ch!=#)Push(S,ch);break;

}//switch

}

if(ch!=#){p++;ch=*p;}}//whilePop(PTR,T);}//CrtExptree80建叶子结点的算法为：voidCrtNode(BiTree&T,charch){if(!(T=newBiTNode))exit(OVERFLOW);T->data=char;T->lchild=T->rchild=NULL;Push(PTR,T);}建子树的算法为：voidCrtSubtree(Bitree&T,charc){if(!(T=newBiTNode))exit(OVERFLOW);T->data=c;Pop(PTR,rc);T->rchild=rc;Pop(PTR,lc);T->lchild=lc;Push(PTR,T);}81

仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，如果同时已知二叉树的中序序列“cbdaegf”,则会如何？

(3)由二叉树的先序和中序序列建树二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根82abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列83voidCrtBT(BiTree&T,charpre[],charino[],intps,intis,intn){//已知pre[ps..ps+n-1]为二叉树的先序序列，ins[is..is+n-1]为二叉树的中序//序列，本算法由此两个序列构造二叉链表

if(n==0)T=NULL;else{k=Search(ino,pre[ps]);//在中序序列中查询if(k==-1)T=NULL;else{ if(!(T=newBiTNode))exit(OVERFLOW); T->data=pre[ps]; if(k==is)T->Lchild=NULL; elseCrtBT(T->Lchild,pre[],ino[],ps+1,is,k-is); if(k=is+n-1)T->Rchild=NULL; elseCrtBT(T->Rchild,pre[],ino[],ps+1+(k-is),k+1,n-(k-is)-1);}}//}//CrtBT84讨论：1.求二叉树深度，或从x结点开始的子树深度。

算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。技巧：递归时应当从叶子开始向上计数，层深者保留。否则不易确定层数。2.按层次输出二叉树中所有结点。

算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，而不必拘泥于递归算法。技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，……由此便可产生按层次输出的效果。3中序遍历的非递归(迭代)算法算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈。可直接用while语句和push/pop操作。参见教材P130-131程序。4.判别给定二叉树是否为完全二叉树（即顺序二叉树）。

算法思路：完全二叉树的特点是：没有左子树空而右子树单独存在的情况(前k-1层都是满的，且第k层左边也满）。技巧:按层序遍历方式，先把所有结点（不管当前结点是否有左右孩子）都入队列.若为完全二叉树,则层序遍历时得到的肯定是一个连续的不包含空指针的序列.如果序列中出现了空指针，则说明不是完全二叉树。856.3.2线索二叉树线索二叉树的相关概念线索二叉树的遍历算法二叉树如何线索化？86一、线索二叉树的相关概念遍历二叉树最终求得结点的一个线性序列。其实质是：非线性结构—>线性结构。

ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA87普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。两种解决方法增加两个域：fwd和bwd；利用空链域（n+1个空链域）存放前驱指针存放后继指针如何预存这类信息？可能是根、或最左（右）叶子88指向该线性序列中的“前驱”和“后继”的指针，称作“线索”与其相应的二叉树，称作“线索二叉树”包含“线索”的存储结构，称作“线索链表”ABCDEFGHK^D^

C^^B

E^89规定：1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索)。为了避免混淆，增加两个标志域，如下图所示：lchildLTagdataRTagrchild约定:当Tag域为0时,表示正常情况，即为指针Link;当Tag域为1时,表示线索情况，即为线索Thread注：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。

线索链表：用前页结点结构所构成的二叉链表线索：指向结点前驱和后继的指针线索二叉树：加上线索的二叉树（后面图形式样）线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程90ABCGEIDHFroot悬空？悬空？解：该二叉树中序遍历结果为:

H,D,I,B,E,A,F,C,

G所以添加线索应当按如下路径进行：例：画出以下二叉树对应的中序线索二叉树。为避免悬空态，应增设一个头结点91对应的中序线索二叉树存储结构如图所示：00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为:H,

D,I,B,E,A,F,C,

G0--root192typedefstruct

BiThrNode{

TElemTypedata;

structBiThrNode*lchild,*rchild;//左右指针

PointerTagLTag,RTag;//左右标志}BiThrNode,*BiThrTree;线索链表的类型描述：

typedef

enumPointerTag{

Link,Thread};

//Link==0:指针，Thread==1:线索93二、线索二叉树的遍历算法:

for(p=

FirstNode(T);p;p=Next(p))Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。94例如:对中序线索二叉树的遍历算法

※中序遍历的第一个结点？

※在中序线索化链表中结点的后继？左子树上处于“最左下”（没有左子树）的结点（线索链表中该结点有何特点？）若无右子树，则为后继线索所指结点否则为对其右子树进行中序遍历时访问的第一个结点95StatusInOrderTraverse_Thr(BiThrTreeT,

Status(*Visit)(TElemTypee)){p=T->lchild;//p指向根结点

while(p!=T){

//空树或遍历结束时，p==Twhile(p->LTag==Link)p=p->lchild;//第一个结点

Visit(p->data);while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//访问后继结点

}p=p->rchild;//p进至其后继或右子树根

}}//InOrderTraverse_Thr96由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。三、二叉树如何线索化？97如何实现？以中序线索化为例需要记下遍历过程中访问结点的先后顺序。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。98void

InThreading(BiThrTreep,BiThrNode*&pre)

{

if(p){//对以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}//InThreading99StatusInOrderThreading(BiThrTree&Thrt,

BiThrTreeT){//构建中序线索链表if(!(Thrt=newBiThrNode))

exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;

//添加头结点returnOK;}//InOrderThreading

……100if(!T)

Thrt->lchild=Thrt;

//若二叉树空，则左指针回指else{Thrt->lchild=T;

pre=Thrt;InThreading(T,pre);

//中序遍历并线索化

pre->rchild=Thrt;//处理最后一个结点pre->RTag=Thread;

Thrt->rchild=pre;

}101二叉树小结1、定义和性质2、存储结构3、遍历4、线索化：线索树顺序结构链式结构二叉链表三叉链表先序线索树中序线索树后序线索树树二叉树森林中序遍历后序遍历先序遍历赫夫曼树赫夫曼编码1026.4树和森林6.4.1树的存储结构6.4.2树和森林与二叉树的转换6.4.3树和森林的遍历1036.4.1树的存储结构树有三种常用存储方式：①双亲表示法②孩子表示法③孩子兄弟表示法1、用双亲表示法来存储思路：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置。parentsdata结点结构dataparents1树结构23n104ABCGEIDHF缺点：求结点的孩子时需要遍历整个结构。01234567812233ABCDEFGHI-1001例1:双亲表示法105

typedefstructPTNode{Elemdata;

intparent;//双亲位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:106typedefstruct{

PTNodenodes[MAX_TREE_SIZE];

intr,n;//根结点的位置和结点个数

}PTree;树结构:107思路一：多重链表第一种结点结构：同构的结点结构？有n个结点度为k的树种有nk-（n-1）个空链域第二种结点结构：异构的结点结构思路二：将每个结点的孩子结点排列起来，形成一个孩子链表，则n个结点要设立n个孩子链表； 每个孩子链表再设一个头结点，用于存放双亲和表头指针，这些头结点可以用数组存放起来，这样就形成一个混合结构。2、用孩子表示法来存储108typedefstructCTNode{

intchild;

structCTNode*nextchild;}*ChildPtr;孩子结点结构:

childnextchildC语言的类型描述:109

typedefstruct{ElemTypedata;ChildPtrfirstchild;//孩子链的头指针

}CTBox;孩子链表头结点(双亲结点结构)

datafirstchild110typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//结点数和根结点的位置

}CTree;树结构:111r=0n=6datafirstchildABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4645123孩子链表表示法示例:-1000224112思路：用二叉链表来表示树，但链表中的两个指针域含义不同。左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild3、用孩子兄弟表示法来存储指向左孩子指向右兄弟113typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C语言的类型描述:结点结构:

firstchilddatanextsibling114abecdfhgbacedfgh设问：树转二叉树的“连线—抹线—旋转”如何由计算机自动实现？例如：1156.4.2树和森林与二叉树的转换树和二叉树如何互相转换？森林和二叉树如何互相转换？116树与二叉树转换ACBED树ABCDE二叉树A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^对应存储存储解释解释117转换步骤：step1:将树中同一结点的孩子（兄弟）相连;step2:保留结点的最左孩子连线，删除其它孩子连线；step3:将同一孩子的连线绕左孩子旋转45度角。加线抹线旋转讨论1：树如何转为二叉树？118将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关