数据结构树和二叉树

第6章树

陈守孔孟佳娜陈卓2024/12/212024/12/2第6章树6.1树的概念及操作6.2二叉树

6.2.1二叉树的概念及操作

6.2.2二叉树的性质6.2.3二叉树的存储结构6.3二叉树的遍历6.4线索二叉树6.5树和森林6.5.1树的存储结构

6.5.2森林、树、二叉树的相互转换

6.5.3树和森林的遍历6.6哈夫曼树及其应用

6.6.1最优二叉树(哈夫曼树)6.6.2哈夫曼编码6.7算法设计举例22024/12/2主要内容知识点树和二叉树定义二叉树的性质，存储结构二叉树的遍历及遍历算法的应用**线索二叉树二叉树和树及森林的关系Huffman树与Huffman编码重点难点二叉树的性质及应用二叉树的遍历算法及应用**线索二叉树的算法Huffman树的构造方法树的算法32024/12/2树例与特征社会的组织结构家族的族谱计算机中的目录组织描述层次结构，是一种一对多的逻辑关系42024/12/2树的定义树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。（注：有人定义树不能为空）有且仅有一个称为根的结点（Root）；n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合又是一棵树，称为子树(SubTree)FGIJABCEDH52024/12/2树的定义树的递归定义的各子树T1,T2,…,Tm的相对次序是重要的，即树是有序的。62024/12/2树定义T1T2T372024/12/2树的抽象数据类型ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下定义的二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D-{root}

,则存在D-{root}的一个划分D1，D2,…,Dm（m>0）,对任意j

k(1

j,k

m)有Dj

Dk=

,且对任意的i(1

i

m),存在唯一数据元素xi

Di,<root,xi>

H;

（3）对应于D-{root}的划分，H-{<root,x1>,…<root,xm>}有唯一的一个划分H1,H2,…,Hm(m>0),对任意j

k(1

j,k

m)有Hj

Hk=

,且对任意i(1

i

m)，Hi是Di上的二元关系，（Di，{Hi}）是一棵符合本定义的树，称为根root的子树。

（转下页）

82024/12/2TreeInit(T);TreeChild(T,x,i);Treebuild(T,F);TreeClear(T);Traverse(T);TreeRoot(T);TreeParent(T,x);TreeRightBrother(T,x);TreeLeftBrother(T,x);TreeInsert(T,y,i,x);}ADTTree树的抽象数据类型92024/12/2树的其它表示方式凹入表示嵌套集合广义表A(B(E,F),C,D(G(J),H,I))AEFBIJGHCDABEFCDGJHIFGIJABCEDH102024/12/2结点：一个数据元素及若干指向其子树的分支；结点的度：结点拥有的子树的数目。树的度：树内各结点的度的最大值；叶子（终端结点）：度为0的结点；分支结点（非终端结点）：度不为0的结点；除根结点外，也称内部结点；孩子，双亲，兄弟，堂兄：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；其父结点是兄弟的结点互称堂兄。树的概念112024/12/2概念祖先：从根结点到该结点所经分支上的所有结点。子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。层次：结点在树结构中的层（一般定义根为1层）。深度：树中结点的最大层次称为树的深度。有序树：结点的子树在树中的位置固定，不能互换，称有序树。无序树：子树在树中的位置可以互换。森林：m(m≥0)棵互不相交的树的集合。122024/12/2概念示例结点结点的度(Degree)叶子（Leaf)或终端结点分支结点或非终端结点树的度层次(Level)树的深度(Depth)孩子（child)双亲（Parent)兄弟(Sibling)祖先子孙树的示例132024/12/2二叉树的概念二叉树(BinaryTree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树又同样都是二叉树

特征：每个结点最多只有两棵子树子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清左右子树。142024/12/2二叉树的抽象数据类型ADTBinTree{

数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=

，则R=

，称二叉树为空二叉树；若D

，则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}

,则存在D-{root}={D1,Dr},且

D1

Dr

；（3）若D1

，则D1中存在唯一的元素x1,<root,x1>

H,且存在D1上的关系H1

H；若Dr

,则Dr中存在唯一的元素xr,<root,xr>

H,且存在Dr上的关系Hr

H；H={<root,x1>,<root,xr>,H1,Hr};

（4）（D1，{H1}）是一棵符合本定义的二叉树，称为根的左子树，（Dr，{Hr}）是一棵符合本定义的二叉树，称为根的右子树。基本操作如下：152024/12/2二叉树的抽象数据类型BiTreeInit(BT);BiTreeRoot(BT);BiTreeParent(BT,x);BiTreeLeftChild(BT,x);BiTreeRightChild(BT,x);BiTreeBuild(BT,LBT,RBT);BiTreeInsertLeft(BT,y,x);BiTreeInsertRight(BT,y,x);BiTreeDeleteLeft(BT,x);BiTreeDeleteRight(BT,x);BiTreeClear(BT);BiTraverse(BT);}ADTBinTree

162024/12/2二叉树的五种形态(a)(b)(c)(d)(e)172024/12/2二叉树的性质1.一个非空二叉树的第i层上至多有2i-1个结点（i

1）

证明：i=1,只有根结点，显然成立

设i=k时成立，最多有2k-1

当i=k+1时，最多的结点个数：

2k-1*2=2k-1+1=2k=2(

k+1)-1182024/12/22.深度为k的二叉树至多有2k-1个结点(k

1)

二叉树的性质证明：二叉树的结点个数为：

1+2+…+2k-1=2k-1192024/12/2二叉树的性质3.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设n1为T中度为1的结点数，则总结点数：

n=n0+n1+n2(1)

另：除根结点外，所有结点都有且仅有一个双亲结点，也就是仅有一个分支进入，若B为分支数，则

n=B+1=n1+2*n2+1(2)

由(1)和(2)有：

n1+2*n2＋1=n0+n1+n2

故 n0=n2+1;202024/12/2满二叉树满二叉树：深度为k且有2k-1个结点的二叉树满二叉树考虑到有序性，任一结点在树中都有确切的位置，因此可以对满二叉树进行编号。编号方式为：从上到下，从左到右。212024/12/2完全二叉树完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树编号从1到n的结点一一对应时，称为完全二叉树。完全二叉树222024/12/2完全二叉树特征：叶子结点只可能在层次最大的两层上出现。任一结点，若其左分支下的子孙的最大层次为l，则其右分支下的最大层次为l或l-1，即若结点无左子女，决不应有右子女。232024/12/2完全二叉树的特性（1）1.具有n个结点的完全二叉树的深度:k=证明：假设n个结点的完全二叉树的深度为k，则n的值应大于深度为k-1的满二叉树的结点数2k-1-1，小于等于深度为k的满二叉树的结点数2k-1，即2k-1-1<n≤2k-1

进一步可推导出

2k-1<n+1≤2k两边取对数后，有

k-1<log2(n+1)≤k因为k是整数，所以有k＝

242024/12/2完全二叉树的特性（2）2.如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1、2、3、…、n,则对任一结点i（1

i

n）有

（a）如果i=1,此结点为根结点，无双亲；若i>1,则其双亲结点是

i/2

。（b）如果2i>n,则结点i无左孩子，i为叶子结点,否则其左孩子是结点2i。（c）如果2i+1>n，则结点i无右孩子，否则其右孩子是结点2i+1。252024/12/2示意图2i2i+1i2i+22i+3i+1

i/2

j层j+1层262024/12/2示意图2i2i+1i2i+22i+3i+1LCHILD(i)LCHILD(i+1)RCHILD(i)RCHILD(i+1)

i/2

272024/12/2完全二叉树性质的推论n个结点的完全二叉树中：度为1的结点数为(n+1)%2;

度为0的结点数为

(n+1)/2；度为2的结点数为

(n+1)/2-1；编号最大的分支结点是

n/2；编号最小的叶子结点是n/2+1。n个结点的二叉树：高最多为n；最低为（完全二叉树）。282024/12/2树的叶子与其它结点的关系设度为m的树中度为0,1,2,…,m的结点数分别为n0,n1,n2,…,nm，结点总数为n，分枝数为B，则下面二式成立n=n0+n1+n2+…+nm(1)n=B+1=n1+2n2+…+mnm(2)由(1)和(2)得叶子结点数n0=1+

292024/12/2二叉树的存储结构顺序存储结构链式存储结构302024/12/2二叉树的顺序存储结构整个二叉树可以按照从上到下，从左到右的顺序编号；对于满/完全二叉树，可以从根结点开始按序号存放；对于一般的二叉树，可以参照满二叉树的编号方法进行编号，位置空的结点为“虚结点”。312024/12/2顺序存储结构举例1234567891018910452673完全二叉树322024/12/2顺序存储结构举例123457810181045273一般二叉树332024/12/2顺序存储结构举例ABC非完全二叉树XABCØØØØAØBØØØC

342024/12/2二叉树的链式存储结构二叉链表三叉链表（线索链表）lchilddatarchilddatalchildrchildlchilddatarchildparentdatalchildrchildparent352024/12/2链式存储结构示例ACFEDBADBCEF∧∧∧∧∧∧∧A∧∧∧∧∧BCDEF∧∧∧∧∧∧∧二叉链表三叉链表362024/12/2二叉链表的类C表示

二叉树的二叉链表存储表示typedefstructBiNode{ElemTytedata;structBiNode*lchild,*rchild;

左右孩子指针

}BiNode,*BiTree；372024/12/2二叉树的遍历

二叉树的遍历的定义：按某种规律，访问二叉树的结点，使每个结点被访问一次且仅一次。访问的含义包括查询、打印、计算、修改等对结点的操作。遍历的过程，实际上是按某种规律，将一个非线性结构的结点排成一个线性序列，使每个结点在这种遍历中有唯一前驱和后继关系。一棵二叉树的遍历序列（在某种遍历方式下）是唯一的，但一般说，二叉树不能由某一遍历序列唯一确定。382024/12/2二叉树的遍历

前序遍历二叉树中序遍历二叉树后序遍历二叉树访问根结点；前序遍历左子树；前序遍历右子树；

中序遍历左子树；访问根结点；中序遍历右子树；

后序遍历左子树；后序遍历右子树；

访问根结点；DLRLDR、LRD、DLRRDL、RLD、DRL若二叉树为空，则空操作，否则：层次遍历二叉树392024/12/2ADBCDLRADLRDLR>B>>D>>CDLR前序遍历序列：ABDC前序遍历402024/12/2ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历序列：BDAC中序遍历412024/12/2ADBCLRDLRDLRD>A>>D>>CLRD后序遍历序列：DBCA后序遍历B422024/12/2遍历图例ACFEDB中序序列为：DBEACF

前序序列为：ABDECF

后序序列为：DEBFCA

432024/12/2中序遍历二叉树的递归算法voidInOrderTraverse(BiTreeT){if(T)二叉树非空

{InOrderTraverse(T->lchild);

中序遍历左子树

visit(T->data);

访问根结点

InOrderTraverse(T->rchild);

中序遍历右子树

}if}InOrderTraverse

442024/12/2图例CFEDBA452024/12/2递归遍历举例abcdgefABCDEF前序序列：abdefcg中序序列：dfebagc后序序列：fedbgca前序序列：abcdef中序序列：cbefda后序序列：cfedba462024/12/2二叉树的中序非递归遍历设S为一个栈，t为指向根结点的指针，其处理过程为：（1）当t非空时，将t所指结点的地址进栈，并将t指向该结点的左子树；（2）当t为空时，弹出栈顶元素，显示结点元素，并将t指向该结点的右子树；（3）重复（1）、（2）步骤，直到栈空且t也为空。

472024/12/2非递归中序遍历栈S的变化－cba×t→”－”－－t→”×”×t→”a”－×at→”NULL”a出栈－×t→”NULL”×出栈－－bt→”b”－t→”NULL”b出栈t→”NULL”－出栈t→”c”ct→”NULL”c出栈t→”NULL”栈空结束482024/12/2voidInOrderTraverse1(BiTreeT){∥中序遍历二叉树的非递归算法，Visit是访问元素的函数

StackInit(S);∥建栈

p=T;while(p||!StackEmpty(S)){while(p){Push(S，p);∥二叉树非空，根结点进栈

p=p->lchild;∥遍历左子树

}∥ifif（！StackEmpty(S)）

{Pop(S，p);Visit(p->data);p=p->rchild;∥遍历右子树

}∥if}}

中序非递归遍历算法492024/12/2voidpostorder(BiTreet)

{typedefstructnode{BiTreet;inttag;//tag0..1}stack;stacks[n+1];top=0;while(t!=null||top!=0){while(t!=null){s[++top].t=t;s[top].tag=0;t=t->lchild;}while(top!=0&&s[top].tag==1)printf(s[top--].t->data:3);if(top){s[top].tag:=1;t=s[top].t->rchild;}}

}

postorder后序非递归遍历算法502024/12/2建立二叉树BiTreeCreatBiTree(){

按前序构造二叉链表表示的二叉树TBiTreeT;scanf(&ch);if(ch==’*’)T=NULL;*表示空

else{T=(BiNode*)malloc(sizeof(BiNode));T->data=ch;生成根结点

T->lchild=CreatBiTree();生成左子树

T->rchild=CreatBiTree();生成左子树

}ifreturnT;}

CreatBiTree

512024/12/2二叉树结构的性质

已知二叉树的先序序列和中序序列，可以唯一确定一棵二叉树。已知二叉树的后序序列和中序序列，可以唯一确定一棵二叉树；已知二叉树的先序序列和后序序列，不能唯一确定一棵二叉树；已知二叉树的层次序列和中序序列，可以唯一确定一棵二叉树。522024/12/2构造二叉树

已知二叉树的

先序序列ABDFCEHG

中序序列DBFAHECG请构造该二叉树。

532024/12/2构造二叉树

已知二叉树的

后序序列DMFBHELGCA

中序序列DBMEAHECGL请构造该二叉树。

542024/12/2构造二叉树试找出满足下列条件的二叉树1）先序序列与后序序列相同2）中序序列与后序序列相同3）先序序列与中序序列相同4）中序序列与层次遍历序列相同

552024/12/2表达式的二叉树表示用二叉树可以表示表达式<exp1><optr><exp2>前序遍历：*+++ab*c+def+gh中序遍历：a+b+c*d+e+f*g+h后序遍历：ab+cde+*+f+gh+*表达式:((a+b)+c*(d+e)+f)*(g+h)562024/12/2二叉树遍历算法的应用(1)以二叉链表作存储结构，试编写求二叉树深度的算法。intBinTreeDetth(BiTreeT){if(T==NULL)return0;else{l=BinTreeDetth(T->lchild);r=BinTreeDetth(T->rchild);return((l>r?l+1:r+1);}}572024/12/2二叉树遍历算法的应用(2)以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。intLeafCount(BiTreeT){if(!T)return0;//空树没有叶子

elseif(!T->lchild&&!T->rchild)return1;//叶子结点

elsereturnLeafCount(T->lchild)+LeafCount(T->rchild);//左子树叶子数加上右子树叶子数}582024/12/2二叉树遍历算法的应用(3)以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。intnum=0;voidLeafCount(BiTreeT){if(T){LeafCount(T->lchild);//中序遍历左子树

if(!T->lchild&&!T->rchild)num++;//访问根结点

LeafCount(T->rchild);//中序遍历右子树

}}592024/12/2二叉树遍历算法的应用(4)以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树。voidchange(BiTree*T){if(*T!=NULL){change(&(*T)->lchild);change(&(*T)->rchild); *t=(*T)->lchild; (*T)->lchild=(*T)->rchild; (*T)->rchild=*t; }}

602024/12/2二叉树遍历算法的应用(5)以二叉链表作为存储结构，设计算法拷贝二叉树。BiTreecopy(BiTreeT){BiTreeT1;if(T==null)T1=null;else{T1=(BiTree)malloc(sizeof(BiNode));//申请结点

T1->data=T->data;T1->lchild=copy(T->lchild);T1->rchild=copy(T->rchild); }returnT1;}

612024/12/2二叉树遍历算法的应用(6)由顺序存储的n个结点的完全二叉树建立二叉链表存储的二叉树。BiTreecreat(ElemTypeA[],inti){BiTreeT;if(i>n)T=null;else{T=(BiTree)malloc(sizeof(BiNode));//申请结点

T->data=A[i];T->lchild=creat(A,2*i);T->rchild=creat(A,2*i+1); }returnT;}

//初始调用：p=creat(A,1);622024/12/2二叉树遍历算法的应用(7)设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组pre[1..n]和mid[1..n]中，试遍写算法建立该二叉树的二叉链表。

voidPreInCreat(BiTreeroot,ElemTypepre[],in[],intl1,h1,l2,h2)//根据二叉树前序序列pre和中序序列in建立二叉树。l1,h1,l2,h2是序列第一和最后元素下标。{root=(BiTree)malloc(sizeof(BiNode));//申请结点root->data=pre[l1];//pre[l1]是根for(i=l2;i<=h2;i++)if(in[i]==pre[l1])break;//在中序序列中，根结点将树分成左右子树if(i==l2)root->lchild=null;//无左子树elsePreInCreat(root->lchild,pre,in,l1+1,l1+(i-l2),l2,i-1)；

//递归建立//左子树if(i==h2)root->rchild=null;//无右子树elsePreInCreat((*root)->rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2)//递归建//立右子树}//结束PreInCreat632024/12/2线索二叉树

线索二叉树的提出：

1、遍历的实质：非线性结构线性化（前驱、后继）;2、前驱和后继是在遍历中得到的;3、知道前驱和后继，再遍历时就不需要栈;4、可以在二叉链表结构中增加前驱和后继两个指针域;5、n个结点的二叉树有n＋1个空指针，可以利用。642024/12/2线索二叉树

n个结点的二叉链表中含有n+1个空指针域，可以利用这些空指针域来存放结点的前驱和后继的信息,这样的的指针称为“线索”，加上了线索的二叉链表称为线索链表，加上线索的二叉树就是线索二叉树（ThreadedBinaryTree）。将二叉树变为线索二叉树的过程称为线索化。

lchildltagdatartagrchildltag=

rtag=

652024/12/2线索二叉树

<？序><前驱/后继/全>线索化只有空指针才能加线索662024/12/2前序前驱线索化前序前驱线索化ABECFGHIDABECFGHID672024/12/2中序（全）线索二叉树NULLACFEDBNULLA00E11C01D11F11B00NULLA

为方便起见，在线索链表中增加一个头结点，令其lchild域指向二叉树的根结点，rchild域指向访问序列的最后一个结点，这样，就建立了一个双向线索链表。68

皮肌炎是一种引起皮肤、肌肉、心、肺、肾等多脏器严重损害的，全身性疾病，而且不少患者同时伴有恶性肿瘤。它的1症状表现如下：1、早期皮肌炎患者，还往往伴有全身不适症状，如-全身肌肉酸痛，软弱无力，上楼梯时感觉两腿费力；举手梳理头发时，举高手臂很吃力；抬头转头缓慢而费力。皮肌炎图片——皮肌炎的症状表现2024/12/2后序（全）线索化702024/12/2类型定义typedefstructBiThrNode{ElemTytedata;structBiThrNode*lchild,*rchild;

左、右孩子指针

intltag,rtag;}BiThrNode，*BiThrTree712024/12/2前序线索化BiThrTreepre=null;//设置前驱voidPreOrderThreat(BiThrTreeT){if(T!=null){if(T->lchild==null){T->ltag=1;T->lchild=pre;}//设置左线索

if(T->rchild==null)T->rtag=1;//为建立右链作准备

if(pre!=null&&pre->rtag==1)pre->rchild=T;//设置前驱的右线索；

pre=T;//前驱后移

if(T->ltag==0)PreOrderThreat(T->lchild);//左子树前序线索化

PreOrderThreat(BT->rchild);//右子树前序线索化

}}722024/12/2中序线索化二叉树BiThrTreepre=null;//设置前驱voidInOrderThreat(BiThrTreeT){if(T)

{InOrderThreat(T->lchild);//左子树中序线索化

if(T->lchild==null){T->ltag=1;T->lchild=pre;}//左线索为pre;if(T->rchild==null)T->rtag=1;//置右标记，为右线索作准备

if(pre!=null&&pre->rtag==1)pre->rchild=T;}//给前驱加后继线索

pre=T;//前驱指针后移

InOrderThreat(T->rchild);//右子树中序线索化

}

}//结束InOrderThreat

732024/12/2后序线索化二叉树BiThrTreepre=null;//设置前驱voidPostOrderThreat(BiThrTreeT){if(T)

{PostOrderThreat(T->lchild);//左子树后序线索化

PostOrderThreat(T->rchild);//右子树后序线索化

if(T->lchild==null){T->ltag=1;T->lchild=pre;}//左线索为pre;if(T->rchild==null)T->rtag=1;//置右标记，为右线索作准备

if(pre!=null&&pre->rtag==1)pre->rchild=T;}//给前驱加后继线索

pre=T;//前驱指针后移

}

}//结束PostOrderThreat

742024/12/2线索二叉树的中序遍历voidInorderTraverseThr(BiThrTreep){while(p)

二叉树非空

{while(p->tag==0)

找中序序列的开始结点

p=p->lchild;

printf(p->data); while(p&&p->rtag==1){p=p->rchild;printf(p->data);}//找P的中序后继结点

if(p)p=p->rchild;}//while}

InorderTraverseThr752024/12/2带头结点的线索二叉树的中序遍历voidInorderTraverseThr(BiThrTreethrt){p=thrt->lchild;while(p!=thrt)

二叉树非空

{while(p->ltag==0)

找中序序列的开始结点

p=p->lchild;printf(p->data); while(p->rtag==1&&p->rchild!=thrt){p=p->rchild;printf(p->data);}//找P的中序后继结点

p=p->rchild;}//while(p!=thrt)}

InorderTraverseThr762024/12/2前序线索树上找前驱和后继找前驱：困难找后继：

若结点有左子女，则左子女是后继；否则，rchild指向后继。772024/12/2前序线索树上找后继BiThrTreePreorderNext(BiThrTreep){if(p->ltag==0)

结点有左子女

return(p->lchild);

结点的左子女为其前序后继

else

return(p->rchild);}

PreorderNext782024/12/2中序线索树上找前驱和后继

中序的前驱和后继都往上指向祖先找前驱：若左标记为1，则lchild指向其前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。找后继：若右标记为1，则rchild指向其后继；否则，其后继是其右子树上按中序遍历的第一个结点。792024/12/2中序线索树上找前驱BiThrTreeInorderPre(BiThrTreep){BiThrTreeq;if(p->ltag==1)

结点的左子树为空

q=p->lchild

结点的左指针域为左线索，指向其前驱

else{q=p->lchild;

p结点的中序前驱是左子树中最右边结点

while(q->rtag==0)q=q->rchild;

}

ifreturn(q);}

InorderPre802024/12/2中序线索树上找后继BiThrTreeInorderNext(BiThrTreep){BiThrTreeq;if(p->rtag==1)

结点的右子树为空

q=p->rchild

结点的右指针域为右线索，指向其后继

else{q=p->rchild;

P结点的中序后继是其右子树中最左边结点

while(q->ltag==0)q=q->lchild;

}

ifreturn(q);}

InorderNext812024/12/2后序线索树上找前驱和后继找前驱：若结点有右子女，则右子女是其前驱；否则，lchild指向其前驱。找后继：困难，需要知道其双亲。822024/12/2后序线索树上找前驱BiThrTreePostorderPre(BiThrTreep){if(p->rtag==0)

结点有右子女

return(p->rchild);

结点的右子女为其后序前驱

else

return(p->lchild);}

PreorderPre832024/12/2线索树上结点的插入与删除除修改结点指针外，还需要修改线索。842024/12/2树的存储结构考虑存储结构时，主要考虑逻辑结构：数据元素数据元素之间的关系树的存储结构：链式存储结构852024/12/2树的存储结构ABECDF双亲表示法

孩子表示法

孩子兄弟表示法

862024/12/2双亲表示法使用静态数组（本质是静态链表）；数组的每个数据元素，包括两个域：一个域是数据元素；另一个域用游标指示该结点的双亲结点在数组中的相对位置；根结点的游标为-1。特点：方便找结点的双亲；顺序存储结构；872024/12/2双亲表示法类型定义#defineMAX_NODE64typedefstructPtnode{ElemTytedata;

数据域

intparent;

双亲指示域

}Ptnode；typedefstruct

{Ptnodenodes[MAX_NODE];intn;}Ptree;

882024/12/2双亲表示示例ACGEDBHF

数组下标

01234567dataABCDEFGHparent-10011222892024/12/2双亲表示法表示的树的深度intDepth(Ptreet){intmaxdepth=0;for(i=1;i<=t.n;i++){temp=0;f=i;while(f>0)//求结点i的深度

{temp++;f=t.nodes[f].parent;}

if(temp>maxdepth)//最大深度更新

maxdepth=temp;}return(maxdepth);//返回树的深度}//结束Depth902024/12/2孩子表示法任一数据元素，有0个或多个孩子；因此可以设计一个链式存储结构，其结点除放置数据元素外，还放置若干指针，分别用来指示该结点的所有孩子结点在存储空间中的位置。912024/12/2孩子表示法方法1根据结点的度，设置结点的指针个数，比如若结点的度为d:datachild1child2…childd问题：不同的数据元素，结点构造不同；操作不方便922024/12/2孩子表示法方法2按照树的度定义结点。若树的度为d,定义degree，表示该结点的度datachild1child2…childddegree问题：因degree为树的度，是所有结点的最大的度，因此树中有相当部分的指针域为空，浪费空间。有n个结点的树的度为k，空指针域有

n(k-1)+1个。932024/12/2孩子表示法有n个结点的树的度为k，空指针域有n(k-1)+1个。证明：n个结点的树，除根结点外，每个结点有一个指针指向，也就是树中有n-1个有效链域（指针）而按该结点定义，n个结点总的指针域有：nk个。因此空链域：

nk–(n-1)=n(k-1)+1942024/12/2一个静态数组，存放所有的结点数组的每个数据元素，包括两部分：数据元素，指针；指针指向一个链表，链表结点的数据域是一个整数，表示该结点的孩子在数组中的相对位置；特点：顺序+链式存储结构；找孩子容易，找双亲难；孩子表示法952024/12/2孩子表示法ACGEDBHF01234567∧∧∧∧657∧ABCDEFG312∧4∧∧H962024/12/2双亲孩子链表在静态数组的结点中增加一个域，表示该结点的双亲在该树组中的相对位置。有利于寻找孩子结点和双亲结点。ACGEDBHF01234567657∧312∧∧G∧∧∧ABCDEF-1001122parent4∧H2∧972024/12/2孩子表示法类型定义#defineMAX_NODE64typedefstructCtnode孩子结点{intchild;structCtnode*next;}*childlink; typedefstruct头结点{ElemTypedata;childlinkfirstchild;}CTBox;CTBoxnodes[MAX_NODE]；982024/12/2孩子兄弟表示法从向下的纵向和向右的横向描述树；定义结点，除存放数据元素外，存放两个指针，一个指向该结点的第一个孩子，另一个指向该结点的下一个兄弟；992024/12/2孩子兄弟表示法typedefstructCSNode{ElemTytedata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;

该表示方法又称二叉树表示法，本质上与二叉链表表示法一致。datafirstchildnextsibling1002024/12/2孩子兄弟表示法A∧BC∧D∧E∧F∧G∧∧H∧∧ACGEDBHF1012024/12/2孩子-兄弟表示法算法示例intLeaves(Treet)//计算以孩子-兄弟表示法存储的森林的叶子数{if(t==null)return0;else{if(t->firstchild==null)//无孩子的结点必是叶子

return(1+Leaves(t->nextsibling));

//返回叶子结点和其兄弟子树中的叶子结点数

elsereturn(Leaves(t->firstchild)+Leaves(t->nextsibling));//孩子子树和兄弟子树中叶子数之和

}}//结束Leaves1022024/12/2孩子-兄弟表示法算法示例intHeight(CSTreebt)//递归求以孩子兄弟链表表示的树的深度{inthc,hs;if(bt==null)return(0);elseif(!bt->firstchild)returnmax(1,height(bt->nextsibling））；

//子女空，取1和兄弟的深度的大者

else{hc=height(bt->firstchild)；//第一子女树高

hs=height(bt->nextsibling)；//兄弟树高

if(hc+1>hs)return(hc+1);elsereturn(hs);//高度取子女高度+1和兄弟子树高度的大者

}}//结束height1032024/12/2若树采用孩子兄弟表示法，二叉树采用二叉链表表示，则从存储结构上看，结点定义完全相同。因此，在使用该存储结构下，树和二叉树是等价的，树可以转化为二叉树。树和二叉树的转化步骤（1）连线：在兄弟结点之间加一条连线。（2）切线：对于每个结点，除了保留与其最左孩子的连线外，切掉该结点与其它孩子的连线。（3）旋转：将按（1）、（2）的方法形成的二叉树，沿顺时针方向旋转450,就可以得到一棵形式上更为清楚的二叉树。

1042024/12/2树和二叉树转化例FGHABCEDFGHABCEDFGHABCEDFHABGCED1052024/12/2将树转换成二叉树树转换成的二叉树其右子树一定为空ABCDEFGHIJKLABCDEFGHIJKL1062024/12/2森林到二叉树的转换若树采用孩子兄弟表示法，二叉树采用二叉链表表示，则：任一棵树，都可以找到唯一的一棵二叉树和它对应，而且该二叉树没有右子树。(因此一棵二叉树，不一定保证能转换为一棵(>=1)树)若把森林中的第二棵树的根结点，看成是第一棵树的根结点的兄弟结点，则这两棵树可以转换为一棵二叉树（该二叉树的根结点的右子女没有右子树）。依次类推，可以认为森林和二叉树是一一对应的，从而得到二叉树和森林的转换规则1072024/12/2森林到二叉树的转换步骤：（1）连线：在兄弟（各树的根结点看作兄弟）结点之间加一条连线。（2）切线：对于每个结点，除了保留与其最左孩子的连线外，切掉该结点与其它孩子的连线。（3）旋转：将按（1）、（2）的方法形成的二叉树，沿顺时针方向旋转450,就可以得到一棵形式上更为清楚的二叉树。1082024/12/2AGJBCDHIKEFLMN将森林转换成二叉树ABGCEHFJKILMND1092024/12/2二叉树到森林的转换

如果B={root,LBT,RBT}是一棵二叉树，F={T1,T2,…,Tn}表示与其对应的森林，转换规则如下：（1）若B为空，则F为空；（2）若B非空，则F中第一棵树T1的根即为二叉树B的根root，T1中根结点的子树森林F1是由B的左子树LBT转换而成的森林；F中除T1之外其余树组成的森林F’={T2,T3…,Tn}是由B的右子树RBT转化而成的森林。1102024/12/2二叉树到森林的转换例1IABDFGHKCEJIABDJHCEFGK1112024/12/2DEFGHIJLABCKFILCABEGHJKD二叉树到森林的转换例21122024/12/2树和森林的遍历

树的遍历：（1）前序遍历（2）后序遍历森林的遍历：（1）前序遍历（2）中序遍历1132024/12/2树的遍历前序遍历树的规则为：若树非空，则：（1）访问树的根结点；（2）依次前序遍历树的第一棵子树、第二棵子树，……后序遍历树的规则为：若树非空，则：（1）依次后序遍历树的第一棵子树、第二棵子树，……（2）访问树的根结点；

ABCED前序遍历序列：ABCDE后序遍历序列：BCEDA1142024/12/2树的遍历与二叉树遍历对应

树的前序遍历序列与其对应的二叉树的前序遍历序列相同；

树的后序遍历序列与其对应的二叉树的中序遍历序列相同；1152024/12/2森林的遍历前序遍历森林的规则为：若森林为空，返回；否则：（1）访问森林中第一棵树的根结点；（2）前序遍历第一棵树的子树森林；（3）前序遍历其它树组成的森林；

中序遍历森林的规则为：若森林为空，返回；否则：（1）中序遍历第一棵树的子树森林；（2）访问第一棵树的根结点；（3）中序遍历除第一棵树外其它树组成的森林；

ABCFGHJIED右图森林的前序遍历序列为：

ABCDEFGHIJ右图森林的后序遍历序列为：BDCAFEHIJG1162024/12/2森林的遍历与二叉树的遍历对应

森林的先序遍历序列与其对应的二叉树的先序遍历序列相同；

森林的中序遍历序列与其对应的二叉树的中序遍历序列相同；1172024/12/2哈夫曼树的概念路径：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径。路径长度：路径上的分支数目称为路径长度。树的路径长度：树的根结点到树中每一个结点的路径长度的和。1182024/12/2结点的带权的路径长度：该结点到根结点之间的路程长度与该结点上权的乘积树的带权的路径长度：树中所有叶子结点的带权的路径长度的和。通常记为：WPL(WeightedPathLength)。由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或哈夫曼（Huffman）树。哈夫曼树的概念（续）1192024/12/2

有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35dcab24751202024/12/2哈夫曼树的性质1、哈夫曼树只有度为0和2的结点，无度为1的结点；2、权值大的结点离根结点近；3、n个叶子的哈夫曼树的形态一般不唯一，但WPL是相同的；4、n个叶子的哈夫曼树共有2n-1个结点。1212024/12/2根据给定的n个权值{w1,w2,…,wn}，构造n棵只有根结点的二叉树，令其权值为wj;在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和;在森林中删除这两棵树，同时将新得到的二叉树加入森林中;重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。构造Huffman树步骤1222024/12/2dcba9653ba96358a9614358962314538abcdcbd哈夫曼树的构造举例1232024/12/2例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100哈夫曼树的形态是不唯一的1242024/12/2已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试构造哈夫曼树。举例1252024/12/2哈夫曼树的类型定义typedefstruct{intweight;intparent,lchild,rchild;}HufmTree;1262024/12/2哈夫曼树的构造算法viodCreatHuffman(HufmTreetree[]，intn){

构造哈夫曼树，n为初始森林中的结点数

inti,j,t1,t2；

if(n<=1)retu