|
链式存储结构 结点的结构 二叉树的每个结点最多有两个孩子用链接方式存储二叉树时每个结点除了存储结点本身的数据外还应设置两个指针域 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形成一个带双亲指针的二叉链表 【例】上面右图是上面左图所示的二叉树的带双亲指针的二叉链表 注意 二叉树存储方法的选择主要依赖于所要实施的各种运算的频度 |
