第6-树和二叉树.pptx

6.1树的定义和基本术语树的定义和基本术语6.2二叉树二叉树6.3遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4树和森林树和森林6.6哈夫曼树与其应用哈夫曼树与其应用树树（tree）是是n(n0)个个结结点点的的有有限限集集。在在任任意意一一棵棵非非空空树树中中：（1）有有且且仅仅有有一一个个特特定定的的称称为为根根的的结结点点；（2）当当n1时时，其其余余结结点点可可分分为为m(m0)个个互互不不相相交交的的有有限限集集T1,T2,Tm，其其中中每每一一个个集集合合本本身身又又是是一一棵棵树，并且称为根的树，并且称为根的子树子树。A只有根结点的树只有根结点的树ABCDEFGHIJKLM有子树的树有子树的树根根子树子树数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集，则称为为空集，则称为空树空树。否则否则:(1)在在D中存在唯一的称为中存在唯一的称为根根的数据元素的数据元素root；(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个个互不相互不相交交的有限集的有限集T1,T2,Tm，存在，存在关系，关系，XiT1，其中每一棵子集本身又是一棵符合本定其中每一棵子集本身又是一棵符合本定义的树，称为根义的树，称为根root的的子树子树。数据关系数据关系R：ADT Tree基基 本本 术术 语语结点结点:结点的度结点的度:树的度树的度:叶子（终端）结点叶子（终端）结点:分支分支(非终端非终端)结点结点:数据元素数据元素+若干指向子树的分支若干指向子树的分支结点拥有的子树数结点拥有的子树数树中所有结点的度的最大值树中所有结点的度的最大值度为零的结点度为零的结点度不为零的结点度不为零的结点DHIJM子孙子孙:以某结点为根的子树中的任一结点。以某结点为根的子树中的任一结点。ABCDEFGHIJMKL孩子孩子:结点的子树的根。结点的子树的根。双亲双亲:该结点称为孩子的双亲。该结点称为孩子的双亲。兄弟兄弟:同一个双亲的孩子之间互称兄弟。同一个双亲的孩子之间互称兄弟。祖先祖先:从根到该结点所经分支上的所有结点从根到该结点所经分支上的所有结点有序树：有序树：子树之间存在确定的次序关系，不能子树之间存在确定的次序关系，不能互换互换无序树：无序树：子树之间不存在确定的次序关系子树之间不存在确定的次序关系树的深度：树的深度：树中结点的最大层次树中结点的最大层次堂兄弟堂兄弟:其双亲在同一层的结点其双亲在同一层的结点结点的层次结点的层次:假设根结点的层次为假设根结点的层次为1，若某结，若某结点在第点在第l 层，则其子树的根结点层次为层，则其子树的根结点层次为l+1DHIJMA AB BC CD DE EF FG GH HI IJ JK KL LM M结点结点A的度：的度：结点结点B的度：的度：结点结点M的度：的度：叶子：叶子：结点结点A的孩子：的孩子：结点结点B的孩子：的孩子：结点结点I的双亲：的双亲：结点结点L的双亲：的双亲：树的度：树的度：结点结点A的层次：的层次：结点结点M的层次：的层次：树的深度：树的深度：320B，C，DE，FK，L，F，G，M，I，J3DE兄弟兄弟兄弟兄弟结点结点B，C，D为为结点结点K，L为为144堂兄弟堂兄弟结点结点F，G为为任何一棵非空树是一个二元组任何一棵非空树是一个二元组Tree=（root，F）其中：其中：root被称为根结点被称为根结点F被称为被称为m棵子树的森林棵子树的森林森林：森林：是是m（m0）棵互）棵互不相交的树的集合不相交的树的集合ArootBCDEFGHIJMKLF树的其他表示形式：嵌套集树的其他表示形式：嵌套集合表示法、广义表表示、凹入表合表示法、广义表表示、凹入表示法。示法。DABCDEFGHIJMKL(A(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根例如例如:树的广义表形式树的广义表形式 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()/遍历遍历基本操作基本操作P:P:InitTree(&T)/初始化置空树初始化置空树插入类：插入类：CreateTree(&T,definition)/按定义构造树按定义构造树Assign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将以将以c为根的树插为根的树插入为结点入为结点p的第的第i棵子树棵子树 ClearTree(&T)/将树清空将树清空删除类：删除类：DestroyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素(无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)对比对比二叉树二叉树:或为空树，或是由一个或为空树，或是由一个根结根结点点加上两棵分别称为加上两棵分别称为左子树左子树和和右子树右子树的、的、互不相交互不相交的二叉树组成。的二叉树组成。ABCDEFGHK根结点根结点左子树左子树右子树右子树特点：特点：（1 1）每个结点至多有二棵子树）每个结点至多有二棵子树(即不存在度大于即不存在度大于2 2的结点的结点)；（2 2）二叉树的子树有左、右之）二叉树的子树有左、右之分，且其次序不能任意颠倒。分，且其次序不能任意颠倒。二叉树的五种基本形态：二叉树的五种基本形态：空树空树只含根结点只含根结点LRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树二叉树的主要基本操作二叉树的主要基本操作：InitBiTree(&T);DestroyBiTree(&T);CreateBiTree(&T,definition);ClearBiTree(&T);BiTreeEmpty(T);BiTreeDepth(T);Assign(T,&e,value);Root(T);InsertChild(T,p,LR,c);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);DeleteChild(T,p,LR);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();二叉树的性质二叉树的性质性质性质1：在二叉树的第在二叉树的第i层上至多有层上至多有2i-1 个结点。个结点。(i1)证明：用归纳法证明之证明：用归纳法证明之i=1时，只有一个根结点，时，只有一个根结点，是对的是对的证明对任意的证明对任意的i命题成立，即第命题成立，即第i层上层上至多有至多有个结点个结点.假设假设第第i-1层至多有层至多有个结点个结点,二叉树二叉树每个结点的度至多为每个结点的度至多为2,所以所以第第i层上最大结点数层上最大结点数是第是第i-1层的层的2倍，即倍，即故命题得证故命题得证性质性质2：深度为深度为k 的二叉树上至多含的二叉树上至多含2k-1 个结个结点（点（k1）。）。证明：证明：基于上一条性质，深度为基于上一条性质，深度为k 的二叉树上的二叉树上的结点数至多为的结点数至多为20+21+2k-1=2k-1。a1(1-qn)/(1-q)性质性质3：对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n0 个叶子个叶子结点、结点、n2 个度为个度为 2的结点，则必存在关的结点，则必存在关系式：系式：n0=n2+1。证明：证明：设设 二叉树上结点总数二叉树上结点总数 n=nn=n0 0+n+n1 1+n+n2 2又又 二叉树上分支总数二叉树上分支总数 b=nb=n1 1+2n+2n2 2 而而 n=b+1=nn=b+1=n1 1+2n+2n2 2+1+1由此，由此，n n0 0=n=n2 2+1 +1。两类特殊的二叉树：两类特殊的二叉树：指的是深度为指的是深度为k且含有且含有2k-1个个结点的二叉树。结点的二叉树。123456789 10 11 12 13 14 15满二叉树：满二叉树：树中所含的树中所含的 n个结点和满二叉树中个结点和满二叉树中编号为编号为1 至至n 的结点的结点一一对应。一一对应。abcdefghij完全二叉树：完全二叉树：完全二叉树特点：完全二叉树特点：（1 1）叶子结点只可能在层次最大的两）叶子结点只可能在层次最大的两层上出现层上出现;（2 2）对任一结点，若其右分支下子孙）对任一结点，若其右分支下子孙的最大层次为的最大层次为l，则其左分支下子孙的最，则其左分支下子孙的最大层次必为大层次必为l或或l+1+1。1231145891213671014151231145891267101234567123456性质性质4：具有具有n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。证明：证明：设完全二叉树的深度为设完全二叉树的深度为k 则根据第二条性质得则根据第二条性质得2k-1(第第k层第一个结点的编号）层第一个结点的编号）n 2k（第（第k1层第一个结点的编号）层第一个结点的编号）即即 k-1 log2 n 1，编号为，编号为 i/2 的结点为其的结点为其双亲结点双亲结点；(2)若若2in，则该结点无左孩子，则该结点无左孩子，否则，编号为否则，编号为2i 的结点为其的结点为其左孩子结点左孩子结点；(3)若若2i+1n，则该结点无右孩子结点，则该结点无右孩子结点，否则，编号为否则，编号为2i+1 的结点为其的结点为其右孩子结点右孩子结点。归纳法证明：归纳法证明：1）i=1时，指的根结点，有时，指的根结点，有2=2*1是其左是其左孩子，孩子，3=2*1+1是根的右孩子；是根的右孩子；2）如果对于第）如果对于第k层的结点层的结点i，满足有左孩，满足有左孩子为子为2i，右孩子，右孩子2i+1；123 i/2 2i+3ii+12i2i+1 2i+2对于对于i+1i+1这个结点，这个结点，i+1i+1的的左孩子为左孩子为2i+2=2(i+1),2i+2=2(i+1),右孩右孩子子2i+3=2(i+1)+1,2i+3=2(i+1)+1,成立成立114589126710123第k层i+1=2k2k-12k+1+12k+1第k+1层第第k层上最后一个结点的编号是层上最后一个结点的编号是2k-1,它的右孩它的右孩子是第子是第k+1层上最后一个结点层上最后一个结点,编号是编号是2k+1-1,右右孩子编号是它的双亲结点编号的孩子编号是它的双亲结点编号的(2k-1)*2+1,左左孩子的编号是孩子的编号是(2k-1)*2所以，编号为所以，编号为i的结点的左孩子结点编号是的结点的左孩子结点编号是2i，右孩子结点编号是，右孩子结点编号是2i+1,双亲结点编号双亲结点编号 i/2 i=2k-12k+1-1=(2k-1)*2+1(2k-1)*2二叉树的存储结构二叉树的存储结构二、链式存储结构二、链式存储结构一、顺序存储结构一、顺序存储结构存储方式：存储方式：用一组地址连续的存储单元依次用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结自上而下、自左至右存储完全二叉树上的结点元素，点元素，即即将完全二叉树上编号为将完全二叉树上编号为i的结点元的结点元素存储在一维数组中下标为素存储在一维数组中下标为i-1的分量中的分量中。一、一、二叉树的顺序存储结构二叉树的顺序存储结构对于一般二叉树，应将其每个结点与完全二对于一般二叉树，应将其每个结点与完全二叉树上结点相对照，存储在一维数组分量中，叉树上结点相对照，存储在一维数组分量中，“0”表示不存在此结点表示不存在此结点例如例如:125371234567891011121314012345678910111213140132646891011121314例如例如:ABCDEFABDCEF01234567891011121314013260表示不存在此结点表示不存在此结点00000000结点间关系蕴含在其存储位置中；结点间关系蕴含在其存储位置中；浪费空间，适于存完全二叉树（在最坏浪费空间，适于存完全二叉树（在最坏情况下，深度为情况下，深度为k且只有且只有的单的单支树需要长度为支树需要长度为的一维数组）。的一维数组）。顺序存储结构特点：顺序存储结构特点：k个结点个结点2k-1AE二、二叉树的链式存储结构二、二叉树的链式存储结构（1 1）二叉链表）二叉链表（2）三叉链表三叉链表ADEBCF rootlchild data rchild结点结构结点结构:1.1.二叉链表二叉链表FABCDE在在n n个结点的二叉链表中，个结点的二叉链表中，有有n+1n+1个空指针域个空指针域typedefstruct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:ADEBCF root 2三叉链表三叉链表parent lchilddatarchild结点结构结点结构:ABCDEFtypedefstructTriTNode/结点结构结点结构TElemTypedata;structTriTNode*lchild,*rchild;/左右孩子指针左右孩子指针structTriTNode*parent;/双亲指针双亲指针TriTNode,*TriTree;parentlchilddatarchild结点结构结点结构:C语言的类型描述如下语言的类型描述如下:在二叉树的一些应用中，要求在树中在二叉树的一些应用中，要求在树中查找具有某种特征的结点，或者对树中全查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。提出部结点逐一进行某种处理。提出遍历遍历二叉二叉树的问题，树的问题，即按某条搜索路径巡访树中的即按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，每个结点，使得每个结点均被访问一次，而且仅被访问一次而且仅被访问一次。遍历二叉树遍历二叉树“访问访问”的含义可以很广，可以是对结的含义可以很广，可以是对结点作各种处理点作各种处理,如输出结点的信息等。如输出结点的信息等。“遍历遍历”是任何类型均有的操作，是任何类型均有的操作，对对线性结构线性结构而言，只有而言，只有一条搜索路径一条搜索路径(因为每个结点均只有一个后继因为每个结点均只有一个后继)，故，故不需要另加讨论。而二叉树是不需要另加讨论。而二叉树是非线性非线性结构，每个结点可能有两棵子树，则结构，每个结点可能有两棵子树，则存在如何遍历即按什么样的搜索路径存在如何遍历即按什么样的搜索路径遍历遍历的问题。的问题。对对“二二叉叉树树”而而言言，可可以以有有三条搜索路径：三条搜索路径：1先上后下先上后下的按层次遍历；的按层次遍历；2先左先左（子树）（子树）后右后右（子树）的遍历；（子树）的遍历；3先右先右（子树）（子树）后左后左（子树）的遍历。（子树）的遍历。若限定先左后右若限定先左后右,则只有则只有3种情况种情况先左后右的遍历算法先左后右的遍历算法先先（根）序遍历（根）序遍历中中（根）序遍历（根）序遍历后后（根）序遍历（根）序遍历根根LRABCDEFGHK类似于类似于送报纸送报纸若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）访问根结点；）访问根结点；（2）先序先序遍历左子树；遍历左子树；（3）先序先序遍历右子树。遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）中序中序遍历左子树；遍历左子树；（2）访问根结点；）访问根结点；（3）中序中序遍历右子树。遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）后序后序遍历左子树；遍历左子树；（2）后序后序遍历右子树；遍历右子树；（3）访问根结点。）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：ADBCDLRADLRDLRBDCDLR先序遍历序列：先序遍历序列：ABDC先序遍历:根根 左左 右右ADBCLDRBLDRLDRADCLDR中序遍历序列：中序遍历序列：BDAC中序遍历:左左根根 右右ADBCLRDLRDLRDADCLRD后序遍历序列：后序遍历序列：DBCA后序遍历:B左左 右右 根根-+/a*b-efcd先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：-+a*b-cd/ef-+a*b-c d/e f-+a*b-cd/ef层次遍历：层次遍历：-+a a*b b-c cd d/e ef f先序遍历二叉树的递归算法描述先序遍历二叉树的递归算法描述StatusPreorder(BiTreeT,Status(*visit)(TElemTypee)/先序遍历二叉树先序遍历二叉树if(T)if(visit(T-data)/访问根结点访问根结点if(Preorder(T-lchild,visit)/先序遍历左子树先序遍历左子树if(Preorder(T-rchild,visit)returnOK;/先序遍历右先序遍历右子树子树returnERROR;/访问没有成功访问没有成功 elsereturnOK;/T为空树为空树 中序遍历二叉树的递归算法描述中序遍历二叉树的递归算法描述StatusInOrderTraverse(BiTreeT,Status(*visit)(TElemTypee)/中序遍历二叉树中序遍历二叉树if(T)if(InOrderTraverse(T-lchild,visit)/中序遍历左子树中序遍历左子树if(visit(T-data)/访问根结点访问根结点if(InOrderTraverse(T-rchild,visit)returnOK;/中序中序遍历右子树遍历右子树returnERROR;/访问没有成功访问没有成功 elsereturnOK;/T为空树为空树 见演示见演示后序遍历二叉树的递归算法描述后序遍历二叉树的递归算法描述StatusPostorder(BiTreeT,Status(*visit)(TElemTypee)/后序遍历二叉树后序遍历二叉树if(T)if(Postorder(T-lchild,visit)/后序遍历左子树后序遍历左子树if(Postorder(T-rchild,visit)/后序遍历右子树后序遍历右子树if(visit(T-data)returnOK；/访问根结点访问根结点returnERROR;/访问没有成功访问没有成功 elsereturnOK;/T为空树为空树 见演示见演示中序遍历算法的中序遍历算法的非递归非递归描述描述(算法算法1)1)StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)InitStack(S);Push(S,T);/根指针进栈根指针进栈While(!StackEmpty(S)向左走到尽头（直到空指针），经过的结点都入栈；向左走到尽头（直到空指针），经过的结点都入栈；空指针出栈；空指针出栈；if(!StackEmpty(S)出栈，访问该结点，即向右退一步；出栈，访问该结点，即向右退一步；结点右孩子入栈结点右孩子入栈；/if/whileReturnOK;/InOrderTraverse-b*caWhile(GetTop(S,p)&p)Push(S,p-lchild);Pop(S,p);Pop(S,p);if(!Visit(p-data)returnERROR;Push(S,p-rchild);-b*ca-*anullnullbnullnullcnullnull中序遍历序列:a*b-cWhile(!StackEmpty(S)While(GetTop(S,p)&p)Push(S,p-lchild);/向左走到尽头向左走到尽头Pop(S,p);/空指针退栈空指针退栈if(!StackEmpty(S)/访问结点访问结点,向右一步向右一步Pop(S,p);if(!Visit(p-data)returnERROR;Push(S,p-rchild);/ifstatusInorderTraverse(BiTreeT,status(*Visit)(TelemTypee)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;/else/whileReturnOK;/InorderTraverse中序遍历算法的非递归描述中序遍历算法的非递归描述(算法算法2)2)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;/else/while-b*ca-*abc中序遍历序列:a*b-c算法思想为：算法思想为：从从二二叉叉树树根根结结点点开开始始，沿沿左左子子树树一一直直走走到到末末端端(左左孩孩子子为为空空)为为止止，在在走走的的过过程程中中，访访问问所所遇遇结结点点，并并依依次次把把所所遇遇结结点点进进栈栈，当当左左子子树树为为空空时时，从从栈栈顶顶退退出出某某结结点点，并并将将指指针针指指向向该该结结点点的的右右孩孩子子。如如此此重重复复，直直到到栈栈为为空空或或指指针针为为空空止止。与与中中序序的的区区别别是是入入栈栈前前访访问问结结点点还还是是出栈时访问结点。出栈时访问结点。先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法3.3.后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法利利用用栈栈来来实实现现二二叉叉树树的的后后序序遍遍历历要要比比前前序序和和中中序序遍遍历历复复杂杂得得多多，在在后后序序遍遍历历中中，当当搜搜索索指指针针指指向向某某一一个个结结点点时时，不不能能马马上上进进行行访访问问，而而先先要要遍遍历历左左子子树树，所所以以此此结结点点应应先先进进栈栈保保存存，当当遍遍历历完完它它的的左左子子树树后后，再再次次回回到到该该结结点点，还还不不能能访访问问它它，还还需需先先遍遍历历其其右右子子树树,所所以以该该结结点点还还必必须须再再次次进进栈栈，只只有有等等它它的的右右子子树树遍遍历历完完后后，再再次次退退栈栈时时，才才能能访访问问该该结结点点。为为了了区区分分同同一一结结点点的的两两次次进进栈栈，引引入入一一个个栈栈次次数数的的标标志志，一一个个元元素素第第一一次次进进栈栈标标志志为为0 0，第第二二次次进进标标志志为为1 1，并并将将标标志志存存入入另另一一个个栈栈中中，当当从从标标志志栈栈中中退退出出的的元元素为素为1 1时，访问结点。时，访问结点。“遍历遍历”是二叉树各种操作的基础，是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操可以在遍历过程中对结点进行各种操作，例如在遍历过程中生成结点，建作，例如在遍历过程中生成结点，建立二叉树的存储结构立二叉树的存储结构例如，按先序次序读入字符例如，按先序次序读入字符ABC#DE#G#F#，其中，其中表示空格，表示空格，可建立相应的二叉链表。可建立相应的二叉链表。StatusCreateBiTree(BiTree&T)/按先序次序输入二叉树中结点的值（一个字符按先序次序输入二叉树中结点的值（一个字符)，空，空/格字符表示空树，构造二叉链表表示的二叉树格字符表示空树，构造二叉链表表示的二叉树T。scanf(&ch);if(ch=)T=NULL;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;/生成根结点生成根结点CreateBiTree(T-lchild);/构造左子树构造左子树CreateBiTree(T-rchild);/构造右子树构造右子树returnOK;/CreateBiTree按先序序列建立二叉链表按先序序列建立二叉链表例：例：ABC#DE#G#F#例：例：ABC#DE#G#F#ABCDEGF#只知道先序字符只知道先序字符ABCDEGFABCDEGF能否建立二叉能否建立二叉树？树？ABCDEGFABCDEGFABCDEGF根据中序遍历和先序遍历（或后序根据中序遍历和先序遍历（或后序遍历才能确定一棵二叉树）遍历才能确定一棵二叉树）先序：先序：ABCDEFGHKABCDEFGHK中序：中序：BDCAHGKFEBDCAHGKFE后序：后序：DCBHKGFEADCBHKGFEA遍历算法的应用遍历算法的应用1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数(先序遍历先序遍历)2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)3、复制二叉树、复制二叉树(后序遍历后序遍历)4 4、建立二叉树的存储结构、建立二叉树的存储结构线索二叉树线索二叉树 何谓线索二叉树？何谓线索二叉树？线索链表的遍历算法线索链表的遍历算法 如何建立线索链表？如何建立线索链表？遍历二叉树是以一定规则将二遍历二叉树是以一定规则将二叉树中结点排列成一个叉树中结点排列成一个线性序列线性序列，得到二叉树中结点的先序序列或中得到二叉树中结点的先序序列或中序序列或后序序列。序序列或后序序列。实质是对一个实质是对一个非线性结构进行非线性结构进行线性化操作线性化操作，使每个结点在这些线，使每个结点在这些线性序列中有且仅有一个直接前驱和性序列中有且仅有一个直接前驱和直接后继。直接后继。何谓线索二叉树？何谓线索二叉树？当以二叉链表作为存储结构时当以二叉链表作为存储结构时,只能只能找到结点的左右孩子信息找到结点的左右孩子信息,不能直接得到不能直接得到结点在任一序列中的结点在任一序列中的前驱和后继信息前驱和后继信息,这这种信息只有在种信息只有在遍历的动态过程中才能得遍历的动态过程中才能得到到。n n个结点的二叉链表存在个结点的二叉链表存在n+1n+1个空链域个空链域,因此可以利用空链因此可以利用空链域存放结点的前驱和后继信息。域存放结点的前驱和后继信息。为了保存这种在遍历过程中得到的信息为了保存这种在遍历过程中得到的信息:并作如下规定：并作如下规定：若结点有左子树，若结点有左子树，则其则其lchild域指示其左孩子，否则令域指示其左孩子，否则令lchild域指示其前驱域指示其前驱若结点有右子树，若结点有右子树，则其则其rchild域指示其右孩子，否则令域指示其右孩子，否则令rchild域指示其后继域指示其后继以这种结点结构构成的二叉链表作为二以这种结点结构构成的二叉链表作为二叉树的存储结构，叫作叉树的存储结构，叫作“线索链表线索链表”。为了避免混淆，需改变结点结构，为了避免混淆，需改变结点结构，增加两个标志域增加两个标志域lchildLTagdataRTagrchild0lchild域指示结点的左孩子域指示结点的左孩子1lchild域指示结点的前驱域指示结点的前驱0rchild域指示结点的右孩子域指示结点的右孩子1rchild域指示结点的后继域指示结点的后继LTag=RTag=遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序先序序列:A B C D E F G H K中序中序序列:B D C A H G K F E后序后序序列:D C B H K G F E A指向结点前驱和后继的指针，指向结点前驱和后继的指针，称作称作“线索线索”。加上线索的二叉树，加上线索的二叉树，称作称作“线索二叉树线索二叉树”ABCDEFGHKDCBE对二叉树以某种次序遍历使其变对二叉树以某种次序遍历使其变为线索二叉树的过程叫做为线索二叉树的过程叫做“线索化线索化”,不同的遍历顺序产生的线索二叉不同的遍历顺序产生的线索二叉树相同吗？树相同吗？实线为指针（指向左、右子树）实线为指针（指向左、右子树）虚线为线索（指向前驱和后继）虚线为线索（指向前驱和后继）ADBCNULLACBD先序遍历产生的线先序遍历产生的线索二叉树索二叉树ADBCNULLACBD中序遍历产生的线中序遍历产生的线索二叉树索二叉树typedefstructBiThrNodeTElemTypedata;structBiThrNode*lchild,*rchild;/左右孩子指针左右孩子指针PointerThrLTag,RTag;/左右标志左右标志BiThrNode,*BiThrTree;二叉树的二叉线索存储表示二叉树的二叉线索存储表示typedefenumPointerThrLink,Thread;/Link=0:指针，指针，Thread=1:线索线索线索链表的遍历算法线索链表的遍历算法:由于在线索链表中添加了遍历中得由于在线索链表中添加了遍历中得到的到的“前驱前驱”和和“后继后继”的信息，从而的信息，从而简化了遍历的算法。简化了遍历的算法。for(p=firstNode(T);p;p=Succ(p)Visit(p);例如例如:对中序线索化链表的遍历算法对中序线索化链表的遍历算法中序遍历的第一个结点？中序遍历的第一个结点？在中序线索化链表中结点的后继？在中序线索化链表中结点的后继？左子树上处于左子树上处于“最左下最左下”（没有左子树）（没有左子树）的结点。的结点。若右标志为若右标志为“1 1”，则右链为线索，指，则右链为线索，指示其后继，否则后继是遍历其右子树示其后继，否则后继是遍历其右子树时访问的第一个结点时访问的第一个结点（右子树中最左（右子树中最左下的结点）下的结点）。在中序线索化链表中结点的前驱？在中序线索化链表中结点的前驱？若左标志为若左标志为“1”，则左链为线索，指，则左链为线索，指示其前驱，否则遍历左子树时最后访问示其前驱，否则遍历左子树时最后访问的一个结点的一个结点（左子树中最右下的结点）（左子树中最右下的结点）为其前驱。为其前驱。voidInSucc(BiTNode*p,BiTNode*succ)/*在中序线索二叉树中查找在中序线索二叉树中查找p的中序后继结点，的中序后继结点，并用并用succ指针返回结果指针返回结果*/if(p-Rtag=1)succ=p-RChild;/*直接利用线索直接利用线索*/else/*在在p的右子树中查找的右子树中查找最左下端最左下端结点结点*/for(q=p-RChild;q-Ltag=0;q=q-LChild);succ=q;【在中序线索树中找结点后继在中序线索树中找结点后继】voidInPre(BiTNode*p,BiTNode*pre)/*在中序线索二叉树中查找在中序线索二叉树中查找p的中序前驱的中序前驱,并用并用pre指针返回结果指针返回结果*/if(p-Ltag=1)pre=p-LChild;/*直接利用线索直接利用线索*/else/*在在p的左子树中查找的左子树中查找“最右下端最右下端”结点结点*/for(q=p-LChild;q-Rtag=0;q=q-RChild);pre=q;【在中序线索树中找结点前驱在中序线索树中找结点前驱】void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType e)p=T-lchild;/p指向根结点 while(p!=T)/空树或遍历结束时，p=Twhile(p-LTag=Link)p=p-lchild;/第一个结点if(!Visit(p-data)return ERROR;while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);/访问后继结点 p=p-rchild;/p进至其右子树根 /InOrderTraverse_Thr后继线索树中找结点后继后继线索树中找结点后继若结点若结点x x是二叉树的根是二叉树的根l后继为空后继为空若结点若结点x x是其双亲的右孩子或是其双亲的是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树左孩子且其双亲没有右子树l后继为双亲结点后继为双亲结点若结点若结点x x是其双亲的左孩子，且其双亲有是其双亲的左孩子，且其双亲有右子树右子树l后继为双亲右子树上按后序遍历出的第一个后继为双亲右子树上按后序遍历出的第一个结点结点线索化的实质是将二叉链表中的线索化的实质是将二叉链表中的空指空指针针改为改为指向前驱或后继的线索指向前驱或后继的线索，而前驱或，而前驱或后继的信息只有在遍历时才能得到，因此后继的信息只有在遍历时才能得到，因此线索化的过程即为线索化的过程即为在遍历的过程中修改空在遍历的过程中修改空指针的过程指针的过程。为了记下遍历过程中访问结。为了记下遍历过程中访问结点的先后关系，附设一个指针点的先后关系，附设一个指针pre,始终指始终指向刚刚访问过的结点，若指针向刚刚访问过的结点，若指针p指向当前指向当前访问的结点，则访问的结点，则pre指向它的前驱。指向它的前驱。如何进行二叉树的线索化？如何进行二叉树的线索化？void InThreading(BiThrTree p)if(p)/对以p为根的非空二叉树进行线索化 InThreading(p-lchild);/左子树线索化 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);/右子树线索化 /if/InThreadingStatus InOrderThreading(BiThrTree&Thrt,BiThrTree T)/构建中序线索链表if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;/添加头结点return OK;/InOrderThreading if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;/处理最后一个结点 pre-RTag=Thread;Thrt-rchild=pre;树的存储结构树的存储结构一、双亲表示法一、双亲表示法二、孩子表示法二、孩子表示法三、孩子兄弟表示法三、孩子兄弟表示法(二叉树表示法或二叉链表表示法）二叉树表示法或二叉链表表示法）一、双亲表示法一、双亲表示法:以一组连续空间存储树的结点，以一组连