引入：
这里我们来复习下二叉树的基本操作，这里假定我们定义一个有序二叉树，就是对于任意的节点，其如果有左子节点，那么左子节点的值一定小于该节点，如果有右子节点，则右子节点的值一定大于该节点。我们这里还给出代码表明如何前序，中序，后序来遍历这个二叉树。
实践：
我们先定义一个二叉树节点的类：
package com.charles.algo.binarytree;/** * 这个类定义了一个二叉树的节点 * @author charles.wang * */public class BinaryTreeNode { //二叉树中当前节点的内容 private Object data; //二叉树的左子节点 private BinaryTreeNode leftChild; //二叉树的右子节点 private BinaryTreeNode rightChild; public BinaryTreeNode(Object data,BinaryTreeNode leftChild,BinaryTreeNode rightChild){ this.data =data; this.leftChild=leftChild; this.rightChild=rightChild; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public BinaryTreeNode getLeftChild() { return leftChild; } public void setLeftChild(BinaryTreeNode leftChild) { this.leftChild = leftChild; } public BinaryTreeNode getRightChild() { return rightChild; } public void setRightChild(BinaryTreeNode rightChild) { this.rightChild = rightChild; } } 然后我们定义一个二叉树类，这个二叉树提供了插入节点，前序遍历，中序遍历，后序遍历的方法：
package com.charles.algo.binarytree;/** * 这里定义了一个基本的有序二叉树的数据结构 * @author charles.wang * */public class OrderedBinaryTree{ //用链表来实现排序二叉树的数据存储，这里放着根节点 private BinaryTreeNode rootNode; public OrderedBinaryTree(){ rootNode = null; } /** * 返回当前有序二叉树的最大高度 * @return */ public int getMaxHeight(){ return getHeight(rootNode); } /** * 基于当前树根节点确定子树的高度,这是一个递归的方法 * @return */ private int getHeight(BinaryTreeNode currentNode){ //如果当前树根节点为空，则返回 0 if(currentNode==null) return 0; //如果当前树根节点不为空，那么获取左子树高度和右字数高度的最大值 int maxLeftTreeHeight = getHeight(currentNode.getLeftChild())+1; int maxRightTreeHeight = getHeight(currentNode.getRightChild())+1; return Math.max(maxLeftTreeHeight, maxRightTreeHeight); } /** * 插入节点到当前的有序二叉树， */ public OrderedBinaryTree insertNode(Object data ){ //如果有序二叉树中rootNode为空，那么就直接新建一个节点并且赋值给root if(rootNode==null){ BinaryTreeNode binaryTreeNode = new BinaryTreeNode(data,null,null); rootNode=binaryTreeNode; return this; } //如果有序二叉树的rootNode不为空，那么就调用递归方法进行插入 else return insertNode(data,rootNode); } /** * 递归的插入一个节点到当前节点使得仍然保持 一个有序二叉树 */ public OrderedBinaryTree insertNode(Object data, BinaryTreeNode rootNode){ //创建一个代表当前待查数据的节点 BinaryTreeNode currentNode = new BinaryTreeNode(data,null,null); //吧当前的数据和被插入的rootNode的大小进行比较 //如果当前数据小于被插入的rootNode,那么这个新的数据节点必定插在rootNode的左边 if( (Integer)data< (Integer)rootNode.getData()){ //如果待插的rootNode的左节点为空，那么直接插入 if(rootNode.getLeftChild()==null){ rootNode.setLeftChild(currentNode); return this; } //如果待插的rotNode的左节点不为空，则递归的吧待插入点设为root的左节点，然后递归的调用方法插入 else return insertNode(data ,rootNode.getLeftChild()); } //如果当前数据大于被插入的rootNode,那么这个新的数据节点必定插在rootNode的右边 else { //如果待插的rootNode的右边节点为空，那么直接插入 if(rootNode.getRightChild()==null){ rootNode.setRightChild(currentNode); return this; } //如果待插的rootNode的右边节点不为空，则赌鬼的吧所待插入点设为root的右节点，然后递归调用方法插入 else return insertNode(data,rootNode.getRightChild()); } } /** * 前序遍历这个二叉树，并且打印出这个二叉树的各个节点 */ public void preOrderFullBinaryTree(){ preOrder(rootNode); } /** * 中序遍历这个二叉树，并且打印出这个二叉树的各个节点 */ public void midOrderFullBinaryTree(){ midOrder(rootNode); } /** * 后序遍历这个二叉树，并且打印出这个二叉树的各个节点 */ public void postOrderFullBinaryTree(){ postOrder(rootNode); } /** * 前序遍历某节点，它会先打印当前节点，然后打印出左边节点，然后打印出右边节点 */ private void preOrder(BinaryTreeNode currentNode){ //当前的节点如果是null,则不打印出当前节点，并且退出递归 if(currentNode!=null){ System.out.print(currentNode.getData()+" "); //遍历左边子树 preOrder(currentNode.getLeftChild()); //遍历右边子树 preOrder(currentNode.getRightChild()); } } /** * 中序遍历某节点，它会先打印左边节点，再打印当前节点，最后打印出右边节点 * @param args */ private void midOrder(BinaryTreeNode currentNode){ //当前节点如果是null,则不打印出当前节点，并且退出递归 if(currentNode!=null){ midOrder(currentNode.getLeftChild()); System.out.print(currentNode.getData()+" "); midOrder(currentNode.getRightChild()); } } /** * 后序遍历某个节点，它会先打印出左边节点，再打印出右边节点，最后打印出当前节点 * @param args */ private void postOrder(BinaryTreeNode currentNode){ //如果当前的节点是null,则不打印出当前节点，并且退出递归 if(currentNode!=null){ postOrder(currentNode.getLeftChild()); postOrder(currentNode.getRightChild()); System.out.print(currentNode.getData()+" "); } } public static void main(String[] args){ OrderedBinaryTree fbt = new OrderedBinaryTree (); fbt.insertNode(12).insertNode(5).insertNode(9).insertNode(11).insertNode(8).insertNode(42).insertNode(4); //前序遍历所有的节点 System.out.println("前序的方式遍历二叉树的所有的节点:"); fbt.preOrderFullBinaryTree(); System.out.println(); //中序遍历所有的节点 System.out.println ("中序的方式遍历二叉树的所有的节点:"); fbt.midOrderFullBinaryTree(); System.out.println(); //后序遍历所有的节点 System.out.println("后序的方式遍历二叉树的所有的节点:"); fbt.postOrderFullBinaryTree(); System.out.println(); }}
其实由于考虑到二叉树定义的递归性，我们上述方法都是用递归实现的，比如插入就是比较当前元素，如果插入元素比当前元素少，那么就比较当前元素的左子元素，如果左子元素不存在，那么新插入的元素就作为左子元素，否则就以左子元素为根，递归的插入该元素到左子二叉树中。反过来也一样，如果插入元素比当前元素大，那么久比较当前元素的右子元素，如果右子元素不存在，那么新插元素就作为右子元素，否则就以右子元素为根，递归的插入到该元素到右子二叉树中。
前序，中序，后序遍历也是一样的。
验证结果：
最后我们来运行这个简单的例子，果然是期望的，比如我们分别插入了果然的不一样的数，那么遍历结果顺序是不一样的但是都遍历二叉树的所有节点。