(9)--第4章 树和二叉树-存储结构.ppt

第5章树和二叉树

二叉树的存储结构

二叉树的顺序存储

实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。

特点：

结点间关系蕴含在其存储位置中

浪费空间，适于存满二叉树和完全二叉树

二叉树的顺序存储

PARENT

LCHILD

RCHILD

二叉树的链式存储

二叉链表

typedefstructBiNode{

TElemTypedata;

structBiNode*lchild,*rchild;//左右孩子指针

}BiNode,*BiTree;

分析：必有2n个链域。除根结点外，每个结点有且仅有一个双亲，所以只会有n－1个结点的链域存放指针，指向非空子女结点。

空指针数目＝2n－(n-1)=n+1

在n个结点的二叉链表中，有个空指针域

练习

n+1

三叉链表

typedefstructTriTNode

{TelemTypedata;

structTriTNode*lchild,*parent,*rchild;

}TriTNode,*TriTree;