二叉搜索树（BST）与哈夫曼树（HFM）
本篇，我们以搜索树和哈夫曼树为例，探究二叉树建立和遍历过程。
二叉树定义：
二叉树 是一种有限的、非线性的树形数据结构，每个节点最多只有两个子节点，分别称为：左孩子（左子树）、右孩子（右子树）
搜索树概念：
1.左子树上所有节点值 ＜ 根节点值
2.右子树上所有节点值 ＞ 根节点值
3.左右子树，也必须各自是二叉搜索树
搜索树类：
自定义类MTree，创建节点类TreeNode（）：
class TreeNode{publicintdata;public TreeNode left;public TreeNode right;publicTreeNode(intdata){this.data=data;}}在MTree类中，定义全局变量 root 作为根节点：
public TreeNode root;定义建树的方法：
判断原先是否有根节点，进而判断当前节点curr和存入节点值的大小，以及该节点是否存在左右子树来确定放入节点的位置：
publicvoidcreateTree(TreeNode node){if(root==null){root=node;}else{TreeNode curr=root;while(true){if(curr.data>node.data){if(curr.left==null){curr.left=node;break;}curr=curr.left;}else{if(curr.right==null){curr.right=node;break;}curr=curr.right;}}}}二叉树中序遍历：（栈方法）
创建栈对象stack，判断当前指针不为空或栈里还有节点，如果当前节点不为空，就把当前节点压入栈，更新 curr ，若为空则说明节点走到最左边了，出栈回弹，并打印当前值。接着节点赋给当前节点右边，继续遍历：
publicvoidinorde(TreeNode root){TreeNode curr=root;Stack<TreeNode>stack=new Stack<>();while(curr!=null||!stack.isEmpty()){if(curr!=null){//压栈stack.push(curr);curr=curr.left;}else{//出栈curr=stack.pop();//打印节点System.out.println(curr.data+" ");curr=curr.right;}}}二叉树前序遍历：（栈方法）
创建栈对象stack，判断当前指针不为空或栈里还有节点，如果当前节点不为空，打印当前节点（父节点），当前节点压栈（用于之后寻找右子树），一路遍历左子树，否则弹出栈中当前节点，转向遍历它右子树
publicvoidpreorder(TreeNode root){TreeNode curr=root;Stack<TreeNode>stack=new Stack<>();while(curr!=null||!stack.isEmpty()){if(curr!=null){System.out.println(curr.data+" ");stack.push(curr);curr=curr.left;}else{curr=stack.pop();curr=curr.right;}}}二叉树后序遍历：（栈方法）
定义pre来记录上一个被打印访问的节点，往左一直走到底，走完后拿到栈顶节点不弹出，取出栈顶，判断能不能打印这个节点，接着满足以下任意一种情况即可打印当前栈顶节点：
1.没有右子树 2.右子树已经全部遍历、打印完了。弹出节点、打印节点，更新 pre 为当前刚打印的节点，标记右子树已走完
publicvoidpostorder(TreeNode root){TreeNode curr=root;Stack<TreeNode>stack=new Stack<>();TreeNode pre=null;while(curr!=null||!stack.isEmpty()){if(curr!=null){stack.push(curr);curr=curr.left;}else{TreeNode top=stack.peek();//右边为空或右边已经走完if(top.right==null||top.right==pre){stack.pop();System.out.println(top.data+" ");pre=top;}else{//右边没走完，去右边curr=top.right;}}}}二叉树的中序遍历（递归）：
publicvoidinorde(TreeNode root){if(root!=null){inorde(root.left);System.out.println(root.data+" ");inorde(root.right);}}最后定义测试方法，创建数组，用TreeNode类创建的对象来存数组中的值，创建二叉树，进行遍历：
publicstaticvoidmain(String[]args){intarr[]={4,3,5,7,1,2,9};MTree tree=newMTree();for(inti=0;i<arr.length;i++){TreeNode node=newTreeNode(arr[i]);tree.createTree(node);}tree.inorde(tree.root);tree.preorder(tree.root);tree.postorder(tree.root);}测试结果如图（以中序遍历为例）：
哈夫曼树概念：
1.把所有叶子权值从小到大排序；
2.选出权值最小的两个节点；
3.合成一个新父节点，父节点权值 = 两节点之和；
4.把新父节点放回集合，重复以上步骤；
5.直到只剩一个节点，就是哈夫曼树根。
哈夫曼树类：
自定义类HmfTree，创建节点类TreeNode（），定义全局变量root。
为了方便取出列表中最小两个数值，先对传入的列表进行排序，这里用冒泡排序定义排序方法：
publicvoidsort(List<TreeNode>nodeList){for(inti=0;i<nodeList.size();i++){for(intj=0;j<nodeList.size()-1;j++){if(nodeList.get(j).data>nodeList.get(j+1).data){TreeNode temp=nodeList.get(j);nodeList.set(j,nodeList.get(j+1));nodeList.set(j+1,temp);}}}}定义创建哈夫曼树的方法：
注意，方法最后，要将排序列表中首位置元素传给作为根节点的 root ，
publicvoidcreateTree(List<TreeNode>nodeList){while(nodeList.size()>1){//对nodeList升序排序sort(nodeList);//找到最小两个节点TreeNode left=nodeList.remove(0);TreeNode right=nodeList.remove(0);//构建子树TreeNode node=newTreeNode(left.data+right.data);node.left=left;node.right=right;//新节点添加到集合中nodeList.add(node);}root=nodeList.get(0);}中序遍历叶子节点：
思路类比上面搜索树，另外，在出栈时添加一步对弹出节点右子树是否存在的判断。（上面逻辑已经遍历到最左边子树了）
publicvoidinorder(){TreeNode curr=root;Stack<TreeNode>stack=new Stack<>();while(curr!=null||!stack.isEmpty()){if(curr!=null){//压栈stack.push(curr);curr=curr.left;}else{//出栈TreeNode node=stack.pop();//打印节点if(node.right==null&&node.left==null){System.out.println(node.data+" ");}curr=node.right;}}}最后，写测试方法：
publicstaticvoidmain(String[]args){int[]arr={4,2,1,6};List<TreeNode>nodeList=new ArrayList<>();for(inti=0;i<arr.length;i++){nodeList.add(newTreeNode(arr[i]));}HfmTree hfm=newHfmTree();hfm.createTree(nodeList);hfm.inorder();}演示结果如图：