二叉树分析之一：定义和遍历讨论
? ? 它包含有3个部分，一个数据部分，保存节点的数据内容。两个引用，分别指向左边和右边的子节点。
通过这种形式定义的二叉树则如下图所示：
? ? 从图中我们可以看出，这种二叉树的数据结构定义我们可以将它定义成两个部分，一个是节点(BinaryNode)，还有一个就是二叉树（BinaryTree）。
下面是一个相对比较通用一点的节点定义：
? ? 对应的二叉树则转变成如下：
?
? ? 这部分带来的变动在节点和树的定义上影响比较小，加入了父节点会在后续的插入元素和删除元素的时候影响比较大。这里，节点对应的定义代码为：
? ? 这里，我们按照递归的定义，首先访问当前节点，这里我们用一个简单的打印信息语句来代替。然后递归的处理当前节点的左子节点，再处理右子节点。
非递归实现? ? 递归实现的时候是每次访问当前节点，再接着访问它的左子节点，再访问右子节点。而用非递归的方式来实现时，我们不可避免的要使用到栈。因为我们访问完了某个节点和它的左子节点后还要返回来访问它的右子节点。这样，我们就有两种具体实现方式。
? ? 1. 既然我们访问每个节点的时候，首先要针对这个节点进行处理，然后再处理它的左右子节点。而且是先处理走子节点再处理右子节点。我们可以在处理节点后将该节点入栈，但是出栈的时候这个节点已经被处理过了，只需要接着去处理它的右子节点就可以了。我们在碰到的节点不为空的情况下，都是执行处理该节点，然后将节点入栈的操作。一直到节点为空了，则退栈，退到前一个处理过的节点，再将该节点指向右子节点。
? ? 这里的一个重点是需要判断循环的退出条件，必须是stack为空和t也为空的时候，表示树已经遍历完了。
? ? 2. 还有一种前序遍历的方式，和前面的方式有点细微的差别。既然我们每次访问都是当前节点，然后是左子节点，再就是右子节点。那么既然左子节点先处理，在栈里头，它们应该被后压入到栈中，而右子节点应该先被加入到栈中。我们每次遍历的时候只要把当前栈顶的元素弹出来，处理完之后再先后把它的右子节点、左子节点压栈。
?
中序? ? 中序的遍历过程比较类似，就是“左子节点-当前节点-右子节点” 。
递归实现? ? 有了前面的讨论，相对代码就很简单直接了：
?
非递归实现? ? 非递归的顺序来中序遍历树的时候，我们要考虑到。它每次访问的时候都是要访问左子节点。那么按照递归的定义，最开始被访问处理的一定是最左下的子节点。当这个这个节点的左子节点肯定已经为空了。同时，我们也可以把它当成一个左子节点为空的根节点。那么访问完它之后我们需要再到它的右子节点继续前面的那个一路向左的过程。每次到最左边没有其他左子节点了，我们再弹栈，处理最上面这个节点。
?
? ? 和前面的问题类似，我们的循环终止条件是p和栈为空。
?
后序? ? ?后续的遍历则是“左子节点-右子节点-当前节点”。
递归实现? ? 递归实现和前面的代码类似，毫无难度：
? ? 看代码，不解释。
?
非递归实现? ? 后序遍历的非递归实现可以说是这几种里面最难的。这里面的解决办法也不是我最初想到的，在参考了后续的实现之后才分析出来。问题的解决思路如下：对于任意一个节点，我们需要访问了它的左右子节点之后才能访问它。所以，我们可以这样来考虑，对于一个节点，先将它入栈，如果它的左右子节点为空，则可以直接访问它。另外，如果它的左右子节点都被访问过了，也可以访问它。如果不是以上的这两种情况，则先后将它的右子节点和左子节点入栈。这样保证了每次先访问左子节点，再访问右子节点。
? ? 还有一个问题就是，在前面判断是否能访问该节点时，我们怎么知道它的左右子节点已经被访问了呢？这里用一个比较巧妙的手法，用了一个额外的引用pre。它指向当前访问节点的前一个节点。如果它的前一个节点是当前节点的左右子节点，则表示子节点已经访问完了。对于判断它的前一个节点是当前节点的左子节点这一种情况有点让人困惑。因为按照前面的遍历顺序，走了左子节点要走右子节点，如果有右子节点的话，这种条件不成立，如果没有右子节点，就会出现这种情况。
?
? ? 这部分的代码的难点在于要判断需要访问的节点符合的条件。
逐层遍历? ? 逐层遍历的过程就是一个广度优先遍历树的过程。树的结构是一层一层的。这个遍历的顺序就是从最上层开始一层一层的按照从左到右的顺序输出。这个问题看似比较困难，实际上只要把队列这个数据结构搬出来，就已经解决一大半了。
? ? 它的过程无非就是碰到一个节点，先处理它，再分别将它的左右子节点加入到队列。这样一直从队列头取，一边从队列尾加，一直到队列为空。代码如下：
?
总结? ? 二叉树的定义虽然大体上是要求任何一个节点包含分别指向左右子节点的引用（指针） ，但是根据一些特殊的需要，它的实现会有所调整。比如增加指向父节点的引用或者指向兄弟节点的引用。在一些问题比如求父节点或者前一个/后一个节点的情况下，这些新增加的部分能够对问题解决带来极大的便利。
? ? 围绕二叉树的常用几种遍历形式涌现出很多有意思的问题。这里主要针对递归和非递归的实现做了一个总结。某些问题，比如说根据某两种遍历的序列来构造树、遍历结果序列和树的关系、节点的共同父节点等会在后续的文章里进一步分析。
参考资料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
