5、2_3_二叉树的存储结构_20200905124531.pdf

《5、2_3_二叉树的存储结构_20200905124531.pdf》由会员分享，可在线阅读，更多相关《5、2_3_二叉树的存储结构_20200905124531.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020/3/7王道考研/1本节内容二叉树存储结构王道考研/CSKAOYAN.COM2王道考研/CSKAOYAN.COM知识总览知识总览32020/3/7王道考研/2王道考研/CSKAOYAN.COM二叉树的顺序存储二叉树的顺序存储124376581110913121514123456789101112定义一个长度为 MaxSize 的数组 t ，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点t0t1t2可以让第一个位置空缺，保证数组下标和结点编号一致初始化时所有结点标记为空4王道考研/CSKAOYAN.COM二叉树的顺序存储二叉树的顺序存储12437658111091312151

2、4123456789101112几个重要常考的基本操作：i 的左孩子i 的右孩子i 的父节点i 所在的层次2i2i+1 /2 log2(n + 1)或log2n+ 12i n ?2i+1 n ?i /2 ?若完全二叉树中共有n个结点，则判断 i 是否有左孩子？判断 i 是否有右孩子？判断 i 是否是叶子/分支结点？t0t1t252020/3/7王道考研/3王道考研/CSKAOYAN.COM二叉树的顺序存储二叉树的顺序存储1236547812345678如果不是完全二叉树，依然按层序将各节点顺序存储，那么i 的左孩子i 的右孩子i 的父节点2i2i+1 /2无法从结点编号反映出结点间的逻辑关系t

3、0t1t26王道考研/CSKAOYAN.COM二叉树的顺序存储二叉树的顺序存储i 的左孩子i 的右孩子i 的父节点2i2i+1 /2二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来1243765811109131215141235671112t0t1t22i n ?2i+1 n ?i /2 ?若非完全二叉树中共有n个结点，则判断 i 是否有左孩子？判断 i 是否有右孩子？判断 i 是否是叶子/分支结点？72020/3/7王道考研/4王道考研/CSKAOYAN.COM二叉树的顺序存储二叉树的顺序存储12437658111091312151413715t0t1t2i 的左孩子i 的

4、右孩子i 的父节点2i2i+1 /2二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来最坏情况：高度为 h 且只有 h 个结点的单支树（所有结点只有右孩子），也至少需要2h-1个存储单元结论：二叉树的顺序存储结构，只适合存储完全二叉树8王道考研/CSKAOYAN.COM二叉树的链式存储二叉树的链式存储1243765811109131215141241136127n个结点的二叉链表共有 n+1 个空链域可以用于构造线索二叉树92020/3/7王道考研/5王道考研/CSKAOYAN.COM二叉树的链式存储二叉树的链式存储1241136127root10王道考研/CSKAOYAN.CO

5、M二叉树的链式存储二叉树的链式存储1241136127root如何找到指定结点 p 的父结点？只能从根开始遍历寻找找到指定结点 p 的左/右孩子超简单三叉链表方便找父结点Tips：根据实际需求决定要不要加父结点指针p112020/3/7王道考研/6王道考研/CSKAOYAN.COM知识回顾与重要考点知识回顾与重要考点i 的左孩子i 的右孩子i 的父节点2i2i+1 /2二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来最坏情况：高度为 h 且只有 h 个结点的单支树（所有结点只有右孩子），也至少需要2h-1个存储单元结论：二叉树的顺序存储结构，只适合存储完全二叉树/2i22i+1i+12+22i+3思考：如果结点从0开始编号，该怎么算12王道考研/CSKAOYAN.COM知识回顾与重要考点知识回顾与重要考点1241136127n个结点的二叉链表共有 n+1 个空链域13