《第8周树和二叉树（上）第4讲-二叉树的存储结构.pdf》由会员分享，可在线阅读，更多相关《第8周树和二叉树（上）第4讲-二叉树的存储结构.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、回顾二叉树的回顾二叉树的性质性质4，完全，完全二叉树二叉树节点按层序编号：节点按层序编号： i/2 i 2i2i+1 A BC D EFG HIJK 1 2 4 8 9 1011 56 7 3 151413121110987654321 顺序存储结构（不用下标为顺序存储结构（不用下标为0的元素）的元素） 完 全 二 叉 树 的 顺 序 存 储 结 构 完 全 二 叉 树 的 顺 序 存 储 结 构 ABCDEFGHIJK# A B C D E F 2 5 1 14 3 7 一般的二叉树先用空节点补全成一般的二叉树先用空节点补全成 为完全二叉树，然后对节点编号为完全二叉树，然后对节点编号 非 完
2、 全 二 叉 树 的 顺 序 存 储 结 构 非 完 全 二 叉 树 的 顺 序 存 储 结 构typedef ElemType SqBTreeMaxSize; SqBTree bt=#ABD#C#E#F; ABD#C#E#F 1413121110987654321 用一个数组存储用一个数组存储 对于对于完全二叉树完全二叉树来说，其顺序存储是十分合适的。来说，其顺序存储是十分合适的。 对于对于一般的二叉树一般的二叉树，特别是对于那些单分支节点较多的二叉树来说，特别是对于那些单分支节点较多的二叉树来说 是很不合适的，因为可能只有少数存储单元被利用，特别是对退化是很不合适的，因为可能只有少数存储单
3、元被利用，特别是对退化 的二叉树（即每个分支节点都是单分支的），空间浪费更是惊人。的二叉树（即每个分支节点都是单分支的），空间浪费更是惊人。 在顺序存储结构中，在顺序存储结构中，找一个节点的双亲和孩子都很容易找一个节点的双亲和孩子都很容易。 二叉树顺序存储结构的特点：二叉树顺序存储结构的特点： i/2 i 2i2i+1 typedef struct node ElemType data; struct node *lchild, *rchild; BTNode; 借鉴借鉴树的孩子链存储树的孩子链存储结构结构 二叉树二叉树的链式存储结构的链式存储结构。 在二叉树在二叉树的的链式存储链式存储中中，
4、节点节点的类型定义如下的类型定义如下: 指向的都是指向的都是二叉树：递归性二叉树：递归性 A BC DE G F A B D G C E F b 二叉链存储二叉链存储结构演示结构演示 二叉链二叉链 二二叉链存储结构的特点：叉链存储结构的特点： 除了指针外，二叉链除了指针外，二叉链比较节省存储空间比较节省存储空间。占用的存储空间与树形。占用的存储空间与树形 没有关系，只与树中节点个数有关。没有关系，只与树中节点个数有关。 在二叉链中，在二叉链中，找一个节点的孩子很容易找一个节点的孩子很容易，但找其双亲不方便。，但找其双亲不方便。 一颗树采用孩子兄弟链存储结构表示一颗树采用孩子兄弟链存储结构表示 二叉链二叉链 A B D G C E F b 在在二叉链中，空指针的个数？二叉链中，空指针的个数？ n个节点个节点 2n个指针域个指针域 分支数为分支数为n- -1 非空指针域有非空指针域有n- -1个个 空指针域个数空指针域个数 = 2n- -(n- -1) = n+1 n=7 空指针域个数空指针域个数=8 本讲完本讲完