二叉树链式存储结构.pdf

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