信息与通信数据结构chapter 6 树和二叉树课件

18-Nov-221第六章树和二叉树树是一类重要的非线性数据结构，是以分支关系定义的层次结构典型例子：企业的管理机构计算机文件系统09-Nov-221第六章树和二叉树树是一类重要的非线性数18-Nov-222

第一节树的定义树(Tree)的定义树是由n(n0)个节点组成的有限集合。如果n=0，称为空树；如果n>0，则:有且仅有一个特定的称之为根(root)的节点，它只有直接后继，但没有直接前驱；如果n>1，则：除根以外的其它节点可以划分为m(m>0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称为根的子树(subTree)。每棵子树的根节点有且仅有一个直接前驱，但可以有0个或多个直接后继。特点：非空的树至少有一个根节点树中各子树是互不相交的集合09-Nov-222第一节树的定义树(Tree)的定义18-Nov-223树的示例子树根A只有根节点的树09-Nov-223树的示例子树根A只有根节点的树18-Nov-224

树的基本术语节点(node)：树中的元素。包含一个数据元素及若干指向其子树的分支节点的度(degree)：节点拥有的指向其子树的分支数目分支(branch)节点：度不为0的节点叶(leaf)（终端）节点：度为0的节点树的度：树中所有节点度的最大值孩子(child)与双亲(parent)节点：节点的子树的根称为该节点的孩子，该节点称为孩子的双亲ABCDEFG09-Nov-224树的基本术语节点(node)：树中的18-Nov-225树的基本术语（续）兄弟

(sibling)：同一个双亲的孩子之间互称兄弟。祖先(ancestor)：从根节点到某个节点所经分支上的所有节点。子孙（descendant)：以某个节点为根节点的子树中的所有节点均是该节点的子孙。堂兄弟：双亲在同一个层次上的节点互为堂兄弟。节点所处层次(level)：根为第一层，根的孩子为第二层，依此类推。树的深度(depth)（高度）：树中所有节点层次的最大值。ABCDEFG09-Nov-225树的基本术语（续）兄弟(siblin18-Nov-226树的基本术语（续）有序树与无序树：树的各个子树从左至右的顺序不可以调换则称为有序树，否则为无序树。森林（Forest）：m(m≥0)棵互不相交的树的集合称为森林。对树中每个节点而言，其子树的集合就构成森林。09-Nov-226树的基本术语（续）有序树与无序树：树的各18-Nov-227树的基本术语举例12344节点A的度：3节点B的度：2节点M的度：0叶子：K，L，F，G，M，I，J节点I的双亲：D节点L的双亲：E树的度：3树的深度：4节点B，C，D为兄弟节点K，L为兄弟节点E，G，H为堂兄弟节点A，D，H是M的祖先09-Nov-227树的基本术语举例12344节点A的度：318-Nov-228树的抽象数据类型数据对象D：

D是具有相同特性的数据元素的集合。数据关系R：如果D为空集，则称为空树；如果D中只有一个元素，则R为空集;否则R={H}，H是满足以下条件的二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠Ø,则存在D-{root}上的一个划分D1,D2,…,Dmm>0，对任意j≠k(1≤j,k≤m)有Dj∩Dk=Ø，且对任意的i(1≤i≤m)，唯一存在数据元素xi(xi∈Di),，有<root,xi>∈H(3)对应于D-{root}的划分，H–{<root,x1>,<root,x2>,…,<root,xm>}有唯一的一个划分H1,H2,…,Hmm>0，对任意j≠k(1≤j,k≤m)有Hj∩Hk=Ø，且对任意的i(1≤i≤m)，Hi

是Di

上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。09-Nov-228树的抽象数据类型数据对象D：18-Nov-229树的操作①初始化InitTree(&T);②销毁树DestroyTree(&T)③创建树CreateTree(&T)④清空树ClearTree(&T)⑤判断树是否为空TreeEmtpy(T)⑥求树的深度TreeDepth(T)⑦求树的根Root(T)⑧求树上某个节点的值Value(T,cur_e)⑨给树上某个节点赋值Assign(T,Cur_e,value)⑩返回某个节点的双亲Parent(T,Cur_e)11求某个节点的左孩子LeftChild(T,Cur_e)12求某个节点的右孩子RightChild(T,Cur_e)13求某个节点的右兄弟RightSibling(T,Cur_e)14在树中插入元素InsertChild(&T,&p,i,c)15删除树中的元素DeleteChild(&T,&p,i)16遍历树中所有元素TranverseTree(T,Visit())09-Nov-229树的操作①初始化InitTree(&18-Nov-2210第二节二叉树（BinaryTree）二叉树的定义一棵二叉树是n(n≥0)个节点的有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树的特点每个节点至多有二棵子树(即不存在度大于2的节点)二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树是一种度为2的有序树09-Nov-2210第二节二叉树（BinaryTree18-Nov-2211二叉树的五种不同形态(a)空二叉树(b)仅有根节点的二叉树(c)右子树为空(d)左子树为空(e)左右子树均非空09-Nov-2211二叉树的五种不同形态(a)空二叉树18-Nov-2212二叉树的抽象数据类型数据对象D：

D是具有相同特性的数据元素的集合。数据关系R：如果D=Ø，则R=Ø称为空二叉树；如果D≠Ø，则R={H}，H是满足以下条件的二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠Ø,则存在D-{root}={Dl,Dr},且有Dl∩Dr=Ø(3)如果Dl≠Ø，则Dl中存在唯一元素xl，<root,xl>∈H，且存在Dl上的关系Hl∈H；如果Dr≠Ø，则Dr中存在唯一元素xr，<root,xr>∈H,且存在Dr上的关系Hr∈H，并且有H={<root,xl>,<root,xr>,Hl,Hr}(4)(Dl,{Hl})是一棵符合本定义的二叉树，称为根root的左子树。(Dr,{Hr})是一棵符合本定义的二叉树，称为根root的右子树09-Nov-2212二叉树的抽象数据类型数据对象D：18-Nov-2213二叉树的操作二叉树的操作同普通树的操作类似二叉树的遍历操作是最重要的操作二叉树的遍历包括先序遍历中序遍历后序遍历09-Nov-2213二叉树的操作二叉树的操作同普通树的操作18-Nov-22142二叉树的重要特性性质1

在二叉树的第i层上至多有2i-1(i≥1)个节点证明：第1层只有1个节点1=21-1=20假定第i层的节点个数为2i-1那么由于二叉树每个节点最多有两个分支，因此第i+1层最多会有：2×2i-1=2i-1+1=2(i+1)-1个节点性质2

深度为k的二叉树至多有2k-1(k≥1)个节点证明：09-Nov-22142二叉树的重要特性性质1在二叉18-Nov-2215二叉树的性质(续)性质3

对任何一棵二叉树T，如果其终端节点数为n0

，度为2的节点数为n2，则有：n0=n2+1证明：若设度为1的节点有n1个，总节点个数为n，总分支数为B，则根据二叉树的定义，

n=n0+n1+n2（1）

B=2n2+n1=n–1（2）于是有：2n2+n1=n0+n1+n2-1n2=n0

–1n0=n2+1

09-Nov-2215二叉树的性质(续)性质3对任何一棵18-Nov-2216几种特殊形式的二叉树满二叉树(FullBinaryTree)定义：一棵深度为k，且有2k-1个节点的二叉树被称为满二叉树。特点每一层的节点数目均达到了最大值可以对其按照从上到下，从左到右的原则进行连续编号。

09-Nov-2216几种特殊形式的二叉树满二叉树(Ful18-Nov-2217完全二叉树完全二叉树(CompleteBinaryTree)定义：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时，称之为完全二叉树。完全二叉树的特点：叶子节点只可能在层次最大的两层上出现；对任一节点，若其右分支下的子孙的最大层次为L，那么其左分支下的子孙的最大层次必为L或L+1。

09-Nov-2217完全二叉树完全二叉树(Complete18-Nov-2218满二叉树与完全二叉树图示09-Nov-2218满二叉树与完全二叉树图示18-Nov-2219进一步解释完全二叉树完全二叉树：若共有h层，除第h层外，其它各层(1h-1)的节点数都达到最大个数，第h层从右向左连续缺若干节点，这就是完全二叉树。123114589121367101415123114589126710123456712345609-Nov-2219进一步解释完全二叉树完全二叉树：若共有18-Nov-2220完全二叉树的两个重要性质性质4

具有n个节点的完全二叉树的深度为⌊log2n⌋+1符号⌊x⌋表示不大于x的最大整数。证明：根据完全二叉树的定义，若深度为k,则有：

09-Nov-2220完全二叉树的两个重要性质性质4具有18-Nov-2221完全二叉树的两个重要性质性质5

对于一棵有n个节点的完全二叉树（深度为⌊log2n⌋+1）的节点按照层序编号（从上到下，从左到右），则对于任意一个节点i(1≤i≤n)有：1）如果i=1，则节点是根节点，无双亲；如果i>1，则其双亲是节点是⌊i/2⌋

。2）如果2i>n，则节点i无左孩子，否则其左孩子为2i 3）如果2i+1>n，则节点i无右孩子，否则其右孩子为2i+1性质5说明：在完全二叉树中，如果知道节点的编号就可以用简单的数学运算求出其双亲和孩子的位置。性质5的证明；可以先证明2和3，然后利用2和3的结论来证明1。09-Nov-2221完全二叉树的两个重要性质性质5对于18-Nov-2222性质5的证明假定第i个节点位于第k层，根据二叉树的性质，那么前面k-1层总的节点个数为:2k-1-1个节点第k层第一个节点的编号为2k-1-1+1=2k-1,由此可以知道在第K层的第i个节点前面节点数目为：i-2k-1如果节点i有左孩子，根据完全二叉树的定义，那么第k层中在它前面的节点必然有左右孩子，这些孩子的总数目为：2×（i-2k-1

）且位于第k+1层由于第K+1层第一个节点的编号为2k，那么第i个节点的左孩子的编号必然为：2k+2×（i-2k-1

）=2i，它的右孩子的编号则为2i+1.iK层2k-1K+1层2ii-2k-12k2i+109-Nov-2222性质5的证明假定第i个节点位于第k层，18-Nov-2223第三节二叉树的存储结构一顺序存储结构用一组连续的存储单元依次自上而下、自左至右存储完全二叉树中的所有元素。特点：节点间关系蕴含在其存储位置中只适用于完全二叉树，对于普通的树，可能会造成严重的空间浪费。

09-Nov-2223第三节二叉树的存储结构一顺序存储结18-Nov-2224顺序存储示例09-Nov-2224顺序存储示例18-Nov-2225顺序存储缺点由于完全二叉树的节点数目与树的深度是指数关系，因此如果树的深度较大，所需要的空间是惊人的。单支树示例例：一个深度为k(k=10)的二叉树，如果用顺序存储结构来表示，需要2k-1(1023)个单元，而实际上树中的元素可能只有10个(单支树)。09-Nov-2225顺序存储缺点由于完全二叉树的节点数目与18-Nov-2226顺序存储结构的C语言描述#defineMAX_TREE_SIZE100TElenTypeSqBiTree[MAX_TREE_SIZE]完全二叉树普通二叉树09-Nov-2226顺序存储结构的C语言描述#define18-Nov-2227

二二叉树的链式存储结构

根据不同的需要，可以设计不同的节点结构，从而得到不同的链式存储结构。常用的链式存储结构有两种：二叉链表，节点中有两个指针域，分别指向左右孩子三叉链表，节点中有三个指针域，分别指向左右孩子和父亲09-Nov-2227二二叉树的链式存储结构根据不同的18-Nov-2228二叉链表与三叉链表示例09-Nov-2228二叉链表与三叉链表示例18-Nov-2229二叉链表存储C描述 typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild; }BiTNode,*BiTree;09-Nov-2229二叉链表存储C描述 typedefs18-Nov-2230第四节遍历二叉树在实际应用中通常要在二叉树中查找具有某些特性的节点，或是对二叉树中的所有节点作某种处理，这就需要涉及二叉树的遍历问题。所谓树的遍历，就是按某种次序访问树中的节点，要求每个节点访问一次且仅访问一次。树遍历的典型例子：计算机上删除目录必须找到一种规律，将二叉树转换为一种线性结构，然后进行遍历。

09-Nov-2230第四节遍历二叉树在实际应用中通常要在18-Nov-2231二叉树的遍历方法由于二叉树是由根节点、左子树、右子树三部分组成的,假定访问根节点记作D，遍历根的左子树记作L，遍历根的右子树记作R那么二叉树可能的遍历次序有6种:DLR，DRL，LDR，LRD，RDL，RLD若限定先访问左子树后访问右子树，则可能有三种遍历方法：先（根）序遍历DLR，先访问根，然后是左子树和右子树中（根）序遍历LDR，先访问左子树，然后是根和右子树后（根）序遍历LRD

，先访问左子树和右子树，然后是根09-Nov-2231二叉树的遍历方法由于二叉树是由根节点、18-Nov-2232先序遍历算法表达式语法树若二叉树为空，则空操作；否则访问根节点(D)；先序遍历左子树(L)；先序遍历右子树(R)。举例：先序遍历结果：-+a*b-cd/ef09-Nov-2232先序遍历算法表达式语法树若二叉树为空，18-Nov-2233中序遍历算法若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根节点(D)；中序遍历右子树(R)举例：遍历结果

a+b*c-d-e/f09-Nov-2233中序遍历算法若二叉树为空，则空操作；18-Nov-2234后序遍历算法若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根节点(D)举例：遍历结果abcd-*+ef/-09-Nov-2234后序遍历算法若二叉树为空，则空操作；18-Nov-2235三种遍历算法示例先序遍历得到的序列为：ABDEHIJKCFG中序遍历得到的序列为：DBHEJIKAFCG后序遍历得到的序列为：DHJKIEBFGCA09-Nov-2235三种遍历算法示例先序遍历得到的序列为：18-Nov-2236先序遍历算法的C语言描述Statuspreordertranverse(BiTreeT,statsus(*visit)(TelemType){ if(T){ visit(T->data); preorderTranverse(T->lchild,visit); preorderTranverse(T->rchild,visit); } returnOK;}09-Nov-2236先序遍历算法的C语言描述Status18-Nov-2237C语言函数的递归调用如果函数体中的某语句调用函数本身，那么这个函数是递归的。例：定义阶乘n!的递归函数factr(intn)与非递归fact(intn)factr(intn){intanswer;if(n==1)return1;answer=factr(n-1)*n;returnanwser;}fact(intn){intt,answer;answer=1;for(t=1;t<=n;t++)answer=answer*t;returnanwser;}09-Nov-2237C语言函数的递归调用如果函数体中的某语18-Nov-2238递归程序递归程序的主要优点是能够使某些算法更清晰简洁。编写递归函数时必须在恰当的位置放置if条件语句，让递归函数不需要继续递归而是立即返回。函数调用自己时在栈上为局部变量和参量分配存储空间，从头执行函数代码，并不复制函数代码。09-Nov-2238递归程序递归程序的主要优点是能够使某些18-Nov-2239递归示例1：统计叶子节点数目intCountLeafNum(BiTreeT){ if(T==NULL)return0;if(T->lchild==NULL&&T->rchild==NULL) return1; returnCountLeafNum(T->lchild)+ CountLeafNum(T->rchild);}09-Nov-2239递归示例1：统计叶子节点数目intC18-Nov-2240递归示例2：计算树的高度intComputeTreeHeight(BiTreeT){ intlh;intrh; if(T==NULL)return0;if(T->lchild==NULL&&T->rchild==NULL) return1; lh=ComputeTreeHeight(T->lchild);rh=ComputeTreeHeight(T->rchild);

return(lh>rh?lh+1:rh+1);}09-Nov-2240递归示例2：计算树的高度intCom18-Nov-2241中序遍历非递归算法(1)statusInOrderTraverse(BiTreeT,Status(*Visit)(TElemente)){ 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);} } }returnOK;}09-Nov-2241中序遍历非递归算法(1)status18-Nov-2242非递归算法(1)示意图abcdeTaStackPbPcPnullPOutput:ceP09-Nov-2242非递归算法(1)示意图abcdeTaS18-Nov-2243中序遍历非递归算法(2)statusInOrderTranverse(BiTreeT，

Status(*Visit)(TElemente))){InitStack(S);p=T;while(p||!EmptyStack(S)){if(p){push(S,p);p=p->lchild;}else{pop(S,p);visit(p->data);p=p->rchild;}}returnOK;}

09-Nov-2243中序遍历非递归算法(2)status18-Nov-2244非递归算法(2)示意图abcdeTaStackPbPcPOutput:cePPP两种方法的区别是（2）的处理要简洁些，空指针不需要入栈，而方法(1)有多次的空指针入栈、出栈操作。09-Nov-2244非递归算法(2)示意图abcdeTaS18-Nov-2245先序遍历非递归算法statusPreOrderTranverse(BiTreeT，

Status(*Visit)(TElemente))){InitStack(S);p=T;while(p||!EmptyStack(S)){if(p){visit(p->data);push(S,p);p=p->lchild;}else{pop(S,p);p=p->rchild;}}returnOK;}

09-Nov-2245先序遍历非递归算法statusPre18-Nov-2246二叉树形态与遍历结果的关系当二叉树的形态确定后，那么它的先序、中序和后序遍历的结果就已经确定。但是单纯根据二叉树的先序、中序或后序遍历的序列不可能完全确定二叉树的形态。如果要完全确定二叉树的形态需要知道先序和中序的结果，或是中序和后序遍历的结果09-Nov-2246二叉树形态与遍历结果的关系当二叉树的形18-Nov-2247创建二叉树单纯根据先序、中序或后序无法完全确定二叉树的形态因此必须在输入过程中输入特殊的字符来表示某个节点的左右子树是否为空，以便帮助建立二叉树比如：要建立右面的二叉树，则输入先序序列为：ABCφφDEφGφφHφφφ特殊符号φ用来表示子树为空09-Nov-2247创建二叉树单纯根据先序、中序或后序无法18-Nov-2248按先序序列建立二叉树的C算法StatusCreateBitree(BiTree&T){scanf(“%c”,&ch);if(ch==‘特殊符号’)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))returnERROR;T->data=ch;CreateBitree(T->lchild);CreateBitree(T->rchild);}returnOK;}09-Nov-2248按先序序列建立二叉树的C算法Statu18-Nov-2249二叉树遍历C程序演示演示如何根据插入了特殊符号的先序序列建立完整的二叉树演示如何利用递归算法实现树的先序、中序和后序遍历演示如何利用递归计算树的高度和叶子数目程序example61.c09-Nov-2249二叉树遍历C程序演示演示如何根据插入了18-Nov-2250第五节线索二叉树二叉树遍历后得到一个节点的线性序列每个节点都有自己的前驱和后继先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEAABCDEFGHK09-Nov-2250第五节线索二叉树二叉树遍历后得到一18-Nov-2251基本概念问题：能否利用这些空指针域来指向遍历结果中的前驱和后继？现象：节点中有很多空的指针区域有n个节点的二叉树必然有n+1个空指针域赋予新用途的空指针被称为“线索”09-Nov-2251基本概念问题：能否利用这些空指针域来指18-Nov-2252线索示意图ABCDEFGHK先序序列:ABCDEFGHK^D^

C^^B

E^D09-Nov-2252线索示意图ABCDEFGHK先序序列:区分子树和线索的方法为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域ltagltag=LINKlchild域指向其左子树ltag=THREADlchild域指向其“前驱”rtagrtag=LINKrchild域指向其右子树rtag=THREADrchild域指向其“后继”18-Nov-2253lchildltagdatartagrchild区分子树和线索的方法为了区分孩子结点和前驱、后继结点，为结点如何对二叉树进行线索化在遍历过程中修改当前结点的左、右空指针域以保存该结点的“前驱”和“后继”信息。此过程称为对二叉树的线索化。遍历过程中,附设指针p指向当前访问的结点,指针pre指向它的前驱。18-Nov-2254如何对二叉树进行线索化在遍历过程中修改当前结点的左、右空指针中序线索化C语言描述voidInThreading(structBiTNode*p,structBiTNode**pre){ if(p) { InThreading(p->lchild,pre); if(!p->lchild)p->ltag=THREAD; else p->ltag=LINK; if(!p->rchild)p->rtag=THREAD; else p->rtag=LINK; if(!p->lchild)p->lchild=*pre; if(!(*pre)->rchild)(*pre)->rchild=p; (*pre)=p; InThreading(p->rchild,pre); }}18-Nov-2255中序线索化C语言描述voidInThreading(str先序线索化C语言描述voidPreThreading(structBiTNode*p,structBiTNode**pre){ if(p) { if(!p->lchild)p->ltag=THREAD; else p->ltag=LINK; if(!p->rchild)p->rtag=THREAD; else p->rtag=LINK;

if(!p->lchild)p->lchild=*pre;if(!(*pre)->rchild)(*pre)->rchild=p; (*pre)=p;InThreading(p->lchild,pre); InThreading(p->rchild,pre); }}18-Nov-2256先序线索化C语言描述voidPreThreading(st后序线索化C语言描述voidPostThreading(structBiTNode*p,structBiTNode**pre){ if(p){ InThreading(p->lchild,pre); InThreading(p->rchild,pre);if(!p->lchild)p->ltag=THREAD; else p->ltag=LINK; if(!p->rchild)p->rtag=THREAD; else p->rtag=LINK;

if(!p->lchild)p->lchild=*pre;if(!(*pre)->rchild)(*pre)->rchild=p;(*pre)=p; }}18-Nov-2257后序线索化C语言描述voidPostThreading(s线索化初始问题问题：在树进行线索化之前，pre值为空左子树最左下的节点线索也为空办法人为建立一个头节点head将树T作为head的左子树head->lchild=T初始时pre=T18-Nov-2258线索化初始问题问题：09-Nov-2258线索化初始问题18-Nov-2259D^^B

C

^AH线索化初始问题09-Nov-2259D^^B线索二叉树的遍历在线索二叉树中添加了“前驱”和“后继”的信息简化了遍历的算法：不需要堆栈不需要递归只要先找到第一个结点,然后依次找结点的后继直到后继为空时为止。只要先找到最后一个结点,然后依次找结点的前驱直到前驱为空时为止。18-Nov-2260线索二叉树的遍历在线索二叉树中添加了“前驱”和“后继”的信息线索二叉树中序遍历示例中序遍历的第一个结点树上左子树最左下的节点（ltag==THREAD)当前结点的后继若rtag=THREAD,则rchild指向后继否则，对将右子树设为中序遍历的第一个结点18-Nov-2261线索二叉树中序遍历示例中序遍历的第一个结点09-Nov-2218-Nov-2262二叉树线索化及遍历C程序演示演示如何根据对二叉树进行线索化演示如何在线索二叉树上进行遍历程序example62.c09-Nov-2262二叉树线索化及遍历C程序演示演示如何根18-Nov-2263第七节树和森林树的特点与二叉树不同的是，树的每个节点可能会有多个分支，因此树的表示方法与二叉树的表示方法略有不同。树的表示方法主要有以下三种：双亲表示法孩子表示法孩子兄弟表示法

09-Nov-2263第七节树和森林树的特点18-Nov-2264树的应用示例–BBS09-Nov-2264树的应用示例–BBS18-Nov-2265双亲表示法利用树中所有节点只有一个双亲的特点，用一组连续的存储单元来表示树中的每个节点，在这些存储单元中需要有一个数据域来表示该节点的双亲。#defineMAX_TREE_SIZE100 typedefstructPTNode{ TElemTypedata; intparent; }PTNode; typedefstruct{ PTNodenodes[MAX_TREE_SIZE]; intn; }PTree;09-Nov-2265双亲表示法利用树中所有节点只有一个双亲18-Nov-2266树的双亲表示法示例数组下标09-Nov-2266树的双亲表示法示例数组下标18-Nov-2267双亲表示法的特点由孩子找双亲比较方便，但是由双亲找孩子需要遍历整个数据表。09-Nov-2267双亲表示法的特点由孩子找双亲比较方便，18-Nov-2268孩子表示法在节点中给每个孩子分配一个指针域。由于树中各个节点的度不同，意味着不同的节点可能有不同数目的指针域，通常有两种解决办法：固定节点结构，即：根据树的度，为每个节点分配固定数目的指针域非固定的节点结构，即：在节点中需要增加一个域来指示该节点有多少个指针域09-Nov-2268孩子表示法在节点中给每个孩子分配一个指18-Nov-2269固定节点结构固定节点结构假定d为树的度，于是每个节点有d个指针域。特点：实现容易，但容易浪费空间，因为节点必须按照树的度来设计。datachild1child2

…childd09-Nov-2269固定节点结构固定节点结构假定d为树18-Nov-2270非固定节点结构根据各个节点度的不同，采用不同的结构节点中有一个专门的域用来表示该节点中指针的数目。特点：节约空间但实现比较复杂degreechild1child2

…childddata09-Nov-2270非固定节点结构根据各个节点度的不同，采18-Nov-2271链式孩子表示法把每个节点的孩子节点排列起来，形成一个线性表，且以单链表作为存储结构。RACDEHGBFK普通的树孩子表示法得到的链表09-Nov-2271链式孩子表示法把每个节点的孩子节点排列18-Nov-2272孩子表示法的特点n个节点的树需要有n个单链表来表示n个头指针构成一个线性表每个节点在表中出现两次（根节点除外）采用孩子表示方法，寻找某个节点的孩子方便了，但要寻找某个节点的双亲同样需要搜寻所有的孩子链表可以在孩子链表中添加一个表示双亲位置的区域。这就得到孩子双亲表示法09-Nov-2272孩子表示法的特点n个节点的树需18-Nov-2273孩子兄弟表示法又称为二叉树表示法，或二叉链表表示法。每个节点有两个指针：一个指向该节点的第一个孩子节点，第二个指针指向该节点的下一个兄弟。C语言描述的数据结构如下：

typedefstructCSNode{ ElemTypedata; structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;09-Nov-2273孩子兄弟表示法又称为二叉树表示法，或二18-Nov-2274孩子兄弟表示法示例RACDEHGBFK普通的树孩子兄弟法得到的二叉树RADEBCFGHK09-Nov-2274孩子兄弟表示法示例RACDEHGBFK18-Nov-2275孩子兄弟表示法的特点利用这种表示方法可以将普通的树变换为二叉树。注意：用二叉树表示法来表示树将得到一个右子树为空的二叉树。09-Nov-2275孩子兄弟表示法的特点利用这种表示方法可18-Nov-2276

二、森林与二叉树的转换二叉树B由三部分构成树根root(B)左子树LB右子树RB普通的森林由三部分构成第一个颗树的根节点第一颗树根节点的子树森林除第一颗树之外的其它树构成的森林09-Nov-2276二、森林与二叉树的转换二叉树B由三18-Nov-2277换一个角度来看树的概念ABCDEFGABCDEFG根节点子树森林09-Nov-2277换一个角度来看树的概念ABCDEFGA18-Nov-2278换一个角度看森林ABCDEFGT1HIT2JKLMNT3根节点子树森林其它树构成的森林09-Nov-2278换一个角度看森林ABCDEFGT1HI18-Nov-2279森林转化成二叉树的规则假定F={T1,T2,…,Tn}是森林，

B=(root,LB,RB)是二叉树若F为空，即n=0，则对应的二叉树B为空二叉树。若F不空，则：对应二叉树B的根root(B)是F中第一棵树T1的根root(T1)；其左子树为LB由T11,T12,…,T1m构成，其中，T11,T12,…,T1m是root(T1)的子树；其右子树为RB由T2,T3,…,Tn构成，其中，T2,T3,…,Tn是除T1外其它树构成的森林。09-Nov-2279森林转化成二叉树的规则假定F={T118-Nov-2280森林转换为二叉树递归概念示意图ABCDEFGT1HIT2JKLMNT3根节点子树森林其它树构成的森林A二叉树左子树右子树09-Nov-2280森林转换为二叉树递归概念示意图ABCD18-Nov-2281森林转换为二叉树示例BCDFEHIKJT1T2T3BAABCDFEHIKJ09-Nov-2281森林转换为二叉树示例BCDFEHIKJ18-Nov-2282森林转换为二叉树的非递归方法首先将森林的每棵树用二叉树表示法转换为二叉树然后将森林中的第二棵树看成是第一棵树的兄弟，即将第二颗树作为右子树添加到第一颗树上去以此类，直到将所有的树转换为一颗二叉树09-Nov-2282森林转换为二叉树的非递归方法首先将森18-Nov-2283森林转换为二叉树的非递归方法示例09-Nov-2283森林转换为二叉树的非递归方法示例18-Nov-2284二叉树转换为森林的规则如果B为空，则对应的森林F也为空。如果B非空，则：F中第一棵树T1的根为root(B)；root(B)的左子树LB

转换为T1的子树森林{T11,T12,…,T1m}root(B)的右子树RB

转换成林F中除了T1

之外其余树组成的森林{T2,T3,…,Tn}09-Nov-2284二叉树转换为森林的规则如果B为空，则对18-Nov-2285二叉树转换森林为示例FEHIKJT1T2T3BABCDBCDAFEHIKJ09-Nov-2285二叉树转换森林为示例FEHIKJT1T18-Nov-2286树和森林的遍历与二叉树的遍历不相同的是，由于树可能有多个子树，因此树的遍历只有先根遍历和后根遍历两种。先根遍历就是先访问根节点，然后依次先根访问树的各个子树。后根遍历就是先依次后根遍历树的各个子树，最后访问树的根节点。09-Nov-2286树和森林的遍历与二叉树的遍历不相同的18-Nov-2287树的遍历示例先根遍历：后根遍历：ABCDEBDCEA09-Nov-2287树的遍历示例先根遍历：ABCDEBDC18-Nov-2288森林的遍历根据先遍历森林中第一颗树的根结点还是先遍历第一颗树根节点的子树森林，可以将森林的遍历分为两种：先序遍历森林中序遍历森林

先序遍历森林规则若森林F为空,返回；否则 访问F的第一棵树的根节点；先序遍历第一棵树的子树森林；先序遍历其它树组成的森林。中序遍历森林规则若森林F为空,返回；否则 中序遍历第一棵树的子树森林；访问F的第一棵树的根节点；中序遍历其它树组成的森林。09-Nov-2288森林的遍历根据先遍历森林中第一颗树的根18-Nov-2289先序遍历森林的示例AFEHIKJT1T2T3ABCD先序森林遍历结果：BCDFEHIKJ09-Nov-2289先序遍历森林的示例AFEHIKJT1T18-Nov-2290中序遍历森林的示例BFEHIKJT1T2T3ABCD中序森林遍历结果：CDAEFKIJH09-Nov-2290中序遍历森林的示例BFEHIKJT1T18-Nov-2291关于森林遍历的几点说明将森林转换为二叉树后，森林的先序和中序遍历就可以通过对二叉树的先序和中序遍历来实现。09-Nov-2291关于森林遍历的几点说明将森林转换为二叉18-Nov-2292第八节huffman树及其应用基本术语：路径：从树的一个节点到另一个节点之间的所有分支构成路径路径长度(PathLength)：连接两节点的路径上的分支数目。树的路径长度:

树根节点到各节点的路径长度之和节点的带权路径长度：路径长度乘以节点的权值树的带权路径长度：树的所有叶节点的权值与该节点到根的路径长度的乘积之和（带权路径长度和）。WPL=∑wi×li特别注意：树的带权路径长度只计算叶节点的带权路径长度和，并不计算非终端节点09-Nov-2292第八节huffman树及其应用基本术18-Nov-2293树的路径长度示例0，1，1，2，2，2，2，3PL=130，1，1，2，2，2，3，3PL=1409-Nov-2293树的路径长度示例0，1，1，2，2，218-Nov-2294树的带权路径长度示例(a)WPL=2×2+4×2+5×2+7×2=36(b)WPL=2×1+4×2+5×3+7×3=46(c)WPL=7×1+5×2+2×3+4×3=3509-Nov-2294树的带权路径长度示例(a)WPL=2×18-Nov-2295Huffman树带权路径长度最小的二叉树称为最优二叉树，也叫huffman树。huffman树的特点：在叶子节点数目和权值相同的情况下，Huffman树的带权路径最小权值大的节点离根最近。Huffman树在信号与信息处理领域有非常广泛的应用数据压缩视频、语音编码09-Nov-2295Huffman树带权路径长度最小的二叉18-Nov-2296Huffman树的应用示例例：统计学生的成绩，检验学生的学习效果，同时评判考试题目是否合理。若设计程序对各个分数段的学生成绩进行统计，则最直观的设计思路如下图所示09-Nov-2296Huffman树的应用示例例：统计学生18-Nov-2297Huffman应用示例通常情况下学生的考试成绩是一种正态分布，也就是大部分学生处于中等水平，特别优秀或特别差的学生很少假定一般情况下学生成绩分布如下表所示如果有10000个学生，根据比例，各个分数段的学生数目应该为：500，1500，4000，3000，1000。如果采用前面的算法，那么在统计过程中需要比较的次数为：采用该比较方法，统计10000个学生需要比较的次数为：500×1+1500×2+4000×3+3000×4+1000×4=31500次分数0~5960~6970~7980~8990~100比例0.050.150.400.300.1009-Nov-2297Huffman应用示例通常情况下学生的18-Nov-2298改进的统计算法如果我们采用下面的统计方法则需要比较的次数为：500×3+1500×3+4000×2+3000×2+1000×2=22000次09-Nov-2298改进的统计算法如果我们采用下面的统计方18-Nov-2299算法效率提高的原因我们有处理对象的先念知识，即：我们知道学生成绩的分布情况。这一般需要根据经验或统计分析得到。由于大部分学生的成绩在70到90分之间，算法改进后，大部分学生的成绩只需要比较2次就可以做出判断只有成绩特别差或特别好的学生才需要多次比较。但由于这些学生的人数很少，因此不会占用较多的计算时间如果我们把不同档次的学生数目看成是叶子节点的权值将每个学生成绩需要比较的次数看成是从根节点到叶子节点的路径那么要使比较的次数最小就是要使二叉树的带权路径最小，即：根据权值生成huffman树09-Nov-2299算法效率提高的原因我们有处理对象的先念18-Nov-22100如何构造一棵最优二叉树(1)由给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的森林F={T1,T2,…,Tn}，其中每一棵二叉树Ti中只有一个带有权值wi的根节点，其左、右子树均为空。(2)重复以下步骤,直到F中仅剩下一棵树为止：

①在F中选取两棵根节点权值最小的二叉树作为左右子树构造一棵新的二叉树，置新的二叉树的根节点的权值为其左、右子树上根节点的权值之和②在F中删去这两棵二叉树③把新的二叉树加入F中09-Nov-22100如何构造一棵最优二叉树(1)由给定18-Nov-22101Huffman树构造示例09-Nov-22101Huffman树构造示例18-Nov-22102Huffman编码主要用途是实现数据压缩。通信系统中传送的是一个一个的符号，每个通信系统传送的符号个数可能不同，每个符号出现的概率和编码长度也可能不同。如果我们用Wi

表示这种符号出现的概率，路径长度Li表示该符号编码后的比特数，那么

WPL=∑Wi×Li表示每传送一个符号需要的平均比特数。显然我们总是希望平均比特数越小越好。在什么情况下比特数能够达到最小？根据各个符号的概率建立huffman树。09-Nov-22102Huffman编码主要用途是实现数据18-Nov-22103Huffman编码需要解决的问题例：有8个符号的通信系统，假设8个符号出现的概率分别为：A(0.4)，B(0.3)，C(0.1)，D(0.08)E(0.05)，F(0.04)，G(0.02)，H(0.01)如果用定长编码，显然每个码字需要3比特，比如：A→000B→001C→010D→011E→100F→101G→110H→111如果采用Huffman编码，显然出现概率大的符号编码后的码长比较小，而概率小的符号编码后的码长比较长由于各个符号的码长不一样，那么在接收端解码的时候会出现问题，比如：假定有三个符号A，B，C，他们编码的结果是：0，01，001，那么当接收端接收到0001时，接收端不知道发送端发送的是A，A，B还是A，C。这是因为这三个符号的编码中A是B和C的前缀，B又是C的前缀。解决的办法：在编码过程中任何一个符号的码字均不能是另一个符号码字的前缀。09-Nov-22103Huffman编码需要解决的问题例：18-Nov-22104前缀码（唯一可解码）如果各个符号编码后的码长不相同，那么每个码字的编码不能是其它码字的前缀，接收端才能进行正确的解码，这种编码称为前缀码。为了得到前缀编码，可以使用最优二叉树，并采用如下规则：约定左分支表示符号“0”，右分支表示符号“1”，从根节点到叶子节点的路径上的分支字符组成的字符串作为该叶子节点字符的编码这个过程称为Huffman编码

09-Nov-22104前缀码（唯一可解码）如果各个符号编码18-Nov-22105前缀码实现示例09-Nov-22105前缀码实现示例18-Nov-22106Huffman编码示例对于上面的例子，根据各个符号出现概率的不同构造一颗Huffman树假定我们约定左分支表示符号‘0’，右分支表示符号‘1’，则可以得到各个符号的编码如下：A→0B→10C→1111D→1110E→1100F→11011G→110101H→11010009-Nov-22106Huffman编码示例对于上面的例子18-Nov-22107计算编码效率采用定长编码每个符号要用3比特来表示采用Huffman编码后，每个符号的平均长度为：可以计算出它们的平均码长：

=0.40×1+0.30×2+0.10×4+0.08×4+0.05×4+0.04×4+0.02×6+0.01×6=2.3即：平均每个符号只需要2.3个比特。那么，编码效率提高了(3.0-2.3)/3×100%≈23%09-Nov-22107计算编码效率采用定长编码每个符号要用18-Nov-22108Huffman树的构造过程示例输入四个符号A,B,C,D，它们的频率为:1/12,2/12,4/12,5/1212451233477512010101110021014115012建立huffman树给每个分支赋值获得每个符号的编码09-Nov-22108Huffman树的构造过程示例输入四18-Nov-22109Huffman解码示例假定接收到的输入为:1101001011234751201010111C0D100A10B1译码后的输出:CDAB09-Nov-22109Huffman解码示例假定接收到的输18-Nov-22110Huffman编码存储C描述typedefstruct{ unsignedintweight; unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;WPLR09-Nov-22110Huffman编码存储C描述type18-Nov-22111Huffman编码算法(初始化）voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//求n个字符的huffman编码,w为它们的权值

if(n<=1)return; m=2*n-1;//节点总数目

HT=(HuffmanTree)malloc((m+1)* sizeof(HTNode));//0号未使用

for(p=HT+1,i=1;i<=n;i++,p++,w++) *p={*w,0,0,0}; for(;i<=m;i++,p++) *p={0,0,0,0};09-Nov-22111Huffman编码算法(初始化）vo18-Nov-22112Huffman编码算法(建树）for(i=n+1;i<=m;i++){Select(HT,i-1,s1,s2);//从前面i-1元素中选择parent==0且权值最小的两个值

HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}200040000000125500070003425004500601209-Nov-22112Huffman编码算法(建树）for18-Nov-22113Huffman编码算法(编码）HC=(HuffmanCode)malloc((n+1)sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]=‘\0’;for(i=1;i<=n;i++){ start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]=‘0’; else cd[--start]=‘1’; HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]; }//endoffor free(cd);}09-Nov-22113Huffman编码算法(编码）HC=18-Nov-22114无栈非递归遍历Huffman树HC=(HuffmanCode)malloc((n+1)sizeof(char*));p=m;cdlen=0;for(i=1;i<=m;i++)HT[i].weight=0;while(p){ if(HT[p].weight==0){//向左

HT[p].weight=1; if(HT[p].lchild!=0) {p=HT[p].lchild;cd[cdlen++]=‘0’;} elseif(HT[p].rchild==0){//右孩子为空

HC[p]=(char*)malloc( (cdlen+1)*sizeof(char)); cd[cdlen]=‘\0’;strcpy(HC[p],cd); }//右孩子为空

}//向左09-Nov-22114无栈非递归遍历Huffman树HC=18-Nov-22115无栈非递归遍历Huffman树（续） elseif(HT[p].weight==1){ HT[p].weight=2; if(HT[p].rchild!=0){ p=HT[p].rchild; cd[cdlen++]=‘1’;} }else{ HT[p].weight=0; p=HT[p].parent; --cdlen; }}09-Nov-22115无栈非递归遍历Huffman树（续）18-Nov-22116Huffman编码C程序演示演示如何根据预定的权值创建Huffman树演示如何利用所建立的Huffman树获取各个符号的编码序列程序example63.c09-Nov-22116Huffman编码C程序演示演示如何18-Nov-22117Huffman编码的缺陷–误码扩散假定接收到的输入为:110100101→100100101译码后的输出:CDAB→AAB12347512010101100A100A10B109-Nov-22117Huffman编码的缺陷–误码扩18-Nov-22118第六章树和二叉树树是一类重要的非线性数据结构，是以分支关系定义的层次结构典型例子：企业的管理机构计算机文件系统09-Nov-221第六章树和二叉树树是一类重要的非线性数18-Nov-22119

第一节树的定义树(Tree)的定义树是由n(n0)个节点组成的有限集合。如果n=0，称为空树；如果n>0，则:有且仅有一个特定的称之为根(root)的节点，它只有直接后继，但没有直接前驱；如果n>1，则：除根以外的其它节点可以划分为m(m>0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称为根的子树(subTree)。每棵子树的根节点有且仅有一个直接前驱，但可以有0个或多个直接后继。特点：非空的树至少有一个根节点树中各子树是互不相交的集合09-Nov-222第一节树的定义树(Tree)的定义18-Nov-22120树的示例子树根A只有根节点的树09-Nov-223树的示例子树根A只有根节点的树18-Nov-22121

树的基本术语节点(node)：树中的元素。包含一个数据元素及若干指向其子树的分支节点的度(degree)：节点拥有的指向其子树的分支数目分支(branch)节点：度不为0的节点叶(leaf)（终端）节点：度为0的节点树的度：树中所有节点度的最大值孩子(child)与双亲(parent)节点：节点的子树的根称为该节点的孩子，该节点称为孩子的双亲ABCDEFG09-Nov-224树的基本术语节点(node)：树中的18-Nov-22122树的基本术语（续）兄弟

(sibling)：同一个双亲的孩子之间互称兄弟。祖先(ancestor)：从根节点到某个节点所经分支上的所有节点。子孙（descendant)：以某个节点为根节点的子树中的所有节点均是该节点的子孙。堂兄弟：双亲在同一个层次上的节点互为堂兄弟。节点所处层次(level)：根为第一层，根的孩子为第二层，依此类推。树的深度(depth)（高度）：树中所有节点层次的最大值。ABCDEFG09-Nov-225树的基本术语（续）兄弟(siblin18-Nov-22123树的基本术语（续）有序树与无序树：树的各个子树从左至右的顺序不可以调换则称为有序树，否则为无序树。森林（Forest）：m(m≥0)棵互不相交的树的集合称为森林。对树中每个节点而言，其子树的集合就构成森林。09-Nov-226树的基本术语（续）有序树与无序树：树的各18-Nov-22124树的基本术语举例12344节点A的度：3节点B的度：2节点M的度：0叶子：K，L，F，G，M，I，J节点I的双亲：D节点L的双亲：E树的度：3树的深度：4节点B，C，D为兄弟节点K，L为兄弟节点E，G，H为堂兄弟节点A，D，H是M的祖先09-Nov-227树的基本术语举例12344节点A的度：318-Nov-22125树的抽象数据类型数据对象D：

D是具有相同特性的数据元素的集合。数据关系R：如果D为空集，则称为空树；如果D中只有一个元素，则R为空集;否则R={H}，H是满足以下条件的二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠Ø,则存在D-{root}上的一个划分D1,D2,…,Dmm>0，对任意j≠k(1≤j,k≤m)有Dj∩Dk=Ø，且对任意的i(1≤i≤m)，唯一存在数据元素xi(xi∈Di),，有<root,xi>∈H(3)对应于D-{root}的划分，H–{<root,x1>,<root,x2>,…,<root,xm>}有唯一的一个划分H1,H2,…,Hmm>0，对任意j≠k(1≤j,k≤m)有Hj∩Hk=Ø，且对任意的i(1≤i≤m)，Hi

是Di

上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。09-Nov-228树的抽象数据类型数据对象D：18-Nov-22126树的操作①初始化InitTree(&T);②销毁树DestroyTree(&T)③创建树CreateTree(&T)④清空树ClearTree(&T)⑤判断树是否为空TreeEmtpy(T)⑥求树的深度TreeDepth(T)⑦求树的根Root(T)⑧求树上某个节点的值Value(T,cur_e)⑨给树上某