第六章树无答案.ppt

《第六章树无答案.ppt》由会员分享，可在线阅读，更多相关《第六章树无答案.ppt（87页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、上页上页 下页下页节节末页末页结束结束第第 六六 章章树树 和和 二二 叉叉 树树上页上页 下页下页节节末页末页结束结束第六章第六章 树和二叉树树和二叉树6.1 树的定义和基本术语树的定义和基本术语6.2 二叉树的定义、性质和存储结构二叉树的定义、性质和存储结构6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树6.4 树和森林树和森林6.5树与等价问题树与等价问题6.6 赫夫曼树及其应用赫夫曼树及其应用上页上页 下页下页节节末页末页结束结束6 6.1.1 树的定义和基本术语树的定义和基本术语1、树的结构特点、树的结构特点结构特点结构特点:树是一个层次结构树是一个层次结构,“有有且仅有一个根结

2、点无前驱且仅有一个根结点无前驱(第一层第一层);有一或多个叶结点无后继有一或多个叶结点无后继;其余结点其余结点有唯一前驱和若干后继有唯一前驱和若干后继”。递归定义递归定义:树由根结点树由根结点(唯一唯一)及该及该根结点的若干根结点的若干(零或多个零或多个)“子树子树”组组成。不含任何结点也是树，称为空成。不含任何结点也是树，称为空树树树的图形表示ABCDEFGHIJMKL上页上页 下页下页节节末页末页结束结束6 6.1.1 树的定义和基本术语树的定义和基本术语1、树的结构特点、树的结构特点结构特点结构特点:树是一个层次结构树是一个层次结构,“有有且仅有一个根结点无前驱且仅有一个根结点无前驱(第

3、一层第一层);有一或多个叶结点无后继有一或多个叶结点无后继(最后一层最后一层);其余结点有唯一前驱和若干后继其余结点有唯一前驱和若干后继”。递归定义递归定义:树树(非空非空)由由根结点根结点(唯一唯一)及该根结点的及该根结点的若干若干(零或多个零或多个)子树子树组组成。空树不含任何结点成。空树不含任何结点ABCDEFGHIJMKL树的图形表示树的操作可递归分解成对根结点及其各树的操作可递归分解成对根结点及其各子树子树(由根节点的由根节点的孩子即子树的根孩子即子树的根标识标识)的操作进的操作进行行,直至空直至空.如求结点数如求结点数/叶结点数叶结点数/深度等深度等int NodeCount(Tr

4、ee T)/int NodeCount(Tree T)/递归法统计所有结点的个数递归法统计所有结点的个数if(Tif(T为空树为空树)n=0;)n=0;else n=1+NodeCount(else n=1+NodeCount(子树子树1 1)+NodeCount(+NodeCount(子树子树k k););return n;return n;int TreeDepth(Tree T)int TreeDepth(Tree T)/递归法求树的深度递归法求树的深度if(Tif(T为空树为空树)d=0;)d=0;elseelse d1=Tree d1=TreeDepthDepth(子树子树1);1)

5、;d dk k=Tree=TreeDepthDepth(子树子树k k););d=d=max(d1,max(d1,dk)+1;,dk)+1;return d;return d;int LeafCount(Tree T)/int LeafCount(Tree T)/递归法统计叶子结点的个数递归法统计叶子结点的个数if(Tif(T为空树为空树)n=0;)n=0;else if(Telse if(T只含一个根结点只含一个根结点)n=1;)n=1;else n=LeafCount(else n=LeafCount(子树子树1 1)+LeafCount(+LeafCount(子树子树k k););ret

6、urn n;return n;上页上页 下页下页节节末页末页结束结束2 2、ADTADT树的定义树的定义-逻辑结构逻辑结构右例：右例：D=A,B,M H=数据对象数据对象D:若干数据元素的集合若干数据元素的集合数据关系数据关系R:若若|D|=0或或1则则R为空为空,否则否则R=H,H具体定义如下具体定义如下:(1)D中有唯一元素无前驱中有唯一元素无前驱,root (2)若若D-root非空则存在它的一个划分非空则存在它的一个划分D1Dm使得任意两个使得任意两个Di与与Dj不相交不相交,且每个且每个Dk中中存在唯一元素存在唯一元素xi使得使得 H (3)对应于元素集合对应于元素集合D-root的

7、划分，关系的划分，关系集合集合H-,也存在划分也存在划分H1Hm，使得，使得(Di,Hi)也是一个树也是一个树(root的子树的子树)ABCDEFGHIJMKL树的图形表示上页上页 下页下页节节末页末页结束结束3 3、树的相关术语树的相关术语空树空树 根结点根结点(可标识一颗树可标识一颗树)叶子结点叶子结点结点的子树结点的子树 树的子树树的子树 结点的度结点的度 (叶子结点的度为几叶子结点的度为几)树的度树的度终端结点终端结点 非终端非终端(分支分支)结点结点 内部结点内部结点结点的孩子结点的孩子/双亲双亲/兄弟兄弟/祖先祖先/子孙子孙/堂兄弟堂兄弟结点的层次结点的层次(从从1始始)树的深度、

8、宽度树的深度、宽度无序树无序树 有序树有序树森林森林:互不相交的树的集合互不相交的树的集合Tree=(root,F)，F=T1,TmTi=ri,Fi,RF路径与路径长度，如路径与路径长度，如A-D-J长为长为2从根结点到任意结点存在唯一路径从根结点到任意结点存在唯一路径ABCDEFGHIJMKL树的树形表示上页上页 下页下页节节末页末页结束结束InitTree(&T)CreateTree(&T,definition)InsertChild(&T,&p,i,c)/插入插入c c为为T T中中p p所指结点的第所指结点的第i i子树子树,c,c为子树的根为子树的根,可唯一确定子树可唯一确定子树Cl

9、earTree(&T)DestroyTree(&T)DeleteChild(&T,&p,i)/删除结点删除结点p p的第的第i i棵子树棵子树4 4、ADTADT树的定义树的定义基本操作（略）基本操作（略）上页上页 下页下页节节末页末页结束结束Root(T)/求树求树T的根结点的根结点 Value(T,cur_e)/求求cur_e结点的元素值结点的元素值 Parent(T,cur_e)/求求cur_e结点的双亲结点结点的双亲结点LeftChild(T,cur_e)/返回返回cur_e结点的最左孩子结点的最左孩子,可标示整个左子树可标示整个左子树RightSibling(T,cur_e)/求求c

10、ur_e结点的右兄弟结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树 TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历引用型基本操作（略）引用型基本操作（略）Assign(T,&cur_e,valueAssign(T,&cur_e,value)/)/给给cur_ecur_e结点赋值为结点赋值为value value 上页上页 下页下页节节末页末页结束结束(A(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根树根5 5、树的表示方法树的表示方法ABCDEFGHIJMKLABDCJIHMFEGKL广义表表

11、示广义表表示:将树写作将树写作(root(F)root(F)的形式的形式A B E F K L C上页上页 下页下页节节末页末页结束结束6.2 6.2 二叉树二叉树二叉树的定义、二叉链表存储二叉树的定义、二叉链表存储(与基本操作与基本操作)二叉树的性质二叉树的性质二叉树的其它存储结构二叉树的其它存储结构abcdefghij1234上页上页 下页下页节节末页末页结束结束 二叉树是度不大于2的有序树有序树(每个结点最多两棵子树,子树有左右之分),具体定义类树可得1 1、二叉树的概念二叉树的概念N空树空树只含根结点只含根结点NNNTTR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树均不为

12、空树左右子树均不为空树不考虑节点内元素值不考虑节点内元素值,含含2 2或或3 3结点的二叉树与树各有几种形态结点的二叉树与树各有几种形态?上页上页 下页下页节节末页末页结束结束InitBiTree(&T)CreateBiTree(&T,definition)InsertChild(&T,p,LR,c)/LR为为0或或1,插入右子树为空的二叉树插入右子树为空的二叉树c c为为T T中中p p所指结点的左或右子树所指结点的左或右子树ClearBiTree(&T)DestroyBiTree(&T)DeleteChild(&T,&p,LR)/删除结点删除结点p p的左或右子树的左或右子树二叉二叉树的基

13、本操作（先了解）树的基本操作（先了解）上页上页 下页下页节节末页末页结束结束Root(T)Value(T,cur_e)Parent(T,cur_e)LeftChild(T,cur_e)/返回返回T中中cur_e结点的左孩子结点的左孩子,作为作为左子树的根可代表左子树左子树的根可代表左子树RightChild(T,cur_e)/求求T中中cur_e结点的右孩子结点的右孩子,作为右作为右子树的根可代表右子树子树的根可代表右子树RightSibling(T,cur_e)/求求cur_e结点的右兄弟结点的右兄弟BiTreeEmpty(T)BiTreeDepth(T)引用型基本操作（有重点的看）引用型基

14、本操作（有重点的看）PreOrderTraverse(T,Visit();/先序遍历先序遍历 InOrderTraverse(T,Visit();/中序遍历中序遍历 PostOrderTraverse(T,Visit();/后序遍历后序遍历 LevelOrderTraverse(T,Visit();/层次遍历层次遍历Assign(T,&cur_e,value)/给给cur_ecur_e结点赋值结点赋值上页上页 下页下页节节末页末页结束结束先先(根根)序遍历序遍历:树非空则访问根结点树非空则访问根结点,后后递归地递归地先序遍历其左子树；再先序遍历其左子树；再递归地递归地先序先序遍历其右子树；空则

15、无操作。遍历其右子树；空则无操作。中中(根根)序遍历序遍历:树树非空则非空则递归地递归地中序遍历中序遍历根左子树；后访问根结点根左子树；后访问根结点,再再递归地递归地中序中序遍历右子树；空则无操作。遍历右子树；空则无操作。s2s2-s1-s1-s3s3 后后(根根)序遍历序遍历:树树非空则非空则递归地递归地后序遍历后序遍历根右子树；后根右子树；后递归地递归地后序遍历右子树后序遍历右子树,再再访问根结点；空则无操作访问根结点；空则无操作s2s2-s3-s3-s1-s1层次遍历层次遍历:由上到下由上到下,由左到右由左到右,不宜递归不宜递归Status PreOrderTraverse(BiTree

16、 T,Status(*visit)(TElemType)Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType)if(T if(T为空树为空树)return OK;)return OK;else if(T else if(T不空不空)(*visit)(T (*visit)(T的根结点的根结点 );/s1);/s1 PreOrderTraverse(T PreOrderTraverse(T的左子树的左子树,(*visit);/s2,(*visit);/s2 PreOrderTraverse(T PreOrderTraverse(T的右子

17、树的右子树,(*visit);/s3(*visit);/s3 return OK return OK 1234先序输出:1 2 3 4中序输出:2 3 1 4后序输出:3 2 4 1层次输出:1 2 4 3上页上页 下页下页节节末页末页结束结束 A D E B C F T2.2.存储结构：二叉链表存储结构：二叉链表typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree T;/思考树的操作?lchild data rchild上页上页 下页下页节节末页末页结束结束3.1

18、 3.1 操作：求树深操作：求树深【补补】int TreeDepth(BiTree T)int TreeDepth(BiTree T)/递归法求树的深度递归法求树的深度if(T=NULL)d=0;if(T=NULL)d=0;elseelse d1=Tree d1=TreeDepthDepth(T-lchild1);d(T-lchild1);d2 2=Tree=TreeDepthDepth(T-rchild);(T-rchild);if(d1d2)if(d1d2)d=dd=d1+1;1+1;else d=d2+1;else d=d2+1;return d;return d;/其余操作类似实现，务

19、必掌握其余操作类似实现，务必掌握typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;思路：如果树为空树则深度为思路：如果树为空树则深度为0 0，否则，先递归计算出左子树的深度，再计算，否则，先递归计算出左子树的深度，再计算出右子树的深度，最后，树的深度为两子树深度的最大值加出右子树的深度，最后，树的深度为两子树深度的最大值加1 11234上页上页 下页下页节节末页末页结束结束3.23.2操作：遍历二叉树操作：遍历二叉树【P129P129】先先(根根)序遍历序遍历:树空无操作，非

20、空则先访树空无操作，非空则先访问根结点问根结点,后后递归地递归地先序遍历其左子树；先序遍历其左子树；再再递归地递归地先序遍历其右子树。先序遍历其右子树。中中(根根)序遍历序遍历:树树非空则非空则递归地递归地中序遍历中序遍历根左子树；后访问根结点根左子树；后访问根结点,再再递归地递归地中序中序遍历右子树。遍历右子树。s2s2-s1-s3-s1-s3 后后(根根)序遍历序遍历:树树非空则非空则递归地递归地后序遍历后序遍历左子树；后左子树；后递归地递归地后序遍历右子树，再访后序遍历右子树，再访问根结点。问根结点。s2s2-s3-s3-s1-s1ABCDEFGHK先序先序:A B C D E F G

21、H K:A B C D E F G H K中序中序:B D C A H G K F E:B D C A H G K F E后序后序:D C B H K G F E A:D C B H K G F E AStatus PreOrderTraverse(BiTree T,Status(*visit)(TElemType)Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType)if(!T)return OK;if(!T)return OK;else if(T else if(T不空不空)(*visit)(T (*visit)(T的根结点的根

22、结点 );/s1);/s1 PreOrderTraverse(T PreOrderTraverse(T的左子树的左子树,(*visit);/s2,(*visit);/s2 PreOrderTraverse(T PreOrderTraverse(T的右子树的右子树,(*visit);/s3(*visit);/s3 return OK;return OK;/尚需具体实现尚需具体实现,visit,visit可能失败，如求倒数可能失败，如求倒数Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType)Status PreOrderTravers

23、e(BiTree T,Status(*visit)(TElemType)if(T)if(T)if(*visit)(T-data)/s1 if(*visit)(T-data)/s1 if(PreOrderTraverse(T-lchild,(*visit)/s2 if(PreOrderTraverse(T-lchild,(*visit)/s2 if(PreOrderTraverse(T-rchild,(*visit)/s3 if(PreOrderTraverse(T-rchild,(*visit)/s3 return OK;return OK;return ERROR;/return ERROR

24、;/只要有一次访问失败则必执行此语句只要有一次访问失败则必执行此语句 return OK;/return OK;/树空时返回树空时返回OK OK 上页上页 下页下页节节末页末页结束结束算法思路算法思路:定义输出函数定义输出函数PrintElemPrintElem，调用树的先序遍历函数，调用树的先序遍历函数,并并将其传递给先序遍历函数中的参数将其传递给先序遍历函数中的参数visitvisit即可即可,假设元素为整型假设元素为整型3.3 3.3 操作操作:二叉链表的先序输出二叉链表的先序输出【补补】Typedef int TElemType;Typedef int TElemType;Typede

25、f Typedef BiTree BiTreeStatus PrintTElem(TElemType e)printf(%d,e);return OK;Status PrintTElem(TElemType e)printf(%d,e);return OK;Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType)Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType)if(T)if(T)if(*visit)(T-data)if(*visit)(T-data)if(PreOrd

26、erTraverse(T-lchild,(*visit)if(PreOrderTraverse(T-lchild,(*visit)if(PreOrderTraverse(T-rchild,(*visit)if(PreOrderTraverse(T-rchild,(*visit)return OK return OK return ERROR;return ERROR;else return OK;else return OK;void main()BiTree T;void main()BiTree T;PreOrderTraverse(T,PrintTElem);PreOrderTraver

27、se(T,PrintTElem);上页上页 下页下页节节末页末页结束结束typedef int TElemType;typedef int TElemType;Status CreateBiTree(BiTree&T)Status CreateBiTree(BiTree&T)TElemType e;scanf(%d,&e);TElemType e;scanf(%d,&e);if(e=0)T=NULL;if(e=0)T=NULL;else else T=(BiTree)malloc(sizeof(BiTNode);T=(BiTree)malloc(sizeof(BiTNode);if(!T)ex

28、it(OVERFLOW);if(!T)exit(OVERFLOW);T-data=e;T-data=e;CreateBiTree(T-lchild);CreateBiTree(T-lchild);CreateBiTree(T-rchild);CreateBiTree(T-rchild);return OK;return OK;/若元素若元素为字符为字符型则输入时不可型则输入时不可随意加空格随意加空格先序创建：若输入为先序创建：若输入为0 0则创建一个空树则创建一个空树,停止。否则创建根结点，递停止。否则创建根结点，递归创建左子树，递归创建右子树。如归创建左子树，递归创建右子树。如1203004

29、001203004003.43.4操作：二叉链表的创建操作：二叉链表的创建【P131P131】12 34先序创建:1 2 0 3 0 0 4 0 0上页上页 下页下页节节末页末页结束结束Status DestroyBiTree(BiTree&T)Status DestroyBiTree(BiTree&T)if(if(!T)T)return OK;return OK;else else DestroyBiTree(T-lchild);DestroyBiTree(T-lchild);DestroyBiTree(T-rchild);DestroyBiTree(T-rchild);free(T);fr

30、ee(T);T T=NULL;/=NULL;/不可丢！不可丢！return OK;return OK;算法思路：树为空什么都不作，否则，先递归释放左子树，后算法思路：树为空什么都不作，否则，先递归释放左子树，后递归释放右子树，最后释放根结点。递归释放右子树，最后释放根结点。3.53.5操作操作:二叉链表的后序递归销毁二叉链表的后序递归销毁【补补】上页上页 下页下页节节末页末页结束结束遍历应用遍历应用:由遍历序列确定二叉树由遍历序列确定二叉树(P(P154154例例6-6-5)5)先序序列先序序列+中序序列中序序列:先序序列中第先序序列中第1 1个元素个元素X X为根为根,中序序列中唯有遍历完中

31、序序列中唯有遍历完X X的左子树后方的左子树后方访问访问X,X,故故X X之前的之前的abcabc必构成必构成X X的左子树的左子树,X,X之之后的后的defdef必构成必构成X X的右子树的右子树.对于子树类似处对于子树类似处理理,第第1 1个在先序序列中出现的元素个在先序序列中出现的元素Y Y为该左子为该左子树的根树的根,中序序列中中序序列中Y Y左侧的元素构成左侧的元素构成Y Y的左子的左子树树,右侧构成右子树右侧构成右子树,依此类推依此类推,最终可定最终可定中序序列中序序列+后序序列后序序列:后后序序列中最后一个序序列中最后一个元素为根元素为根,中序序列中该结点前的元素为左子中序序列中

32、该结点前的元素为左子树树,后的元素为右子树。对于左后的元素为右子树。对于左/右子树右子树,最后最后一个在后序序列中出现的元素为子树的根结点一个在后序序列中出现的元素为子树的根结点,再看中序序列再看中序序列,依此类推依此类推先序输出先序输出+后序输出不能确定后序输出不能确定.如如ABAB和和BABA1234 先序输出:1 2 3 4 中序输出:2 3 1 4 后序输出:3 2 4 1先序先序先序先序-+1*2-34/56+1*2-34/56+1*2-34/56+1*2-34/56中序中序中序中序1+2*3-41+2*3-41+2*3-41+2*3-4-5/65/65/65/6后序后序后序后序12

33、34-*+56/1234-*+56/1234-*+56/1234-*+56/-A AB BA AB B思考思考思考思考:何时先序与中序序列相同何时先序与中序序列相同何时先序与中序序列相同何时先序与中序序列相同,后中序同、先后同如何？后中序同、先后同如何？后中序同、先后同如何？后中序同、先后同如何？上页上页 下页下页节节末页末页结束结束遍历应用遍历应用P129:P129:表达式的二叉树表示表达式的二叉树表示6/5-43-12*+先序先序:-+1*2-34/56-+1*2-34/56-+1*2-34/56-+1*2-34/56 前缀表达式前缀表达式/波兰式波兰式中序：中序：1+2*3-4-5/61

34、+2*3-4-5/6 中缀表达式中缀表达式后序后序:1234-*+56/-1234-*+56/-1234-*+56/-1234-*+56/-后缀表达式后缀表达式/逆波兰逆波兰对于中缀表达式对于中缀表达式(e1)OP(e2)(e1)OP(e2)，令根结点值为，令根结点值为OPOP，左子树为左子树为e1e1，右子树，右子树e2e2，e1e1与与e2e2递归。如递归。如1+2*(3-1+2*(3-4)-5/64)-5/6即即(1)+(2)*(3-4)-(5)/(6)(1)+(2)*(3-4)-(5)/(6)根据后缀表达式可直接求值根据后缀表达式可直接求值(不用考虑优先级不用考虑优先级)，但求后缀式过

35、程中需用优先级。算符优先法实际但求后缀式过程中需用优先级。算符优先法实际在执行过程中隐含形成的逻辑结构就是一颗树。在执行过程中隐含形成的逻辑结构就是一颗树。上页上页 下页下页节节末页末页结束结束作业作业补充：编写递归算法，计算二叉数结点数补充：编写递归算法，计算二叉数结点数42、编写递归算法、编写递归算法,计算二叉树中叶子结点计算二叉树中叶子结点的数目的数目说明说明1：假设采用二叉链表存储结构：假设采用二叉链表存储结构说明说明2：分三部分，存储结构定义：分三部分，存储结构定义+思路思路+代码代码上页上页 下页下页节节末页末页结束结束中序遍历的非递归描述中序遍历的非递归描述-完全模拟完全模拟递归

36、递归:调用递归函数时树空则直接返回调用递归函数时树空则直接返回;树树不空不空先先递归递归访问左子树访问左子树,中间访问根节点，最后递归访问右子树中间访问根节点，最后递归访问右子树转化转化:何时入栈？何时出栈何时入栈？何时出栈?入栈、出栈时作什么操作入栈、出栈时作什么操作？何时结束？何时结束？【空树空树 单节点树单节点树 普通树普通树】模拟模拟:T T入栈入栈,重复如下操作至栈空：重复如下操作至栈空：只要栈顶元素不只要栈顶元素不为为 则则 其左孩子入栈其左孩子入栈。最后栈顶必为。最后栈顶必为，出栈。若下，出栈。若下一个栈顶元素不空则出栈访问且右孩子入栈一个栈顶元素不空则出栈访问且右孩子入栈 12

37、35Status InOrderTraverse_NonRecur(BiTree T,Status(*visit)(ElemType)Status InOrderTraverse_NonRecur(BiTree T,Status(*visit)(ElemType)SqStack S;SqStack S;InitStack(S);InitStack(S);Push(S,T););/Push(S,T););/入栈入栈whilewhile(!StackEmpty(S)(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);/while(GetTop(S

38、,p)&p)Push(S,p-lchild);/入栈入栈 Pop(S,p);/Pop(S,p);/出栈出栈 if(!StackEmpty(S)if(!StackEmpty(S)Pop(S,p);(*vist)(p-data);Push(S,p-rchild);/Pop(S,p);(*vist)(p-data);Push(S,p-rchild);/操作操作 return OK;return OK;上页上页 下页下页节节末页末页结束结束中序遍历的非递归描述中序遍历的非递归描述-略加总结略加总结递归递归:树空时无操作树空时无操作;树树不空时不空时先先递归访问左子树递归访问左子树,中间中间访问根节点，

39、最后递归访问右子树访问根节点，最后递归访问右子树转化转化:何时入栈？何时出栈何时入栈？何时出栈?入栈、出栈时作什么操作入栈、出栈时作什么操作总结总结：设指针：设指针p p指向根结点指向根结点:如果如果p p不空不空,入栈入栈,之后之后p p指指向左孩子向左孩子,开始下次循环开始下次循环;否则否则p p空空,出栈出栈访问访问,令指针指令指针指向出栈元素的右孩子向出栈元素的右孩子,开始下次循环重复至开始下次循环重复至p p和栈空和栈空1234Status InOrderTraverse_NonRecur(BiTree T,Status(*visit)(ElemType)Status InOrder

40、Traverse_NonRecur(BiTree T,Status(*visit)(ElemType)SqStack S;SqStack S;InitStack(S);InitStack(S);BiTNode*p=T;BiTNode*p=T;whilewhile(p|!EmptyStack(S)(p|!EmptyStack(S)if(p)if(p)Push(S,p);Push(S,p);p=p-lchild;p=p-lchild;else else Pop(S,p);Pop(S,p);if(!(*vist)(p-data)return ERROR;if(!(*vist)(p-data)retu

41、rn ERROR;p=p-rchild;p=p-rchild;return OK;return OK;时间复杂度时间复杂度:每个结点访问每个结点访问3次次,T(n)=O(n)空间复杂度空间复杂度:栈空间栈空间,遍历过程中最大栈长遍历过程中最大栈长O(n)上页上页 下页下页节节末页末页结束结束小小 结结树的结构特点及树的结构特点及递归定义递归定义(非空树由根结点及其子树组成非空树由根结点及其子树组成),二叉树二叉树的定义，对二叉树的操作可递归分解成对根结点、的定义，对二叉树的操作可递归分解成对根结点、左子树左子树(由根节由根节点的点的左孩子左孩子标识标识)、右子树、右子树(根节点根节点右孩子右孩

42、子标识标识)的操作进行的操作进行.如求结点如求结点数数/叶结点数叶结点数/深度深度/复制复制/左右互换左右互换int NodeCount(Tree T)/int NodeCount(Tree T)/递归法统计所有结点的个数递归法统计所有结点的个数if(Tif(T为空树为空树)n=0;)n=0;else n=1+NodeCount(else n=1+NodeCount(子树子树1 1)+NodeCount(+NodeCount(子树子树k k););return n;return n;int LeafCount(Tree T)/int LeafCount(Tree T)/递归法统计叶子结点的个数

43、递归法统计叶子结点的个数if(Tif(T为空树为空树)n=0;)n=0;else if(Telse if(T只含一个根结点只含一个根结点)n=1;)n=1;else n=LeafCount(else n=LeafCount(子树子树1 1)+LeafCount(+LeafCount(子树子树k k););return n;return n;上页上页 下页下页节节末页末页结束结束小小 结结二叉树的二叉链表存储结构、操作及二叉树的二叉链表存储结构、操作及先先/中中/后后/层序层序遍历遍历int int BiBiTreeDepth(TreeDepth(BiBiTree T)Tree T)/递归法求树

44、的深度递归法求树的深度if(T=if(T=NULL)d=0;=NULL)d=0;elseelse d1=Tree d1=TreeDepthDepth(T-lchild1);d(T-lchild1);d2 2=Tree=TreeDepthDepth(T-rchild);(T-rchild);if(d1d2)if(d1d2)d=dd=d1+1;else d=d2+1;1+1;else d=d2+1;return d;return d;/注意创建一个二叉树的原理、测试步骤注意创建一个二叉树的原理、测试步骤typedef struct BiTNode TElemType data;struct BiT

45、Node *lchild,*rchild;BiTNode,*BiTree;上页上页 下页下页节节末页末页结束结束6.2 6.2 二叉树二叉树二叉树的定义、二叉链表存储二叉树的定义、二叉链表存储(与基本操作与基本操作)二叉树的性质二叉树的性质二叉树的其它存储结构二叉树的其它存储结构abcdefghij1234上页上页 下页下页节节末页末页结束结束6.2.2 6.2.2 二叉树的性质二叉树的性质性质性质1:在二叉树的第在二叉树的第i层上最多有层上最多有2i-1个结点（个结点（i1）性质性质2:深度为深度为K的二叉树最多有的二叉树最多有2K-1个结点（个结点（K1）性质性质3:对于任意一棵二叉树对于

46、任意一棵二叉树BT，如，如果度为果度为0的结点个数为的结点个数为n0，度为，度为2的结的结点个数为点个数为n2，则，则n0=n2+1。证证:二叉树上结点总数 n=n0+n1+n2 二叉树上边的总数 e=n1+2n2 根结点外每个结点都有且仅有一条边根结点外每个结点都有且仅有一条边(分支分支)”进入进入”,故故e=n-1 由此由此n-1=n0+n1+n2-1，进而，进而 n0=n2+1。12345678 9 101112131415上页上页 下页下页节节末页末页结束结束满二叉树与完全二叉树：满二叉树与完全二叉树：满二叉树：设深度为满二叉树：设深度为k,k,含含2 2k k-1-1个个结点的二叉树

47、。结点数达最大结点的二叉树。结点数达最大完全二叉树：设树中含完全二叉树：设树中含完全二叉树：设树中含完全二叉树：设树中含n n n n个结点个结点个结点个结点,它它它它们和满二叉树中编号为们和满二叉树中编号为们和满二叉树中编号为们和满二叉树中编号为1 1 1 1至至至至n n n n的结点位的结点位的结点位的结点位置上一一对应置上一一对应置上一一对应置上一一对应(编号规则为由上到下，编号规则为由上到下，编号规则为由上到下，编号规则为由上到下，从左到右）。相比满二叉树仅少从左到右）。相比满二叉树仅少从左到右）。相比满二叉树仅少从左到右）。相比满二叉树仅少“最最最最后的后的后的后的”若干个，不能少

48、中间的若干个，不能少中间的若干个，不能少中间的若干个，不能少中间的123456789 10 11 12 13 14 15abcdefghij完全二叉树特点完全二叉树特点完全二叉树特点完全二叉树特点:(1):(1):(1):(1)叶子结点出现在最后叶子结点出现在最后叶子结点出现在最后叶子结点出现在最后2 2 2 2层或多或层或多或层或多或层或多或1 1 1 1层层层层(2)(2)(2)(2)对于任意结点，若其右分支下的子孙的最大层次为对于任意结点，若其右分支下的子孙的最大层次为对于任意结点，若其右分支下的子孙的最大层次为对于任意结点，若其右分支下的子孙的最大层次为L,L,L,L,则左分支下的子孙

49、的最大层次为则左分支下的子孙的最大层次为则左分支下的子孙的最大层次为则左分支下的子孙的最大层次为L L L L或或或或L+1L+1L+1L+1上页上页 下页下页节节末页末页结束结束证证:设完全二叉树的深度为设完全二叉树的深度为 k 则据性质则据性质2得得 2k-1-1 2k-1 n 2k-1 2k 即即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+1n，则该结点无右孩子，否则，编号为2i+1 的结点为其右孩子右孩子结点。123456789 10 11 12 13 14 15上页上页 下页下页节节末页末页结束结束6.2.36.2.3

50、二叉树的存储结构二叉树的存储结构顺序存储顺序存储顺序存储结构顺序存储结构 :将二叉树映射到完全二叉树上，不存在将二叉树映射到完全二叉树上，不存在的结点以空标记的结点以空标记，之后用地址连续的存储单元(一维数组)依次自上而下、自左而右存储完全二叉树上完全二叉树上的各元素.(将一般二叉树以完全二叉树形式存储),最坏情况下k个结点需2 2k k-1-1个单元。空间可能浪费，但适合完全二叉树的存储，操作简单方便ABCDEFABCDEFA B D C E F 上页上页 下页下页节节末页末页结束结束6.2.36.2.3二叉树的存储结构二叉树的存储结构顺序存储顺序存储顺序存储结构顺序存储结构用地址连续的存储