数据结构课件：树和二叉树的物理实现.ppt

1、树和二叉树树和二叉树数据结构与算法1树的（物理）存储结构2内容父指针表示法父指针表示法 树的实现树的实现 K叉树叉树 树的顺序表示法树的顺序表示法3父指针表示法4内容 父指针表示法父指针表示法树的实现树的实现v子结点表表示法子结点表表示法v左子结点左子结点/右兄弟结点表示法右兄弟结点表示法v动态结点表示法动态结点表示法v动态左子结点动态左子结点/右兄弟结点表示法右兄弟结点表示法 K叉树叉树 树的顺序表示法树的顺序表示法5子结点表表示法Lists of Children 6左子结点/右兄弟结点表示法 (1)7左子结点/右兄弟结点表示法(2)8内容 树的定义与术语树的定义与术语 父指针表示法父指针

2、表示法树的实现树的实现v子结点表表示法子结点表表示法v左子结点左子结点/右兄弟结点表示法右兄弟结点表示法v动态结点表示法动态结点表示法v动态左子结点动态左子结点/右兄弟结点表示法右兄弟结点表示法 K叉树叉树 树的顺序表示法树的顺序表示法9Linked Implementations (1)10Linked Implementations (2)11树替换为二叉树左子结点左子结点/右兄弟结点表示法本质上使用二叉右兄弟结点表示法本质上使用二叉树来替换树树来替换树.使用这种方法可以把任意树替换为二叉树使用这种方法可以把任意树替换为二叉树.森林是一个或多个树的集合森林是一个或多个树的集合.12内容 树

3、的定义与术语树的定义与术语 父指针表示法父指针表示法 树的实现树的实现 K叉树叉树树的顺序表示法树的顺序表示法13树的顺序表示法 (1)按照先根周游的顺序访问结点的值按照先根周游的顺序访问结点的值.节省空间，但是只允许顺序查找节省空间，但是只允许顺序查找.必须保留重建树结构的信息必须保留重建树结构的信息.例子例子: 对于二叉树对于二叉树, 使用一个符号来标记使用一个符号来标记null 指针指针.AB/D/CEG/FH/I/ABDCEGFHI树的顺序表示法(2)例子例子: 对于满二叉树对于满二叉树, 标记叶结点或分支结点标记叶结点或分支结点.AB/DCEG/FHI例子例子: 对于树对于树, 标记

4、每个子树的结束标记每个子树的结束.RAC)D)E)BF)ABDCEGFHIRADBCFE要点回顾要点回顾 父指针表示法 树的实现 K叉树 树的顺序表示法16二叉树的（物理）存储结构17内容 二叉树的实现二叉树的实现使用数组实现二叉树使用数组实现二叉树 使用指针实现二叉树使用指针实现二叉树18对于满二叉树和完全二叉树，显然可以将二叉树的数据元素映射到一组连续的存贮单元，反之可以按向量的下标值确定相应数据元素在二叉树中的结点位置。BDEACFGHIA B C D E F G H I123 4 5678 9完全二叉树二叉树的数组实现19但对下列二叉树存于一向量中BDEACFGA B C D EF G

5、123 4 5678 9101112 13 14 15BCADA BC123 4 5678D20显然要浪费大量的存贮单元，此外，若要在二叉树中插入或删除结点时，更为不便。因此，以顺序结构存贮一般的二叉树是不适宜的。通常情况下，采用多重链表结构(对于非满二叉树和非完全二叉树)来作为二叉树的存贮结构。21使用数组来实现完全二叉树 (1)Position012345678910 11Parent-00112233445Left Child1357911-Right Child246810-Left Sibling-1-3-5-7-9-Right Sibling-2-4-6-8- 10-22Paren

6、t(r) = (r-1)/2 当当 0rn 时时 Left child(r) = 2r+1 当当 2r+1n 时时 Right child(r) = 2r+2 当当 2r+2n 时时 Left sibling(r) = r-1 当当r为偶数且为偶数且 0rn 时时 Right sibling(r) = r+1 当当r为奇数且为奇数且 r+1n 时时 使用数组来实现完全二叉树 (2)23二叉树 二叉树的实现二叉树的实现 使用数组实现二叉树使用数组实现二叉树使用指针实现二叉树使用指针实现二叉树24Binary Tree Implementation (1)25Binary Tree Impleme

7、ntation (2)26ADEBCF rootlchild data rchild结点结构结点结构:二叉链表27ADEBCF root 三叉链表parent lchild data rchild结点结构结点结构:280123456 data parent结点结构结点结构:双亲链表LRTagLRRRL29空间代价Space Overhead (1)根据满二叉树定理根据满二叉树定理: 一半的指针是空指针一半的指针是空指针.如果叶子只存储数据如果叶子只存储数据,那么额外开销依赖于树那么额外开销依赖于树是否是满的是否是满的.例例: 所有的结点采用带有两个指向子结点的指针的所有的结点采用带有两个指向子

8、结点的指针的相同的结构相同的结构: 全部的空间需求是全部的空间需求是 (2p + d)n 额外开销额外开销: 2pn If p = d, this means 2p/(2p + d) = 2/3 overhead.30Space Overhead (2)在满二叉树中，去掉叶结点中的指针会省下大量空在满二叉树中，去掉叶结点中的指针会省下大量空间间: n/2(2p) p n/2(2p) + dn p + d如果如果 p = d,结构性开销将达到全部空间的一半结构性开销将达到全部空间的一半.2p/(2p + d) if data only at leaves 2/3 overhead.注意一些方法需

9、要区分叶结点和分支结点注意一些方法需要区分叶结点和分支结点.=31空间开销空间开销有n个结点的满二叉树每个结点都存储两个子结点指针和一个数据去掉叶结点中的指针只有叶结点存储数据(分支结点的数据区没有使用)分支结点只存储指针, 叶结点只存储数据总共需要空间2pn+dn2pn/2+dn2pn/2+dn2pn/2+dn/2结构性开销在全部开销中所占比例若p=d=2/3=1/2=3/4=2/3dppdnpnpn2222dppdnpnpn)2(2)2(2dpdpdnpndnpn222)2(22)2(2dppdnpnpn222)2(2)2(2要点回顾要点回顾 使用指针实现二叉树 使用数组实现二叉树 树型结构是一种动态的，非线性的，可描述结构层次特性的数据结构,如何物理存数（二叉）树是非常重要的！ 二叉树的性质是很重要的33课后思考课后思考 通过对二叉树存储结构的学习，请思考如何把实际问题中的具有树型关系的数据存储到物理存储结构（内存）中？ 模拟可能的实际树型关系的数据（如何表示），并设计方法如何用某种选定的树型物理存储结构来存储。请邮件告诉我（）34二叉树的遍历。 课后预习课后预习35