转：http://memewry.iteye.com/blog/1490721
据说面试中树考到的概率很高
package com.gengu.树;import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ConcurrentLinkedQueue;import org.junit.Test;/*** 这里测试树的相关算法* 1：构造一个树* 2：先序遍历* 3：中序遍历* 4：后序遍历* 5：层次遍历* 6：打印某一层二叉树的所有节点* 7：求高度* 8：求最远的节点* 9：判断一个树是不是平衡二叉树* */
class Node{public int value;public Node left;public Node right;public Node(int value){this.value = value;}
}public class TestTree {public static Node root = new Node(9);public static Node value1 ;public static Node value2 ;/*** 创建一颗二叉树* */public static void createTree(){Node node1 = new Node(8);Node node2 = new Node(7);Node node3 = new Node(6);Node node4 = new Node(5);Node node5 = new Node(4);Node node6 = new Node(3);Node node7 = new Node(2);Node node8 = new Node(1);Node node9 = new Node(0);Node node10 = new Node(11);Node node11 = new Node(12);value1 = node3;value2 = node9;root.left = node1;root.right = node2;node1.left = node3;node1.right = node4;node2.left = node5;node2.right = node6;node3.left = node7;node3.right = node8;node6.left = node10;node10.right = node11;node8.right = node9;}/*** 先序遍历* */public static void rootFirst(Node node){System.out.println(node.value);if(node.left != null){rootFirst(node.left);}if(node.right != null){rootFirst(node.right);}}/*** 后序遍历* */public static void rootLast(Node node){if(node.left != null){rootLast(node.left);}if(node.right != null){rootLast(node.right);}System.out.println(node.value);}/*** 中序*/public static void rootMid(Node node){if(node.left != null){rootMid(node.left);}System.out.println(node.value);if(node.right != null){rootMid(node.right);}}/*** 层次第n层的节点* */public static void layer(Node node,int n){if(node == null){return ;}if(1 == n){System.out.println(node.value);}else {layer(node.left,n-1);layer(node.right, n-1);}}/*** 求出树的高度* */public static int getHeight(Node root){if(null == root){return 0;}else{int lh = getHeight(root.left);int rh = getHeight(root.right);return lh>rh?lh+1:rh+1;}}/*** 层次序遍历* */public static void layer1(Node root){Queue<Node> nodes = new ConcurrentLinkedQueue<Node>();//加入第一个节点nodes.add(root);while(true){if(nodes.isEmpty()){break;}Node node2 = nodes.poll();if(node2.left!=null){nodes.add(node2.left);}if(node2.right!=null){nodes.add(node2.right);}System.out.println(node2.value);}}/*** 判断一颗树是不是平衡二叉树* */public static boolean isAVL(Node root){if(root==null){return true;}else {//求左树的高度int left_depth = getHeight(root.left);//右子树的高度int right_depth = getHeight(root.right);System.out.println(left_depth);System.out.println(right_depth);//如果从这个点可以看出它不平衡那么就返回falseif(left_depth-right_depth>1||right_depth-left_depth>1){return false;}//如果从这个节点往下看是平衡的不能就说它是平衡//还要看它的左右子树else {return isAVL(root.right)&&isAVL(root.right);}}}/*** 中序遍历的非递归算法* 要注意的是所有节点都要入栈* */public static void inorder(Node root){Stack<Node> stack1 = new Stack<Node>();Node node = root;//stack1.push(root);//第一个节点的路径while(node!=null||!stack1.isEmpty()){if(node!=null){stack1.push(node);node = node.left;}else {node = stack1.pop();System.out.print(node.value);node = node.right;}}System.out.println();}/*** 先序遍历* 非递归算法* */public static void preorder(Node root){Stack<Node> stack = new Stack<Node>();Node node = root;stack.push(root);while(!stack.isEmpty()){node = stack.pop();System.out.print(node.value);if(node.right!=null){stack.push(node.right);}if(node.left!=null){stack.push(node.left);}}System.out.println();}/*** 寻找最近公共父节点* */public static Node commanNode(Node root,Node value1,Node value2){if(root == null){return null;}else if(root==value1){//这里表示的是如果在其它地方没有找到value2//而找到了value1 那么表示value2在value1下面//所以返回value1return value1;}//同上else if(root==value2){return value2;}/*** 这里是一个分治的思想* 从它的左右子树分别去找两个节点* 如果找到那么当前节点就是最近父节点* 想不通的可以画图*/Node leftNode = commanNode(root.left, value1, value2);Node rightNode = commanNode(root.right, value1, value2);//如果在左右子树种分别找到就返回当前节点if(leftNode!=null&&rightNode!=null){return root;}/*** 如果只有在左边找到这个节点 那么返回* 因为在右边没找到所以另外那个顶点一定是这个节点的子节点* 画个图就能看懂*/else if(leftNode!=null){return leftNode;}/*** 如果只有在右边找到这个节点 那么返回* 因为在左边没找到所以另外那个顶点一定是这个节点的子节点* 画个图就能看懂*/else if(rightNode!=null){return rightNode;}else return null;}@Testpublic void test(){createTree();System.out.println(commanNode(root, value1, value2).value);}}