博客

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

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代表二叉树中的一个节点。定义如下：

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<data.length;i++) {
			Add_Node_To_Tree(data[i]);
		}
	}
	//将指定的值加入到二叉树中适当的节点
	void Add_Node_To_Tree(int value) {
		TreeNode currentNode=rootNode;
		if(rootNode==null) {
			rootNode=new TreeNode(value);
			return;
		}
		//建立二叉树
		while(true) {
			if(value<currentNode.value) {//在左子树
				if(currentNode.left_Node==null) {
					currentNode.left_Node=new TreeNode(value);
					return;
				}else currentNode=currentNode.left_Node;
			}else {//在右子树
				if(currentNode.right_Node==null) {
					currentNode.right_Node=new TreeNode(value);
					return;
				}
				else currentNode=currentNode.right_Node;
			}
		}
		
	}
}
public class ch0602 {
	public static void main(String args[]) throws  IOException {
		int ArraySize=10;
		int tempdata;
		int[] content=new int[ArraySize];
		BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in));
		System.out.println("请连续输入"+ArraySize+"个数据");
		for(int i=0;i<ArraySize;i++) {
			System.out.print("输入第"+(i+1)+"个数据：");
			tempdata=Integer.parseInt(keyin.readLine());
			content[i]=tempdata;
		}
		new BinaryTree(content);
		System.out.println("用链表建立二叉树成功！");
	}
	
	
	
}

我们使用链表来表示二叉树的优点时对节点的增加于删除相当容易，缺点是很难找到父节点，除非在每一节点多增加一个父字段。