《数据结构30-二叉树的存储结构》由会员分享，可在线阅读，更多相关《数据结构30-二叉树的存储结构（12页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构,第三十课 二叉树的存储结构,第二十三课 二叉树的存储结构,本课主题： 二叉树的存储结构 教学目的： 掌握二叉树的两种存储结构 教学重点： 链式存储结构 教学难点： 链式存储二叉树的基本操作 授课内容：复习二叉树的定义 二叉树的基本特征：每个结点的度不大于。,一、二叉树的顺序存储结构,#define MAX_TREE_SIZE 100 typedef TElemType SqBiTreeMAX_TREE_SIZE; SqBiTree bt;二叉树按顺序结构存储必须按完全二叉树形式，这样， 会浪费空间。例如，在最坏情况下，n个结点的单枝树， 要占用2n-1个元素的存储空间。,二、二
2、叉树的二叉链表存储结构,一个二叉树的结点至少保存三种信息：数据元素、左孩子位置、右孩子位置 对应地，链式存储二叉树的结点至少包含三个域：数据域、左、右指针域。,二叉链表的存储方式,typedef struct BiTNode TElemType data; struct BitNode *lchild,*rchild; BiTNode,*BiTree;注意，n个结点的二叉树有n+1个空链域。 基于该存储结构的二叉树基本操作有：,二叉链表,二叉树基本操作(1),Status CreteBiTree(BiTree /采用二叉链表存储结构,Visit是对结点操作的应用函数 /先序遍历二叉树T,对每个
3、结点调用函数Visit一次且仅一次 /一旦visit()失败,则操作失败,二叉树基本操作(2),Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e); /采用二叉链表存储结构,Visit是对结点操作的应用函数 /层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次 /一旦visit()失败,则操作失败 Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e); /采用二叉链表存储结构,Visit是对结点操作的应用函数 /中序遍历二叉树T,对每个结点调用函数
4、Visit一次且仅一次 /一旦visit()失败,则操作失败,二叉树基本操作(3),Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e); /采用二叉链表存储结构,Visit是对结点操作的应用函数 /后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次 /一旦visit()失败,则操作失败,二、二叉树的三叉链表存储结构,在二叉链表表示的二叉树中，找结点的左右子女比较方 便，但找其双亲就不方便了，如果在结点中再增加一个 指向其双亲结点的域，就可以方便的查找其双亲了，这 就是三叉链表。三叉链表可形式定义如下：typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild,*parent; BiTNode ,*Bitree;,也可以在结点中加上指向父结点的指针域P。,四、总结本课内容,顺序存储与链式存储的优缺点。回目录 上一课 下一课,
