二叉树的存储方式有许多种，在数据结构中，习惯用链表来表示和实现二叉树结构，这样在删除或增加节点时，会非常方便且具有弹性。当然也可以使用一维数组这样的连续存储空间来表示二叉树，不过在对树的中间节点进行插入与删除时，可能要大量移动数组中的数据来反映树节点的变动。接下来将介绍数组这种存储方法。

用一维数组来实现二叉树

使用有序的一维数组来表示和实现二叉树，可将此二叉树假想成一棵满二叉树，而且第k层具有2k-1个节点，它们按序存放在这个一维数组中。首先来看使用一维数组建立二叉树的方法（见图6-17）以及索引值的设置（见表6-1）。

从图6-17可以看到此一维数组中的索引值有以下关系：

（1）左子树的索引值是父节点的索引值乘以2。

（2）右子树的索引值是父节点的索引值乘以2加1。

接着来看以一维数组建立二叉树的实例，实际上就是建立一棵二叉搜索树，这是一种很好的排序应用模式，因为在建立二叉树的同时数据就经过了初步的比较判断，并按照二叉树的建立规则来存放数据。二叉查找树具有以下特点：

可以是空集合，若不是空集合，则节点上一定要有一个键值。

每一个树根的键值必须大于左子树的键值。

每一个树根的键值必须小于右子树的键值。

左右子树也是二叉查找树。

树的每个节点的键值都不相同。

现在我们示范用一组数据（32, 25, 16, 35, 27）来建立一棵二叉搜索树，具体过程如图6-18所示。

设计一个Java程序，按序输入一棵二叉树节点的数据（6, 3, 5, 9, 7, 8, 4, 2），并建立一棵满二叉树，最后输出存储此二叉树的一维数组。

【范例程序：ch06_01.java】

01//建立二叉树
02
03import java.io.*;
04public    class ch06_01
05{
06  public static void main(String args[]) throws IOException
07  {
08    int i,level;
09    int data[]={6,3,5,9,7,8,4,2}; /*原始数组*/
10    int btree[]=new int[16];
11    for(i=0;i<16;i++) btree[i]=0;
12    System.out.print("原始数组的内容: \n");
13    for(i=0;i<8;i++)
14    System.out.print("["+data[i]+"] ");
15    System.out.println();
16    for(i=0;i<8;i++)/*把原始数组中的值逐一对比*/
17    {
18      for(level=1;btree[level]!=0;)   /*比较树根及数组内的值*/
19      {
20        if(data[i]>btree[level])       /*如果数组内的值大于树根，则往右子树比较*/
21          level=level*2+1;
22        else/*如果数组内的值小于或等于树根，则往左子树比较*/
23          level=level*2;
24      }   /*如果子树节点的值不为0，则再与数组内的值比较一次*/
25      btree[level]=data[i];           /*把数组值放入二叉树*/
26    }
27    System.out.print("二叉树的内容：\n");
28    for (i=1;i<16;i++)
29    System.out.print("["+btree[i]+"] ");
30    System.out.print("\n");
31  }
}

【执行结果】参见图6-19。

一维数组中存放的值和所建立的二叉树对应的关系如图6-20所示。

通常以数组来存储二叉树，如果越接近满二叉树，则越节省存储空间，如果是歪斜树，则最浪费存储空间。另外，要增删数据比较麻烦，必须重新建立二叉树。

本文节选自《图解数据结构 使用Java(视频教学版)》，内容发布获得作者和出版社授权。