数据结构30-二叉树的存储结构

《数据结构30-二叉树的存储结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构第三十课二叉树的存储结构第二十三课二叉树的存储结构本课主题：二叉树的存储结构教学目的：掌握二叉树的两种存储结构教学重点：链式存储结构教学难点：链式存储二叉树的基本操作授课内容：复习二叉树的定义二叉树的基本特征：每个结点的度不大于２。一、二叉树的顺序存储结构#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;二叉树按顺序结构存储必须按完全二叉树形式，这样，会浪费空间。例如，在最坏情况下，n个结点的单枝树，要占用2n-1个元素的存

2、储空间。二、二叉树的二叉链表存储结构一个二叉树的结点至少保存三种信息：数据元素、左孩子位置、右孩子位置对应地，链式存储二叉树的结点至少包含三个域：数据域、左、右指针域。二叉链表的存储方式typedefstructBiTNode{TElemTypedata;structBitNode*lchild,*rchild;}BiTNode,*BiTree;注意，n个结点的二叉树有n+1个空链域。基于该存储结构的二叉树基本操作有：二叉链表二叉树基本操作(1)StatusCreteBiTree(BiTree&T);//按先序次序输入二叉树中

3、结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链表存储结构,Visit是对结点操作的应用函数//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次//一旦visit()失败,则操作失败二叉树基本操作(2)StatusLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链表存储结构,Visit是对结点操作的应

4、用函数//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次//一旦visit()失败,则操作失败StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链表存储结构,Visit是对结点操作的应用函数//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次//一旦visit()失败,则操作失败二叉树基本操作(3)StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链

5、表存储结构,Visit是对结点操作的应用函数//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次//一旦visit()失败,则操作失败二、二叉树的三叉链表存储结构在二叉链表表示的二叉树中，找结点的左右子女比较方便，但找其双亲就不方便了，如果在结点中再增加一个指向其双亲结点的域，就可以方便的查找其双亲了，这就是三叉链表。三叉链表可形式定义如下：typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild,*parent;}BiTNode,*Bitree;也

6、可以在结点中加上指向父结点的指针域P。四、总结本课内容顺序存储与链式存储的优缺点。回目录上一课下一课