二叉树分析之一：定义和遍历讨论

简介

    二叉树相关的问题和内容一直是一个比较有意思的方面。尤其是结合一些特殊的特性，比如搜索、遍历、高度等，更加让这些问题比想象的复杂。因此，对这些问题的分析也就很有必要。这里先对一些基本定义和操作做一个分析，后续会对一些其他常见的问题进行讨论。对于其中讨论的定义和方法，我们会尽力给出一个比较完备的实现。

二叉树定义

    从字面上来理解二叉树，则比较简单，它主要是由一系列的节点组成。每个节点包含有两个分别指向左右子节点的引用。它有一个唯一的节点，称为根节点，在最上面。它的左右引用分别指向同样类型的节点。通过这样递归的定义，我们可以得到一棵二叉树。最常见的二叉树节点如下图：

    它包含有3个部分，一个数据部分，保存节点的数据内容。两个引用，分别指向左边和右边的子节点。

通过这种形式定义的二叉树则如下图所示：

    从图中我们可以看出，这种二叉树的数据结构定义我们可以将它定义成两个部分，一个是节点(BinaryNode)，还有一个就是二叉树（BinaryTree）。

下面是一个相对比较通用一点的节点定义：

class BinaryNode<T>
{
	T element;
	BinaryNode<T> left;
	BinaryNode<T> right;

	BinaryNode(T element)
	{
		this.element = element;
		left = right = null;
	}
}

    这里，我们将节点定义成一个单独的类。在实际实现的时候，我们也可以根据需要将其定义成一个内部类。这主要取决于我们需要使用节点的范围。

    有了节点之后，我们要定义一棵二叉树就很简单了，我们需要的是一个指向BinaryNode的节点，作为树的根节点：

 

public class BinaryTree<T>
{
    private BinaryNode<T> root;

    public BinaryTree()
    { root = null; }

    //...
}

    这里是对树的一个简略的定义，具体的方法这里先省略。

    在有的情况下，我们需要引入一个指向父节点的引用。那么在这种情况下，节点的形式就变换成如下的样子：

    对应的二叉树则转变成如下：

 

    这部分带来的变动在节点和树的定义上影响比较小，加入了父节点会在后续的插入元素和删除元素的时候影响比较大。这里，节点对应的定义代码为：

class BinaryNode<T>
{
	T element;
	BinaryNode<T> left;
	BinaryNode<T> right;
	BinaryNode<T> parent;

	BinaryNode(T element)
	{
		this.element = element;
		left = right = parent = null;
	}
}

遍历方法

    前面对于树的定义部分讲了很多，其本身的定义其实很简单。这里重点讨论二叉树的遍历。其中前序、中序和后序遍历的过程可以说本身是递归的。他们的这种本身的递归特性使得具体的实现采用递归的方式非常有效。

前序

    前序遍历指的是从一个树的根节点开始，首先处理当前节点，然后处理该节点的左子节点，再处理它的右子节点。也就是“根节点-左孩子-右孩子”这样的顺序。

递归实现

    递归实现的方法非常简单：

private void preOrderTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		System.out.print(t.element + " ");
		preOrderTraverse(t.left);
		preOrderTraverse(t.right);
	}	
}

    这里，我们按照递归的定义，首先访问当前节点，这里我们用一个简单的打印信息语句来代替。然后递归的处理当前节点的左子节点，再处理右子节点。

非递归实现

    递归实现的时候是每次访问当前节点，再接着访问它的左子节点，再访问右子节点。而用非递归的方式来实现时，我们不可避免的要使用到栈。因为我们访问完了某个节点和它的左子节点后还要返回来访问它的右子节点。这样，我们就有两种具体实现方式。

    1. 既然我们访问每个节点的时候，首先要针对这个节点进行处理，然后再处理它的左右子节点。而且是先处理左子节点再处理右子节点。我们可以在处理节点后将该节点入栈，但是出栈的时候这个节点已经被处理过了，只需要接着去处理它的右子节点就可以了。我们在碰到的节点不为空的情况下，都是执行处理该节点，然后将节点入栈的操作。一直到节点为空了，则退栈，退到前一个处理过的节点，再将该节点指向右子节点。

private void preOrderIterTraverse2(BinaryNode<T> t)
{
	if(t != null)
	{
		Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
		while(t != null || !stack.empty())
		{
			if(t != null)
			{
				System.out.print(t.element + " ");
				stack.push(t);
				t = t.left;
			}
			else
			{
				t = stack.pop();
				t = t.right;
			}
		}
	}
}

    这里的一个重点是需要判断循环的退出条件，必须是stack为空和t也为空的时候，表示树已经遍历完了。

    2. 还有一种前序遍历的方式，和前面的方式有点细微的差别。既然我们每次访问都是当前节点，然后是左子节点，再就是右子节点。那么既然左子节点先处理，在栈里头，它们应该被后压入到栈中，而右子节点应该先被加入到栈中。我们每次遍历的时候只要把当前栈顶的元素弹出来，处理完之后再先后把它的右子节点、左子节点压栈。

private void preOrderIterTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
		stack.push(t);
		while(!stack.empty())
		{
			BinaryNode<T> node = stack.pop();
			System.out.print(node.element + " ");
			if(node.right != null) stack.push(node.right);
			if(node.left != null) stack.push(node.left);
		}
	}	
}

 

中序

    中序的遍历过程比较类似，就是“左子节点-当前节点-右子节点” 。

递归实现

    有了前面的讨论，相对代码就很简单直接了：

private void inOrderTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		inOrderTraverse(t.left);
		System.out.print(t.element + " ");
		inOrderTraverse(t.right);
	}
}

 

非递归实现

    非递归的顺序来中序遍历树的时候，我们要考虑到。它每次访问的时候都是要访问左子节点。那么按照递归的定义，最开始被访问处理的一定是最左下的子节点。当这个这个节点的左子节点肯定已经为空了。同时，我们也可以把它当成一个左子节点为空的根节点。那么访问完它之后我们需要再到它的右子节点继续前面的那个一路向左的过程。每次到最左边没有其他左子节点了，我们再弹栈，处理最上面这个节点。

 

private void inOrderIterTraverse(BinaryNode<T> t) {
	if(t != null) {
		Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
		BinaryNode<T> p = t;
		while(p != null || !stack.empty()) {
			if(p != null) {
				stack.push(p);
				p = p.left;
			} else {
				p = stack.pop();
				System.out.print(p.element + " ");
				p = p.right;
			}
		}
	}
}

    和前面的问题类似，我们的循环终止条件是p和栈为空。

 

后序

     后续的遍历则是“左子节点-右子节点-当前节点”。

递归实现

    递归实现和前面的代码类似，毫无难度：

private void postOrderTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		postOrderTraverse(t.left);
		postOrderTraverse(t.right);
		System.out.print(t.element + " ");
	}
}

    看代码，不解释。

 

非递归实现

    后序遍历的非递归实现可以说是这几种里面最难的。这里面的解决办法也不是我最初想到的，在参考了后续的实现之后才分析出来。问题的解决思路如下：对于任意一个节点，我们需要访问了它的左右子节点之后才能访问它。所以，我们可以这样来考虑，对于一个节点，先将它入栈，如果它的左右子节点为空，则可以直接访问它。另外，如果它的左右子节点都被访问过了，也可以访问它。如果不是以上的这两种情况，则先后将它的右子节点和左子节点入栈。这样保证了每次先访问左子节点，再访问右子节点。

    还有一个问题就是，在前面判断是否能访问该节点时，我们怎么知道它的左右子节点已经被访问了呢？这里用一个比较巧妙的手法，用了一个额外的引用pre。它指向当前访问节点的前一个节点。如果它的前一个节点是当前节点的左右子节点，则表示子节点已经访问完了。对于判断它的前一个节点是当前节点的左子节点这一种情况有点让人困惑。因为按照前面的遍历顺序，走了左子节点要走右子节点，如果有右子节点的话，这种条件不成立，如果没有右子节点，就会出现这种情况。

 

private void postOrderIterTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
		BinaryNode<T> cur, pre = null;
		stack.push(t);
		while(!stack.empty())
		{
			cur = stack.peek();
			if((cur.left == null && cur.right == null) ||
				(pre != null && (pre == cur.left || pre == cur.right)))
			{
				System.out.print(cur.element + " ");
				stack.pop();
				pre = cur;
			}
			else
			{
				if(cur.right != null)
					stack.push(cur.right);
				if(cur.left != null)
					stack.push(cur.left);
			}
		}
	}
}

    这部分的代码的难点在于要判断需要访问的节点符合的条件。

逐层遍历

    逐层遍历的过程就是一个广度优先遍历树的过程。树的结构是一层一层的。这个遍历的顺序就是从最上层开始一层一层的按照从左到右的顺序输出。这个问题看似比较困难，实际上只要把队列这个数据结构搬出来，就已经解决一大半了。

    它的过程无非就是碰到一个节点，先处理它，再分别将它的左右子节点加入到队列。这样一直从队列头取，一边从队列尾加，一直到队列为空。代码如下：

private void hierarchyTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		Queue<BinaryNode<T>> queue = new LinkedList<BinaryNode<T>>();
		queue.add(t);
		while(queue.size() > 0)
		{
			BinaryNode<T> node = queue.remove();
			System.out.print(node.element + " ");
			if(node.left != null) queue.add(node.left);
			if(node.right != null) queue.add(node.right);
		}
	}
}

 

总结

    二叉树的定义虽然大体上是要求任何一个节点包含分别指向左右子节点的引用（指针） ，但是根据一些特殊的需要，它的实现会有所调整。比如增加指向父节点的引用或者指向兄弟节点的引用。在一些问题比如求父节点或者前一个/后一个节点的情况下，这些新增加的部分能够对问题解决带来极大的便利。

    围绕二叉树的常用几种遍历形式涌现出很多有意思的问题。这里主要针对递归和非递归的实现做了一个总结。某些问题，比如说根据某两种遍历的序列来构造树、遍历结果序列和树的关系、节点的共同父节点等会在后续的文章里进一步分析。

参考资料

http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html 

http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=sr_1_1?s=books&ie=UTF8&qid=1363617759&sr=1-1&keywords=introduction+to+algorithms

http://www.amazon.com/Data-Structures-Problem-Solving-Using/dp/0321541405/ref=sr_1_1?s=books&ie=UTF8&qid=1363617891&sr=1-1&keywords=data+structures+%26+problem+solving+using+java