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

单击此处编辑母版标题样式,*,数 据 结 构,第三十课 二叉树的存储结构,第二十三课 二叉树的存储结构,本课主题：,二叉树的存储结构,教学目的：,掌握二叉树的两种存储结构,教学重点：,链式存储结构,教学难点：,链式存储二叉树的基本操作,授课内容：,复习,二叉树的定义,二叉树的基本特征：每个结点的度不大于。,一、二叉树的顺序存储结构,#define MAX_TREE_SIZE 100,typedef,TElemType,SqBiTreeMAX_TREE_SIZE,;,SqBiTree,bt,;,二叉树按顺序结构存储必须按完全二叉树形式，这样，,会浪费空间。例如，在最坏情况下，,n,个结点的单枝树，,要占用,2n-1,个元素的存储空间。,二、二叉树的二叉链表存储结构,一个二叉树的结点至少保存三种信息：数据元素、左孩子位置、右孩子位置,对应地，链式存储二叉树,的结点至少包含三个域：,数据域、左、右指针域。,二叉链表的存储方式,typedef,struct,BiTNode,TElemType,data;,struct,BitNode,*,lchild,*,rchild,;,BiTNode,*,BiTree,;,注意，,n,个结点的二叉树有,n+1,个空链域。,基于该存储结构的二叉树基本操作有：,二叉链表,二叉树基本操作,(1),Status,CreteBiTree(BiTree,/,按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树,Status,PreOrderTraverse(BiTree,T,Status,(*,Visit)(TElemType,e);,/,采用二叉链表存储结构,Visit,是对结点操作的应用函数,/,先序遍历二叉树,T,对每个结点调用函数,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,对每个结点调用函数,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,。,四、总结本课内容,顺序存储与链式存储的优缺点。,回目录,上一课,下一课,