【摘要】：与线性链表类似，用于存储二叉树中各元素的存储节点也由两部分组成：数据域与指针域。如图2-33所示为二叉树存储节点的示意图。由于二叉树的存储结构中每一个存储节点有两个指针域。因此，二叉树的链式存储结构也称为二叉链表。如图2-34、、所示分别表示了一棵二叉树、二叉链表的逻辑状态、二叉链表的物理状态。其中BT称为二叉链表的头指针，用于指向二叉树根节点。
2.6.3 二叉树的存储结构
在计算机中，二叉树通常采用链式存储结构。
与线性链表类似，用于存储二叉树中各元素的存储节点也由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后件（即两个子节点）。因此，用于存储二叉树的存储节点的指针域有两个：一个用于指向该节点的左子节点的存储地址，称为左指针域；另一个用于指向该节点的右子节点的存储地址，称为右指针域。如图2-33所示为二叉树存储节点的示意图。其中：L（i）为节点i的左指针域，即L（i）为节点i的左子节点的存储地址；R（i）为节点i的右指针域，即R（i）为节点i的右子节点的存储地址；V（i）为数据域。
图2-33 二叉树存储节点的结构
由于二叉树的存储结构中每一个存储节点有两个指针域。因此，二叉树的链式存储结构也称为二叉链表。如图2-34(a)、(b)、(c)所示分别表示了一棵二叉树、二叉链表的逻辑状态、二叉链表的物理状态。其中BT称为二叉链表的头指针，用于指向二叉树根节点（即存放二叉树根节点的存储地址）。如下图所示：
图2-34 二叉树的链式存储结构
图2-34 二叉树的链式存储结构
对于满二叉树与完全二叉树来说，根据完全二叉树的性质2，可以按层序进行顺序存储，这样，不仅节省了存储空间，又能方便地确定每一个节点的父节点与左右子节点的位置，但顺序存储结构对于一般的二叉树不适用。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
