C#虚拟二叉树图形化程序设计(4)
一个深度为K的二叉树需要 个存储空间，当K值很大并且二叉树的空结点很时，最坏的情况是每层只有一个结点，使用顺序存储结构来存储显然会造成极大的浪费，这时就应该使用链式存储结构来存储二叉树中的数据。
0 1 2 3 4 5 6
（a） 满二叉树
0 1 2 6
（b） 一般二叉树
图1.3 二叉树的顺序存储
（2）链式存储结构：二叉树的链式存储结构可分为二叉链表和三叉链表。二叉链表中，每个结点除了存储本身的数据外，还应该设置两个指针域left和right，分别指向其左孩子和右孩子（如图1.4（a）所示）。
如果在二叉树中经常需要寻找某结点的双亲，每个结点还可以加一个指向双亲的指针域parent，如图1.4（b）所示，这就是三叉链表。
（a） 二叉链表节点指针域 （b） 三叉链表结点指针域
left data right
left data parent right
图1.4 二叉树链式存储的结点指针域
二叉树还有一种叫双亲链表的存储结构，它只存储结点的双亲信息而不存储孩子信息，由于二叉树是一种有序树，一个结点的两个孩子有左右之分，因此结点中除了存放双亲信息外，还必须指明这个结点是左孩子还是右孩子。由于结点不存放孩子信息，无法通过头指针出发遍历所有结点，因此需要借助数组来存放结点信息。双亲链表中的元素存放的顺序是根据结点的顺序来决定的，也就是说把各个元素的存放位置进行调换不会影响结点的逻辑结构。其在物理上是一种顺序存储结构，这样的链表为静态链表。
二叉树存在多种存储结构，选用何种方法进行存储主要依赖于对二叉树进行什么操作。而二叉链表是二叉树最常用的存储结构。