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

《数据结构与算法分析第四章 树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章树11.树2.二叉树3.二叉查找树4.平衡二叉查找树（AVL树）5.伸展树6.B树2物理与电子学院-数据结构1.树数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根root的子树。数据操作3物理与电子学院-数据结构1.树结点的度：该结点的子树数目树的度：树中各结点度数的最大值边（树枝）：路径：叶子（树叶）

2、、分支节点：父、儿子、兄弟结点：祖先结点：从根结点到该结点的路径上所有结点深度：根为0,依次往下数高：树叶的高为0有序树：所有结点的儿子结点具有确定次序，否则为无序树森林：m>=0棵互不相交树的集合ABCDEFGHIL树：(A(B(L,E),C(F),D(G(I),H))BCDEFGHIL森林：m=34物理与电子学院-数据结构1.树数据域第1个儿子指针第2个儿子指针…………第K个儿子指针父亲结点指针广义标准形式：在标准形式的基础上，再增加指向父亲结点的指针域。ABCDEFGHILA123-1B45-10C6-1-10D78-

3、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的树标准形式：5物理与电子学院-数据结构1.树左儿子-兄弟表示法：数据域第一棵子树根结点的地址下一个亲兄弟结点的地址ABCDEFGHILA∧BCD∧∧E∧∧F∧G∧H∧∧L∧I∧度数K＝3的树6物理与电子学院-数据结构1.树树的遍历（访问树中的每一个节

4、点）找出目录usr包含的所有目录和文件？先序遍历输出形式是目录表7物理与电子学院-数据结构1.树树的遍历计算目录usr的大小？后序遍历输出是计算目录大小的顺序8物理与电子学院-数据结构1.树森林的遍历前序遍历类似于树的前序遍历。增加一个虚拟的根结点，它的儿子为各棵树的根。那么对这棵树进行前序遍历，即得到森林的前序序列（不含树根结点）中序遍历类似于树的后序遍历。增加一个虚拟的根结点，它的儿子为各棵树的根。那么对这棵树进行后序遍历，即得到森林的中序遍历（去掉树根结点）前序：B、L、E、C、F、D、G、I、H中序：L、E、B、F、

5、C、I、G、H、DBCDEFGHILABCDEFGHIL9物理与电子学院-数据结构2.二叉树定义：一棵树，每个节点不多于两个儿子，且位置有序。BCDEFL例：二叉树例：结点总数为3时的所有二叉树的树的形状10物理与电子学院-数据结构2.二叉树二叉树的性质性质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个11物理与电子学院-数

6、据结构2.二叉树证：利用性质1，将第1层至第k层的最多的结点数进行相加：1+2+22+………+2k-2+2k-1+2k=2k+1-1性质2：高度为k的二叉树至多有2k+1-1个结点12物理与电子学院-数据结构2.二叉树性质3：二叉树的叶子结点数n0等于度为2的结点数n2+1证：设度为1的结点数为n1，树枝的总数为B则：B=n-1=n0+n1+n2-1;又B=n1+2×n2;原命题得证。CEFLA13物理与电子学院-数据结构2.二叉树BCDEFLAPSQRXUWV满二叉树:每层结点数最多BCDEFLAPSQRU完全二叉树:从满

7、二叉树最底层从右向左依次去掉若干结点性质4：具有n个结点的完全二叉树高度为log2n证：根据性质2和完全二叉树的定义：设其高度为k2k-1

8、号为2i+1(若2i+1<=n)。2：对任何一个编号为j的结点而言，它的父亲结点的的编号为j/2。根结点无父结点。证：对编号归纳BCDEFLAPSQRU12111098765432115物理与电子学院-数据结构2.二叉树二叉树的顺序存储ABCDEFGHILA1-1B92C53D6-1E-1