一个二叉树构建相关的问题分析

问题描述：

    假设我们有一组排序的元素，希望通过他们来构建一棵平衡的二叉搜索树。那么该如何构建呢？

 

分析

    这是一个比较有意思的问题。通过一些递归的手法可以做很好的实现。我们首先来看，如果要构建一棵平衡二叉树的话，我们理想的情况是相对于一个树的节点来说，它的两个子树的元素是一样多的。这样就从本质上保证他们可以达到平衡。

    那么，如果我们现在从定义的角度更加深入一下考虑的话，假定我们要构造一棵树。那么它的根节点就应该取元素列表的中间元素，这样保证两边平衡。在构造了这个节点之后，那么它的左右子节点呢？对于它的左子节点，按照递归的定义，则应该是在元素列表开头到这个节点之间再取中间值，然后返回。这样保证每次返回的节点都是当前剩余部分的中间节点。对于右边的子节点也同样类似。

    这样，我们就得到了一个大致的思路:

1. 取元素列表的中间元素，作为当前节点。

2. 取元素列表开头到中间元素的中间节点，作为左子节点。

3. 取中间节点到列表结尾的元素的中间节点，作为右子节点。

4. 将当前节点和左右子节点关联起来。

5. 返回当前节点。

     有了这些讨论，我们可以得到下面的代码：

public Node buildFromSorted(int[] list, int lo, int hi)
{
	if(hi < lo) return null;
		
	int mid = lo + (hi - lo) / 2;	
	Node middle = new Node(list[mid], null);
		
	Node left = null;
	if(lo < mid)
		left = buildFromSorted(list, lo, mid - 1);
		
	middle.left = left;
	if(left != null)
		left.parent = middle;
		
	Node right = null;
	if(mid < hi)
		right = buildFromSorted(list, mid + 1, hi);
		
	middle.right = right;
	if(right != null)
		right.parent = middle;
		
	return middle;
}

     这里，递归最巧妙的地方在于每次我返回的是一个节点。和二叉搜索树里面实现增加删除元素的递归方法思路一样。值得细细体会。

    和代码配套的节点定义如下：

class Node
{
	int data;
	Node left = null;
	Node right = null;
	Node parent;
		
	Node(int data, Node parent)
	{
		this.data = data;
		this.parent = parent;
	}
}

     这里故意增加了一个指向父节点的引用。只是让实现里面多了两行代码。

     详细的实现可以见附件里。

总结

    这个问题本身并不复杂，主要是对递归思想的运用要考虑清楚。而且，和二叉搜索有点类似的地方是要注意取中间值时这一段元素开头和结尾的位置关系。在TreeMap的源代码实现里有一个基于迭代器的构造实现，也可以作为一个参考。