数据结构与算法分析第四章 树

第四章树物理与电子学院-数据结构21.树2.二叉树3.二叉查找树4.平衡二叉查找树（AVL树）5.伸展树6.B树物理与电子学院-数据结构31.树数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根root的子树。数据操作物理与电子学院-数据结构41.树结点的度：该结点的子树数目树的度：树中各结点度数的最大值边（树枝）：路径：叶子（树叶）、分支节点：父、儿子、兄弟结点：祖先结点：从根结点到该结点的路径上所有结点深度：根为0,依次往下数高：树叶的高为0有序树：所有结点的儿子结点具有确定次序，否则为无序树森林：m=0棵互不相交树的集合ABCDEFGHIL树：(A(B(L,E),C(F),D(G(I),H))BCDEFGHIL森林：m=3物理与电子学院-数据结构51.树数据域第1个儿子指针第2个儿子指针…………第K个儿子指针父亲结点指针•广义标准形式：在标准形式的基础上，再增加指向父亲结点的指针域。ABCDEFGHILA123-1B45-10C6-1-10D78-10L-1-1-11E-1-1-11F-1-1-12G9-1-13H-1-1-13I-1-1-170123456789-1表示空缺点：空指针域太多，多达(K-1)×n+1个。改进：结点中设立度数域，指针域依度数定。但操作麻烦。采用左儿子、兄弟表示法。用数组表示左图的树度数K＝3的树标准形式：物理与电子学院-数据结构61.树左儿子-兄弟表示法：数据域第一棵子树根结点的地址下一个亲兄弟结点的地址ABCDEFGHILA∧BCD∧∧E∧∧F∧G∧H∧∧L∧I∧度数K＝3的树物理与电子学院-数据结构71.树树的遍历（访问树中的每一个节点）找出目录usr包含的所有目录和文件？先序遍历输出形式是目录表物理与电子学院-数据结构81.树树的遍历计算目录usr的大小？后序遍历输出是计算目录大小的顺序物理与电子学院-数据结构91.树森林的遍历前序遍历类似于树的前序遍历。增加一个虚拟的根结点，它的儿子为各棵树的根。那么对这棵树进行前序遍历，即得到森林的前序序列（不含树根结点）中序遍历类似于树的后序遍历。增加一个虚拟的根结点，它的儿子为各棵树的根。那么对这棵树进行后序遍历，即得到森林的中序遍历（去掉树根结点）前序：B、L、E、C、F、D、G、I、H中序：L、E、B、F、C、I、G、H、DBCDEFGHILABCDEFGHIL物理与电子学院-数据结构102.二叉树定义：一棵树，每个节点不多于两个儿子，且位置有序。BCDEFL例：二叉树例：结点总数为3时的所有二叉树的树的形状物理与电子学院-数据结构112.二叉树二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点证：k=1时成立，设k=i-1时成立则当k=i时在二叉树的第i层上至多有2i-1-1*2=2i-1个结点BCDEFLA1层：结点个数21-1=20个2层：结点个数22-1=21个3层：结点个数23-1=22个物理与电子学院-数据结构122.二叉树证：利用性质1，将第1层至第k层的最多的结点数进行相加：1+2+22+………+2k-2+2k-1+2k=2k+1-1性质2：高度为k的二叉树至多有2k+1-1个结点物理与电子学院-数据结构132.二叉树性质3：二叉树的叶子结点数n0等于度为2的结点数n2+1证：设度为1的结点数为n1，树枝的总数为B则：B=n-1=n0+n1+n2-1;又B=n1+2×n2;原命题得证。CEFLA物理与电子学院-数据结构142.二叉树BCDEFLAPSQRXUWV满二叉树:每层结点数最多BCDEFLAPSQRU完全二叉树:从满二叉树最底层从右向左依次去掉若干结点性质4：具有n个结点的完全二叉树高度为log2n证：根据性质2和完全二叉树的定义：设其高度为k2k-1n=2k+1-1；2kn+1=2k+1；2k=n2k+1故：k=log2nk+1;原命题得证。物理与电子学院-数据结构152.二叉树性质5：对一棵有n个结点的完全二叉树按照从第一层（根所在的层次〕到最后一层，并且每一层都按照从左到右的次序进行编号。根结点的编号为1，最后一个结点的编号为n。1：对任何一个编号为i的结点而言，它的左儿子的编号为2i(若2i=n),而右儿子的编号为2i+1(若2i+1=n)。2：对任何一个编号为j的结点而言，它的父亲结点的的编号为j/2。根结点无父结点。证：对编号归纳BCDEFLAPSQRU121110987654321物理与电子学院-数据结构162.二叉树二叉树的顺序存储ABCDEFGHILA1-1B92C53D6-1E-1-1F-1-1G87H-1-1I-1-1L-140123456789rightleftdata应用范围：适用于二叉树上的结点个数已知，或不支持动态存储分配的高级语言。物理与电子学院-数据结构172.二叉树完全二叉树A23B45C67D89E100F00G00H00I00L00012345678910leftdata应用范围：适用于完全二叉树，且结点个数已知。DCGEFBAHILright物理与电子学院-数据结构182.二叉树二叉树的链接存储ABCDEFGHILdataleftright标准形式：（二叉链表）广义标准形式：（三叉链表）dataleftrightParent物理与电子学院-数据结构192.二叉树例子A∧B/\∧∧∧∧∧∧CDEFGGFDCBAE物理与电子学院-数据结构202.二叉树设N代表根节点，L代表左子树，R代表右子树。a.前序（或先序）：如果二叉树为空，则操作为空：否则访问根结点；前序遍历左子树；前序遍历右子树。记为：NLR。b.中序：如果二叉树为空，则操作为空：否则中序遍历左子树；访问根结点；中序遍历右子树。记为：LNR。c.后序：如果二叉树为空，则操作为空：否则后序遍历左子树；后序遍历右子树；访问根结点。记为：LRN。前序：A、L、B、E、C、D、W、X中序：B、L、E、A、C、W、X、D后序：B、E、L、X、W、D、C、ABCDELAXW二叉树遍历BCDELAXW首次遇到第2次遇到末次遇到物理与电子学院-数据结构212.二叉树BCDELAXW前序：A、L、B、E、C、D、W、X中序：B、L、E、A、C、W、X、D后序：B、E、L、X、W、D、C、ABCDELAXWBLEACWXD物理与电子学院-数据结构222.二叉树表达式树树叶是操作数，分支节点是操作符前序：++a*bc*+*defg中序：(a+(b*c))+(((d*e)+f)*g)后序：abc*+de*f+g*+前缀表达式中缀表达式后缀表达式物理与电子学院-数据结构232.二叉树构造表达式树由后缀表达式构造见P71end6物理与电子学院-数据结构243.二叉查找树定义:空或有一个根，根的左子树若非空，则左子树上的所有结点的关键字值均小于根结点的值。根的右子树若非空，则右子树上的所有结点的关键字值均大于根结点的值。根结点的左右子树同样是二叉查找树。LNPEMCY12225030011020099105230216物理与电子学院-数据结构253.二叉查找树ADT物理与电子学院-数据结构263.二叉查找树MakeEmptyFindFindMin,FindMax12225030011020099105230216物理与电子学院-数据结构273.二叉查找树插入将数的序列：122、99、250、110、300、280依次插入一个空二叉查找树1222503001102809912212299122250991222501109912225030011099先查找，判断为空，再插入物理与电子学院-数据结构283.二叉查找树插入物理与电子学院-数据结构293.二叉查找树删除1.叶子节点直接删除15607030205060302050物理与电子学院-数据结构303.二叉查找树删除2.分支节点（只有一个儿子）12225030011020099105230216400450500被删结点122250300200230216400450500110105删除9912225030011020099105330316400450500被删结点122250300230216400450500删除33011099105316父节点绕过被删节点即可物理与电子学院-数据结构313.二叉查找树删除2.分支节点（有两个儿子）12225030011020099105330316400450500被删结点替身替身1102503001052009933031640045050020025030011099105400450500330316选取“替身”取代被删结点，左子树中最大结点或右子树中最小结点物理与电子学院-数据结构323.二叉查找树删除懒惰删除物理与电子学院-数据结构333.二叉查找树平均情形分析：D(N)表示内部路径长所有节点的深度和树的所有节点的平均深度为O(logN)1)1()()(NiNDiDND物理与电子学院-数据结构344.AVL树起因：提高查找速度，避免最坏情况出现。定义：空树的高度定为-1每个结点的左右子树的高度最多差一的二叉树。DABCFEG149843712+1+1+1-1000物理与电子学院-数据结构354.AVL树插入操作破坏了AVL树的平衡条件0149853712+1+1+1-10010+1+2+2+2+1149853712+1+1-100040-1+2+2+2节点：从插入点到根的路径中第一个平衡特性受到破坏的节点物理与电子学院-数据结构364.AVL树遭到破坏后，节点的高度差必然为+-2节点的高度差为2的四种情况：1.对的左儿子左子树进行插入2.对的左儿子右子树进行插入3.对的右儿子左子树进行插入4.对的右儿子右子树进行插入物理与电子学院-数据结构374.AVL树LL、RR插入使用单旋转P82LR、RL插入使用双旋转P84物理与电子学院-数据结构384.AVL树AVL树ADT物理与电子学院-数据结构394.AVL树插入物理与电子学院-数据结构404.AVL树LL单旋转物理与电子学院-数据结构414.AVL树LR双旋转end7物理与电子学院-数据结构425.伸展树定义：基于伸展操作的二叉查找树摊还时间为O(logN)M次操作的最坏情形运行时间为O(MF(N))，它的摊还时间为O(F(N))节点被访问后，经过伸展操作放到根上物理与电子学院-数据结构435.伸展树伸展操作之字形一字形P92查找删除插入