数组转换成二叉树

前面介绍了双向链表，其实二叉树也相当于一个链表。二叉树相对而言比较好理解，我们可以把其看做成一棵树，只不过每个结点至多只有2个枝节点，且仅且只有一个根结点，这就是二叉树。二叉树的定义其实和链表差不多，双向链表是和其前后结点相连，而二叉树的结点就必须和其左右枝节点保持关系。与链表类似，可以这样定义二叉树：

 

public class TreeNode {
	private Object obj;
	private TreeNode parent;
	private TreeNode left;
	private TreeNode right;
	//重写构造方法
	public TreeNode(Object obj){
		this.obj=obj;
	}
	
	public Object getObj() {
		return obj;
	}
	public void setObj(Object obj) {
		this.obj = obj;
	}
	public TreeNode getParent() {
		return parent;
	}
	public void setParent(TreeNode parent) {
		this.parent = parent;
	}
	public TreeNode getLeft() {
		return left;
	}
	public void setLeft(TreeNode left) {
		this.left = left;
	}
	public TreeNode getRight() {
		return right;
	}
	public void setRight(TreeNode right) {
		this.right = right;
	}
	
}

 

二叉树定义好后，这个时候想把一个int数组转化成二叉树，我们就得定义好建树的规则。没有规则，是很难建树，即使建成了，也未必和我们想的一样。建二叉树就必须先建好根结点，按理说，取数组中最中间的数当作根结点是最好的，当为了重新对数组进行排序，可以简单的取数组的第一个元素当作其根结点。这时根结点建好后，然后依次取数组里面的数，往根结点的左右两端连接，做其枝结点。这个时候为了使建成的树是唯一的，建树的规则为：

当遇到比结点小的数时，这个数成为其左孩子，当遇到不小于比结点数时，成为其右孩子。

先定义一个把一个数插入到二叉树中的方法：

/**
	 * 将一个数插入二叉树中
	 * @param node	在这个结点下插入新的结点
	 * @param value	
	 */
	public void addToTree(TreeNode node, int value){  
		if((Integer)node.getObj()>value){
			//当前结点的值比value大，则成为其左子结点
			if(node.getLeft()!=null){
				//看这个结点的左子结点是否存在，如果存在
				node=node.getLeft();
				//递归调用该方法
				addToTree(node, value); 
			}else{
				//不存在
				TreeNode TNode=new TreeNode(value); 
				TNode.setParent(node);   
                node.setLeft(TNode); 
			}	
		}
		else{
			//当前结点的值比value小，则成为其右子结点
			if (node.getRight() != null) { 
				//看这个结点的右子结点是否存在，如果存在
				node = node.getRight();   
				addToTree(node, value);   
            }else{   
            	//不存在
            	TreeNode TNode=new TreeNode(value);  
            	TNode.setParent(node);   
                node.setRight(TNode);   
            }   
		}
	}

 使用递归，直到这个数插入到二叉树中。一个数既然能插入到树中，那一个数组里面的元素也能插入树中，从而建成一棵二叉树：

/**
	 * 将一个数组转化为一个二叉树
	 * @param array
	 * @return
	 */
	public TreeNode arrayToTree(int [] array){
		if(array.length == 0){   
            throw new RuntimeException("数组长度为0，没有元素用来建树！！！");   
        } 
		//把第一个元素变成根结点
        int first = array[0];   
        root = new TreeNode(first);   
        for (int i = 1; i < array.length; i++) {   
        	addToTree(root, array[i]); 
        }   
		return root;
	}

 随便创建一个整数数组，在主函数里面调用这些方法就可以建成一棵二叉树。

<!--EndFragment-->

<!--EndFragment--><!--EndFragment-->