Java实现二叉树的存储

二叉树的存储方式很多，在数据结构中，我们习惯用链表来表示二叉树，这样在删除或者增加节点时，会非常方便且具有弹性。当然，也可以使用一维数组这样的连续存储空间来表示二叉树，不过在对树的中间节点进行插入于删除操作时，可能要大量移动数组中节点的存储位置来反应树节点的变动。我们将分别来介绍数组和链表这两种存储方式。

package Tree;
import java.io.*;
public class ch0601 {
	public static void main(String args[]) {
		int i,level;
		int data[]= {6,3,5,9,7,8,4,2};
		int btree[]=new int[16];
		for(i=0;i<16;i++) btree[i]=0;
		System.out.println("原始数组的内容：");
		for(i=0;i<8;i++)
			System.out.print(data[i]+" ");
		System.out.println();
		for(i=0;i<8;i++) {
			for(level=1;btree[level]!=0;) {
				if(data[i]>btree[level])
					level=level*2+1;
				else
					level=level*2;
			}
			btree[level]=data[i];
		}
		System.out.println("二叉树的内容：");
		for(i=1;i<16;i++)
			System.out.print(btree[i]+" ");
		System.out.println();
	}
}

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

由于二叉树最多只能有两个子节点，就是分支度小于或等于2。而所谓二叉树的链表表示法，就是利用链表来存储二叉树。在Java语言中，我们可以定义TreeNode类和BinaryTree类，其中TreeNode代表二叉树中的一个节点。定义如下：

class TreeNode{
	int value;
	TreeNode left_Node;
	TreeNode right_Node;
	public TreeNode(int value){
		this.value=value;
		this.left_Node=null;
		this.right_Node=null;
		}
}

package Tree;
import java.io.*;
class TreeNode{
	int value;
	TreeNode left_Node;
	TreeNode right_Node;
	public TreeNode(int value) {
		this.value=value;
		this.left_Node=null;
		this.right_Node=null;
	}
}
class BinaryTree{
	public TreeNode rootNode;
	public BinaryTree(int[] data) {
		for(int i=0;i 
我们使用链表来表示二叉树的优点时对节点的增加于删除相当容易，缺点是很难找到父节点，除非在每一节点多增加一个父字段。