数据结构二叉树ppt

1、校长，一，二，三，六系，教务处，科研处，总务处，每个节点(根节点除外)只有一个直接前驱节点。3 .每个节点(包括根节点)可以有多个后续节点。4 .树显示，1 .节点的度：2。树的度：3。叶节点：4。分支节点：5。层次的定义：该节点拥有的子树的数目。树中的最大节点数。图0中的节点，图0中的节点，根节点在第一层，节点(如果有)在第一层，7 .林(林)由： m0棵不相交的树组成的树集合.8 .二进制树的基本形式：(空)，6.2二进制树，2 .两种特殊形式的二叉树，1 .非空二进制树的层i最多包含2i1个节点(i1)。2 .深度为h的非空二叉树最多可以有2h -1个节点。3 .如果非空二叉树中有n0个

2、叶节点，n2度为2的节点，则n0=n2 1，4。具有n个节点的整个二叉树的深度h=log2n 1。二叉树的存储结构2。一般二叉树顺序存储结构，2 .二叉树链存储结构(二次链表)，2 .前一个顺序遍历，3 .中间顺序巡回，4。后序遍历，前序遍历序列3360a，b，d，k，j连续遍历序列3360 d，g，j，k，b，e，i，f，h，c，a，按层次顺序3360a，遍历结果是求节点的线性序列。指向线性序列“前导”和“后续”的指针称为“线索”。包含“线索”的存储结构相应的二叉树称为“线索二叉树”。把二叉树按某种顺序遍历，变成线索二叉树的过程称为“线索化”。2 .2.在双叉链接表的节点结构中添加两个标志域

3、的线索链接表的节点结构。其中：ltag=，0 lchild域表示节点的左侧ii 1 lchild域表示节点的前置任务，rtag=，0 rchild域表示节点/link=0:指针，thread=1:线索threadstruct bithrnode *lchild，* rchild/左和右眼指针pointerthr ltag，rtag/左和右徽标bithrnode，* bithrtree，3 .线索二叉树图例，线索二叉树和存储结构(a)中间顺序线索二叉树(b)中间顺序线索链表，如果右边的标志为 1 ，则组合中间顺序线索树，右边的链是线索，右边的链直接表示节点的后面。如果右侧标志为“0”，则右侧链为

4、指针，然后是右侧子树最左侧的底部节点。如何在线索树中查找节点的前兆？与中间顺序线索树一起，如果左标志为“1”，左链为线索，则直接指示该前置任务。如果左侧标志为“0”，则左侧子树的最右下方节点是前一个节点。线索链接列表的中间顺序遍历算法status iotraver _ t (bith rtree t，status (* visit) (t elemtype e)/t指向标头节点，标头节点的左链lchild指向根节点p=t-lchild；/p根节点while (p！=t) /空树或巡回结束时p=t while(p-ltag=link)p=p-lchild；if(！visit(p-data)ret

5、urn error:/左侧子树为空节点while(p-rtag=thread/io traver _ t，6.4.2树系和树和二叉树之间的对应，将树转换为二叉树方法：1)从左到右排列每个孩子。2)在兄弟之间添加连接。3)对于每个节点，删除与其他孩子的连接(左侧孩子除外)。4)旋转根节点，将整个树顺时针旋转45。2 .森林和二叉树之间的对应关系可以从树的次链表表达的定义中看出。可见，与树对应的二叉树中，至少有一个右边的子树是空的。(约翰f肯尼迪，northern exposure(美国电视剧)，如果将森林中第二棵树的根节点看作第一棵树的根节点的兄弟，那么还可以导出森林和二叉树的对应关系。已知条件

6、：设置森林和二叉树的对应关系林f=(t1，t2，tn)；t1=(根，t11，t12，t1m)；二叉树b=(lbt，节点(根)，rbt)；从森林到二叉树的转换规则为： f=b=；否则，从根(t1)映射节点(根)。lbt对应于(t11，t12，t1m)。rbt对应于(t2，t3，tn)。从二进制树转换为森林的转换规则为： b=f=；否则，获取节点(根)的相应根(t1)。lbt响应(t11、t12、t1m)；除t1根外，森林是通过rbt反应(t2，t3，tn)获得的。t1以外的树林，6.4.3树木和森林的巡回，1 .遍历树：三条搜索路径首先通过根(顺序)。如果树不是空的，则首先访问根节点，然后依次遍

7、历每个子树。遍历后根(顺序):如果树不是空的，则依次遍历每个子树，然后访问根节点。按层次结构遍历：如果结构树不为空，则从上到下从左到右访问结构树中的每个节点。例如，树的第一根横移，获得的第一根顺序为：树的最后根横移，得到的根顺序为：a b e f c d g h i，e f b c g h i d a，2。森林的横移，第一次横移(林中每棵树的第一根横移)1)如果不是林，则2)先遍历林中第一棵树的子树林。3)首先巡回森林(第一棵树除外)剩下的树组成的森林。后巡回(后巡回)林中每棵树的后巡回)1)如果林不空，后巡回(后巡回)林中第一棵树的子树林。2)访问森林中第一棵树的根节点。3)依次巡回森林(第一棵树除外)剩下的树组成的森林。例如：首先遍历森林，获得的顺序如下：后巡回森林，得到的后巡顺序如下：b e f c d g h i，e f b c g h i d，摘要：1。二叉树的线索化2。树的表示及其巡回工作；设置森林和