树 - 二叉树 - 二叉树的存储结构（二）
链式存储结构
结点的结构
二叉树的每个结点最多有两个孩子 用链接方式存储二叉树时 每个结点除了存储结点本身的数据外 还应设置两个指针域
lchild和rchild 分别指向该结点的左孩子和右孩子 结点的结构为
结点的类型说明
typedef char DataType; //用户可根据具体应用定义DataType的实际类型
typedef struct node{
DataType data;
Struct node *lchild *rchild; //左右孩子指针
}BinTNode; //结点类型
typedef BinTNode *BinTree;//BinTree为指向BinTNode类型结点的指针类型
二叉链表(二叉树的常用链式存储结构)
在一棵二叉树中 所有类型为BinTNode的结点 再加上一个指向开始结点(即根结点)的BinTree型头指针(即根指针)root 就构
成了二叉树的链式存储结构 并将其称为二叉链表
【例】下面左图所示二叉树的二叉链表如下面中图所示
注意
① 一个二叉链表由根指针root惟一确定 若二叉树为空 则root=NULL;若结点的某个孩子不存在 则相应的指针为空
② 具有n个结点的二叉链表中 共有 n个指针域 其中只有n 个用来指示结点的左 右孩子 其余的n+ 个指针域为空
带双亲指针的二叉链表
经常要在二叉树中寻找某结点的双亲时 可在每个结点上再加一个指向其双亲的指针parent 形成一个带双亲指针的二叉链表
【例】上面右图是上面左图所示的二叉树的带双亲指针的二叉链表
注意
二叉树存储方法的选择 主要依赖于所要实施的各种运算的频度
lishixinzhi/Article/program/sjjg/201311/23885
