二叉树的存储结构入门(java描述)-一一网

【摘要】 1. 顺序存储结构
所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。这样结点在存储位置上的前驱、后继关系并不一定就是它们在逻辑上的邻接关系，然而只有通过一些方法确定某结点在逻辑上的前驱结点和后继结点，这种存储才有意义。因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以…

1. 顺序存储结构

所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。这样结点在存储位置上的前驱、后继关系并不一定就是它们在逻辑上的邻接关系，然而只有通过一些方法确定某结点在逻辑上的前驱结点和后继结点，这种存储才有意义。因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

图5.6给出的是图5.5（a）所示的完全二叉树的顺序存储示意。
在这里插入图片描述

在这里插入图片描述
对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。

图5.7给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。最坏的情况是右单支树，如图5.8所示，一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。
在这里插入图片描述

完全二叉树的顺序存储表示可描述为：

class BinaryTree<T>
{
	private int maxSize;
	private T[] datas; public int length; //结点总数
}

  
 
  1
  2
  3
  4
  5
  6

链式存储结构

所谓二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常有下面两种形式。

（1）二叉链表存储

链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储结构为：
在这里插入图片描述
其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或null表示）。

二叉树链式存储的每个结点可描述为：

class Node<T> { public Node<T> lChild; //左孩子 public T data; //数据域 public Node<T> rChild; //右孩子 //构造函数,创建一个空结点 public Node() { data = null; lChild = null; rChild = null; } public Node(T x) {//重载构造函数,创建一个数值为x的结点 data = x; lChild = null; rChild = null; }
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

二叉链表也可以带头结点的方式存放
在这里插入图片描述
在Java中描述二叉链表的关键是确定二叉树的根，代码如下。

class BinaryTree<T> { public Node<T> root;// 根结点 public BinaryTree() {//创建一个空二叉树 this.root = new Node<T>(); } public BinaryTree(T x) {//创建一棵以数据元素x为根结点的二叉树 this.root = new Node<T>(x); } //...
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

(2)三叉链表存储

\每个结点由四个域组成，具体结构为：
在这里插入图片描述
其中，data、lchild以及rchild三个域的意义同二叉链表结构，parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点，但是，相对于二叉链表存储结构而言，它增加了空间开销。
图5.10给出了图5.5（b）所示的一棵二叉树的三叉链表表示。
在这里插入图片描述
尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。