数据结构二叉树ppt.ppt

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

2、1个节点，3。非空二叉树n0个叶节点，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 .线索链表期

3、间，在节点结构、辅助链表节点结构中添加两个标志域并规定：其中：LTag=，0 lchild域显示左侧ii 1 lchild域显示节点之前，RTag=，0 rchild域显示节点右侧/Link=0:指针Struct BiThrNode *lchild，* rchild/左和右眼指针PointerThr LTag，RTag/左和右徽标BiThrNode，* BiThrTree，3 .线索二叉树图例、线索二叉树及其存储结构(a)中间顺序线索二叉树(b)中间顺序线索链表、如果右标志为“1”，则组合中间顺序线索树，右链为线索，右链直接指示节点的后面。如果右侧标志为“0”，则右侧链为指针，然后是右侧子树最

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

5、树为空节点while(p-rtag=thread/io traver _ t，6.4.2树系和由于二叉树和树都可以使用二进制链表作为存储结构，因此树和二叉树之间的对应关系，树将转换为二叉树方法。1)从左到右对齐每个孩子。2)在兄弟之间添加连接。3)对于每个节点，删除与其他孩子的连接(左侧孩子除外)。4)旋转根节点，将整个树顺时针旋转45。2 .森林和二叉树之间的对应关系从树的二次链表表示的定义中可以看出，树对应的二叉树中，至少有一个右边的子树应该是空的。如果将森林中第二棵树的根节点视为第一棵树根节点的同级，则还可以导出森林和二叉树之间的对应关系。已知条件：森林和二叉树之间的对应设置森林F=(T

6、1，T2，Tn)；T1=(根，t11，t12，t1m)；二叉树b=(lbt，节点(根)，rbt)；森林中的二叉树转换规则为B=(如果： F=)；否则，从根(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。树的表示及