树的基本结构
public class TreeNode<T>{public TreeNode<T> leftNode;public TreeNode<T> rightNode;public T data;public TreeNode(T data){this.data = data;}} 1.构建一颗树（本文以表达式树为例，用后缀表达式构建，我在前一篇已近介绍了如何将中序转换为后续表达式）
原理：利用栈。步骤：a.当前字符为字符或者数字，则直接构建一个节点，然后入栈
b.当前字符为操作符，则在栈中取出两个节点，将这两个节点作为孩子节点构建一棵树入栈
c.最后将栈中剩下的唯一节点返回，就是要构建的树
// 构建一颗字符树，即数学表达式public static TreeNode<Character> getTree(String obj){// TreeNode<Character> node2=new TreeNode<Character>(null);Stack<TreeNode<Character>> stack = new Stack<TreeNode<Character>>();for (int i = 0; i < obj.length(); i++){char temp = obj.charAt(i);if (Character.isLetterOrDigit(temp))// 如果是字母或者数字，那么直接构建一个树，入栈{TreeNode<Character> node = new TreeNode<Character>(temp);stack.push(node);} else// 操作符的话，从栈中取出两个树节点，然后合并成一个节点，操作符为根节点{TreeNode<Character> node = new TreeNode<Character>(temp);// 有操作符，栈至少有两个元素node.rightNode = stack.pop();node.leftNode = stack.pop();stack.push(node);}}return stack.pop();} 2.用先序，中序，后序打印一颗树，这个没有什么好说的
/* * 递归 打印一棵树 先序，中序，后序 */// 先序遍历一棵树，（根左右）public String printTreePreOreder(TreeNode<T> node){String obj = "";if (node != null){obj += node.data;obj += printTreePreOreder(node.leftNode);obj += printTreePreOreder(node.rightNode);}return obj;}// 中序遍历一棵树(左根右)public String printTreeInfixOreder(TreeNode<T> node){String obj = "";if (node != null){if (node.leftNode != null)obj += "(";obj += printTreeInfixOreder(node.leftNode);obj += node.data;obj += printTreeInfixOreder(node.rightNode);if (node.rightNode != null)obj += ")";}return obj;}// 后续遍历一棵树(左右根)public String printTreePostOreder(TreeNode<T> node){String obj = "";if (node != null){obj += printTreePostOreder(node.leftNode);obj += printTreePostOreder(node.rightNode);obj += node.data;}return obj;} 3.得到树的高度（使用递归）
原理：树根的高度=最大的孩子的高度+1
// 得到一棵树额高度public int getHeight(){if(this==null)return 0;if (this.leftNode == null && this.rightNode == null)return 1;int lHeight = this.leftNode.getHeight();int rHeight = this.rightNode.getHeight();return lHeight > rHeight ? lHeight + 1 : rHeight + 1;} 4.打印树的第k层（递归实现）
原理：可以理解为打印根的第k层，即打印根的孩子的第k-1层，当k=0时，可以直接打印出来
// 打印一棵树的第level层public void printTreeAtLevel(TreeNode<T> node, int level){if (node == null || level < 0)return;if (level == 0)// 到达目标层System.out.print(node.data);printTreeAtLevel(node.leftNode, level – 1);print(1);///打印一个空格printTreeAtLevel(node.rightNode, level – 1);} 5.按层次打印一棵树
我实现了两种方法：
方法一：
知道了树的高度，，依次打印出各层的高度。但是这种方法，会在打印任何一层的时候都会从根节点开始，浪费时间
// 按照树的格式打印一棵树,必须按层次打印public void printTree(){int height = getHeight();for (int i = 0; i < height; i++){print(height * 2 – i);printTreeAtLevel(this, i);System.out.println();}} 方法二：
用两个队列实现，队列1保存所有的同一层叶节点，队列2保存保存队列1的正在访问的孩子节点 ，队列1访问完以后，将队列2加到队列1（此时是空队列）中，再讲队列2清空
public void printTreeByQueue(TreeNode<T> root){Queue<TreeNode<T>> queue1, queue2;queue1 = new LinkedList<TreeNode<T>>();queue2 = new LinkedList<TreeNode<T>>();queue1.add(root);queue2.add(root);while (!queue2.isEmpty()){queue2.clear();while (!queue1.isEmpty()){TreeNode<T> node = queue1.poll();print(2);System.out.print(node.data);if (node.leftNode != null)queue2.add(node.leftNode);if (node.rightNode != null)queue2.add(node.rightNode);}queue1.addAll(queue2);System.out.println();}}
生活若剥去理想、梦想、幻想，那生命便只是一堆空架子
