第5与二叉树树

1、数据结构与算法第五章 二叉树和树（二）王昭信息学院wangzhaoi1wangzhao内容提要 二叉树 二叉树的应用 树与树林2wangzhao树与树林树的定义基本术语树林树的基本运算树的周游树林的周游树、树林与二叉树的转换树和树林的表示3wangzhao关系行政区社会机构：公司-处-科-室书籍目录：书-章-节小节物种分类：门-纲-类-科-目种4wangzhao教学内容第二章第三章第九章第一章演示随堂小测作业提交和讲评源程序示例动画演示授课课件课件 2中源程上机作业讲评课件1中动画动画动画书面上机授课授课作业源程序演示 n演示 2演示 1作业作业课件 2课件 1序及讲评源程序n源程序1源程序2

2、5wangzhao幼儿园初中大学高中工作小学大四大三大二大一好友 C好友 B班级中班级羽中秋晚毕业留班级秋班级篮球班级室友A生赛来访春游日聚会来访球晚会毛球赛会影游6wangzhao建筑设计素材网首页室内模型素材建筑景观室内设计方建筑动画素材建筑效果图素材建筑设计书籍室内设计书籍景观设计书籍案景观设室内设建筑设计方案计方案计方案建筑景观室内建筑景观建筑景观室内设计方案 2设计方案 2设计方案 1设计方案 1设计方案 1设计方案 n设计方案 n设计方案 27wangzhao树的表现形式ABCDEFGHIJ（a）树形表示b入8wangzhao树的表现形式(c)文氏图ABGCHDFIEJ(A(B(D

3、)(E(I)(J)(F)(C(G)(H)(d)嵌套括号表示法9wangzhao树的定义树的递归定义：n(n0)个结点的有穷集合T，当T非空时满足：有且仅有一个特别标出的称为根的结点除根外，其余结点分为m0个互不相交的非空集合T1,T2,Tm，而且每个非空集合Ti又是一颗树，称为根结点的。T1=B，T2=C，E，H，I，J， T3=D，F，G特别地，允许不包括任何结点的树，把它称作空树。10wangzhao树的特点在一棵树中，通常将一个结点定义为其的根结点的前驱结点，而的根结点就是它的后继结点。根结点没有前驱结点，其它结点有唯一前驱所有结点可以有零个或多个后继树描述的是层次关系，数据元间存在一对

4、多或多对一关系。11wangzhao树与树林树的定义基本术语树林树的基本运算树的周游树林的周游树、树林与二叉树的转换树和树林的表示12wangzhao树和二叉树之间差别二叉树不是树的特殊情形，它们是两个概念。树和二叉树之间差别二叉树中结点的在结点只有一棵树还是右树和二叉树之间相同处要区分为树和右，即使是的情况下也要明确该父结点、子结点、路径、路径长度等概念与二叉树的定义相同13wangzhao基本术语1无序树、有序树对的次序不加区别的树叫作“无序树”。对之间的次序加以区别的树叫作“有序树”例如在右图中，按无序树的概念t和t是同一棵树，按有序树的概念则是不同的树，本章讨论的树一般是有序树wang

5、zhao基本术语2结点的次序在有序树中可以从左到右地规定结点的次序例如图中，结点2，3，4是从左到右排序的；可以说结点3是结点2右边的结点，是结点4左边的结点还可以说结点3的所有都在结点2及其的右边，而在结点4及其的左边按从左到右的顺序，可以把一个结点的最左边的结点简称“最结点”或“长子”，长子右边的结点称为“次子”注意：祖先与子孙之间不存在左右的概念。15wangzhao树与树林树的定义基本术语树林树的基本运算树的周游树林的周游树、树林与二叉树的转换树和树林的表示16wangzhao树林的概念“树林”是由0个到多个不相交的树所组成的集O合树林中每棵树的根彼此称为“兄弟”，与自然界的树林有所不

6、同， 这里的树林可以是一个空集。如果从一棵树中将根结点（连同根结点到各子结点的边） 删除，便得到一个树林17wangzhao树与树林树的定义基本术语树林树的基本运算树的周游树林的周游树、树林与二叉树的转换树和树林的表示18wangzhao树的基本运算1Tree t;Node p;1.TreecreatTree(NodeP,Treet1,Treet2,.,Treeti)(i=1,2,3,.)创建一棵空树；2.isNULL(Tree t)判断某棵树是否为空；3.Node root(Tree t)求树中的根结点，若为空树，则返回一特殊值；Node parent(Node P)求树中某个指定结点p的父

7、结点，当指定结点为根时，4.返回一特殊值；19wangzhao树的基本运算2eftChild (Node p)5.N求树中某个指定结点p的最结点，当指定结点为树叶时，它没有，则返回一特殊值；6.Node rightSibling(Node P)求树中某个指定结点p的右兄弟结点，当指定结点没有右兄弟时，返回一特殊值；7.树的周游，即按某种方式树中的所有结点，并使每个结点恰好被一次20wangzhao树与树林树的定义基本术语树林树的基本运算树的周游树林的周游树、树林与二叉树的转换树和树林的表示21wangzhao树的周游定义：对一棵树进行“周游”就是按某一规律系统地树的所有结点，并使每个结点恰好被

8、一周游的结果： 存放：在周游树的过程中，如果将各个结点按其被的先后顺序排列起来，则到一个包括所有结点的线性表 周游空树得到的线性表为空表 当树中只有一个结点时，对应的线性表也只有一个元素 除以上两种情况外，周游一棵树所得到的线性表依赖于周游方法本质：将非线性结构转换为线性结构。22wangzhao周游方法按深度方向周游纵向遍历按宽度方向周游横向遍历23wangzhao按深度方向周游 主要有以下三种方法：先根次序中根次序后根次序24wangzhao先根次序根结点；从左到右按先根次序周游根结点的每棵按先根次序周游所列出的线性表为：12358961047通常按先根次序对一棵树周游得到的线性称为这棵树

9、的先根序列。25wangzhao按先根次序周游树的算法/递归算法void preOrder(Node p)Node c;visit(p);c = leftChild(q);/*获取该结点的长子*/然后按照从左往右的次序先根遍历该结点的while (c!=NULL)reOrderc/先根遍历c = rightSibling(c);/右兄弟26wangzhao中根次序按中根次序周游根结点的最根结点；树；从左到右按中根次序周游根结点的其它各按中根次序周游得到的线性表为：21859310674通常按中根次序对一棵树周游得到的线性表称为这棵树的中根序列。按中根次序周游树的递归算法27wangzhao后根

10、次序从左到右按后根次序周游根结点的每棵；根结点按后根次序周游得到的线性表为：28951063741通常按后根次序对一棵树周游得到的线性表称为这棵树的后根序列。28wangzhao按后根次序周游树的递归算法voidtOrder(Node p)Node c;c = leftChild(q);/获取该结点的长子/然后按照从左往右的次序后根遍历该结点的所有while (c!=NULL)tOrder( c);/后根遍历c = rightSibling(c);/继续后根遍历右兄弟visit(p);/最后根29wangzhao遍历特点相同点：在先、中和后根遍历序列中，树结点的左右次序不变;不同点：那些属于同

11、一条路径上的结点，即只有祖先孙之间的相对次序，在上述三种序列中可能有所不同在先根遍历序列中，结点的所有子孙都紧密排列在该结点的右边；假定 ost n 表示结点n在先根序列中的位置，desc(n)表示结点n的子孙个数，则结点x是结点n的子孙的充分必要条件为： ost n +desc nost xost n在后根遍历序列中，结点的所有子孙都紧密排列在该结点的左边；假定 ost n 表示结点n在后根序列中的位置，desc(n)表示结点n的子孙个数，则结点x是结点n的子孙的充分必要条件为： ost n -desc nost xnistp+1.parent = p)return p+1;elseretu

12、rn -1;50wangzhao求右兄弟结点的位置rightSibling_partree(PParTree t,p)if(p=0 & pn)-n; i+)if (t-nisti.parent = t-nreturn i;istp.parent;)return 1;51wangzhao树的表示树的表示父指针表示法子表表示法双亲表示法孩子表示法长子-兄弟表示法 孩子兄弟表示法树林的表示52wangzhao树的子表表示法方法：把整棵树看成一个结点表，而结点表中的每个元素又包一表，它了这结点的有子结点的置，称为“子表”结点表的长度即树中结点的个数，通常采用顺序的方式表示而子表的长度依赖于各结点的度数

13、，所以各不相同，一般用表示子表中结点的进行的在结点表中需要保存子表的表头指针顺序是按其在树中从左到右的次序53wangzhao子表的结点结构定义nodeition;/nodeition是子结点在nist数组中的位置structEdgeNode*link;wangzhao/link则是指向子表中下一个元素（右兄弟）的指针;struct ChiTreeNode/* 结点表中结点的结构 */Daype info;/ info字段是树结点的信息struct EdgeNode *children;/children是一个指针，指向子表中的第一个元素;struct EdgeNode/* 子表中结点的结构

14、*/子表表示的树结构的定义n;/*结点的个数*/structChiTreeNode*nist;55wangzhao;typedef struct ChiTree *PChiTree;/*树类型的指针类型*/struct ChiTree/* 树结构 */MAXNUM;root;/* 根结点的下标 */子表表示的特点优点：方便找女、找所有等缺点： 找父结点和找右兄弟麻烦，因为要找某结点的父结点必须依次检查每个结点的子表中是否包含该结点，而要找某结点的右兄弟时，则首先要找到其父结点，然后再从父结点的子表中找寻它的右兄弟结点一个新树时(createTree_chitree操 合并若干个作)也要考虑多个

15、结点表的合并问题,因为结点表通常用顺序表示,合并起来比较麻烦.56wangzhao求右兄弟结点的位置rightSibling_chitree(PChiTree t, i;struct EdgeNode *v; for (i=0; i n; i+)p)v = t-nisti.children;while (v!=NULL)-nodeition = p)if (v-link=NULL)return 1;elsereturn v-link-nodeition;elsev = v-link; return 1;57wangzhao求父结点的位置parent_chitree(PChiTree t, i;

16、struct EdgeNode *v;p)for (i = 0; i n;i+)/*逐个检查树的各个结点,是不是父结点*/v = t-nisti.children;/*若检查的结点子表中有p,则返回值是该结点的位置*/while(v!=NULL)if (v-nodeition = p)return(i);elsev = v-link;return 1; /*无父结点,则返回值为-1*/58wangzhao树的表示树的表示父指针表示法子表表示法双亲表示法孩子表示法长子-兄弟表示法 孩子兄弟表示法59wangzhao长子-兄弟表示法女的指针lchild和在树的每个结点中设一个指向其最一个指向其右兄

17、弟的指针rsibling，其类型定义为structCSNode;/* 树中结点结构 */typedef struct CSNode *PCSNode; /*结点的指针类型*/struct CSNode/* 结点结构定义*/Daeinfo/* 结点中的元素 */PCSNode PCSNodelchild;/* 结点的最女的指针 */rsibling;/* 结点的右兄弟的指针 */;typedef typedefstruct CSNode*CSTree;/* 树类型定义 */CSTree*PCSTree;/* 树类型的指针类型 */60wangzhao长子-兄弟表示法对于任意一棵树，可以可定义一个

18、指向树的指针变量：PCSTreet;*t为指向树根结点的指针，也叫根指针，根指针既根结点的位置，又用来标识一树；树中其它各个结点按其逻辑关系用指针字段lchild和rsibling相；61wangzhao长子-兄弟表示法示意图62wangzhao长子-兄弟表示法的特点缺点：找父结点麻烦，首先找到长子，然后再找父结点。优点：方便找、找兄弟等运算leftChild_cstree(p)p-lchildrightSibling_cstree(p)p-rsiblingroot_cstree(t)tisNull_cstree(t)t=NULL;很容易，先由lchild找到长子，再由找到全部rsibling字段逐个找右兄弟结点63wangzhao树和树林的表示树的树林的表示表示64