二叉搜索树（BST）与哈夫曼树（HFM）

本篇我们以搜索树和哈夫曼树为例探究二叉树建立和遍历过程。二叉树定义二叉树 是一种有限的、非线性的树形数据结构每个节点最多只有两个子节点分别称为左孩子左子树、右孩子右子树搜索树概念1.左子树上所有节点值 根节点值2.右子树上所有节点值 根节点值3.左右子树也必须各自是二叉搜索树搜索树类自定义类MTree创建节点类TreeNodeclass TreeNode{publicintdata;public TreeNode left;public TreeNode right;publicTreeNode(intdata){this.datadata;}}在MTree类中定义全局变量 root 作为根节点public TreeNode root;定义建树的方法判断原先是否有根节点进而判断当前节点curr和存入节点值的大小以及该节点是否存在左右子树来确定放入节点的位置publicvoidcreateTree(TreeNode node){if(rootnull){rootnode;}else{TreeNode currroot;while(true){if(curr.datanode.data){if(curr.leftnull){curr.leftnode;break;}currcurr.left;}else{if(curr.rightnull){curr.rightnode;break;}currcurr.right;}}}}二叉树中序遍历栈方法创建栈对象stack判断当前指针不为空或栈里还有节点如果当前节点不为空就把当前节点压入栈更新 curr 若为空则说明节点走到最左边了出栈回弹并打印当前值。接着节点赋给当前节点右边继续遍历publicvoidinorde(TreeNode root){TreeNode currroot;StackTreeNodestacknew Stack();while(curr!null||!stack.isEmpty()){if(curr!null){//压栈stack.push(curr);currcurr.left;}else{//出栈currstack.pop();//打印节点System.out.println(curr.data );currcurr.right;}}}二叉树前序遍历栈方法创建栈对象stack判断当前指针不为空或栈里还有节点如果当前节点不为空打印当前节点父节点当前节点压栈用于之后寻找右子树一路遍历左子树否则弹出栈中当前节点转向遍历它右子树publicvoidpreorder(TreeNode root){TreeNode currroot;StackTreeNodestacknew Stack();while(curr!null||!stack.isEmpty()){if(curr!null){System.out.println(curr.data );stack.push(curr);currcurr.left;}else{currstack.pop();currcurr.right;}}}二叉树后序遍历栈方法定义pre来记录上一个被打印访问的节点往左一直走到底走完后拿到栈顶节点不弹出取出栈顶判断能不能打印这个节点接着满足以下任意一种情况即可打印当前栈顶节点1.没有右子树 2.右子树已经全部遍历、打印完了。弹出节点、打印节点更新 pre 为当前刚打印的节点标记右子树已走完publicvoidpostorder(TreeNode root){TreeNode currroot;StackTreeNodestacknew Stack();TreeNode prenull;while(curr!null||!stack.isEmpty()){if(curr!null){stack.push(curr);currcurr.left;}else{TreeNode topstack.peek();//右边为空或右边已经走完if(top.rightnull||top.rightpre){stack.pop();System.out.println(top.data );pretop;}else{//右边没走完去右边currtop.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 treenewMTree();for(inti0;iarr.length;i){TreeNode nodenewTreeNode(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(ListTreeNodenodeList){for(inti0;inodeList.size();i){for(intj0;jnodeList.size()-1;j){if(nodeList.get(j).datanodeList.get(j1).data){TreeNode tempnodeList.get(j);nodeList.set(j,nodeList.get(j1));nodeList.set(j1,temp);}}}}定义创建哈夫曼树的方法注意方法最后要将排序列表中首位置元素传给作为根节点的 root publicvoidcreateTree(ListTreeNodenodeList){while(nodeList.size()1){//对nodeList升序排序sort(nodeList);//找到最小两个节点TreeNode leftnodeList.remove(0);TreeNode rightnodeList.remove(0);//构建子树TreeNode nodenewTreeNode(left.dataright.data);node.leftleft;node.rightright;//新节点添加到集合中nodeList.add(node);}rootnodeList.get(0);}中序遍历叶子节点思路类比上面搜索树另外在出栈时添加一步对弹出节点右子树是否存在的判断。上面逻辑已经遍历到最左边子树了publicvoidinorder(){TreeNode currroot;StackTreeNodestacknew Stack();while(curr!null||!stack.isEmpty()){if(curr!null){//压栈stack.push(curr);currcurr.left;}else{//出栈TreeNode nodestack.pop();//打印节点if(node.rightnullnode.leftnull){System.out.println(node.data );}currnode.right;}}}最后写测试方法publicstaticvoidmain(String[]args){int[]arr{4,2,1,6};ListTreeNodenodeListnew ArrayList();for(inti0;iarr.length;i){nodeList.add(newTreeNode(arr[i]));}HfmTree hfmnewHfmTree();hfm.createTree(nodeList);hfm.inorder();}演示结果如图