1. 二叉树 遍历算法
package tree; import java.util.ArrayDeque; import java.util.Queue; /** * 二叉树的四种遍历方式<br> * 先序，中序，后序，广度优先遍历 * * @author yinger */ public class IteratorAlgorithm { public static void main(String[] args) { TreeNode root = new TreeNode("0"); TreeNode node1 = new TreeNode("1"); TreeNode node2 = new TreeNode("2"); root.left = node1; root.right = node2; TreeNode node3 = new TreeNode("3"); TreeNode node4 = new TreeNode("4"); node1.left = node3; node1.right = node4; TreeNode node5 = new TreeNode("5"); TreeNode node6 = new TreeNode("6"); node2.left = node5; node2.right = node6; TreeNode node7 = new TreeNode("7"); TreeNode node8 = new TreeNode("8"); node3.left = node7; node4.right = node8; System.out.print("PreIterator: "); root.preIterator();// PreIterator: 0 1 3 7 4 8 2 5 6 System.out.println(); System.out.print("InIterator: "); root.inIterator();// InIterator: 7 3 1 4 8 0 5 2 6 System.out.println(); System.out.print("PostIterator: "); root.postIterator();// PostIterator: 7 3 8 4 1 5 6 2 0 System.out.println(); System.out.print("WideIterator: "); root.wideIterator();// WideIterator: 0 1 2 3 4 5 6 7 8 } } class TreeNode { Object data; TreeNode left; TreeNode right; public TreeNode(Object data) { this.data = data; } // preIterator public void preIterator() { visit(this); if (left != null) { left.preIterator(); } if (right != null) { right.preIterator(); } } // inIterator public void inIterator() { if (left != null) { left.inIterator(); } visit(this); if (right != null) { right.inIterator(); } } // postIterator public void postIterator() { if (left != null) { left.postIterator(); } if (right != null) { right.postIterator(); } visit(this); } // wideIterator public void wideIterator() { // ArrayDeque:faster than stack (when used as a stack) and linkedlist(when used as a queue) Queue<TreeNode> deque = new ArrayDeque<TreeNode>(); deque.add(this); TreeNode node; while ((node = deque.poll()) != null) { visit(node); if (node.left != null) { deque.add(node.left); } if (node.right != null) { deque.add(node.right); } } } // visit function private void visit(TreeNode treeNode) { if (treeNode != null) { System.out.print(treeNode.data + " "); } } }
2. 哈夫曼树 这次我用的是插入排序，两次删除一次插入，以前用的是和最小堆结合，原理差不多，其实也可以使用快排
package tree; import java.util.ArrayDeque; import java.util.Collections; import java.util.LinkedList; import java.util.List; import java.util.Queue; /** * 哈夫曼树 * * @author yinger */ public class HuffmanTree { public static void main(String[] args) { HuffmanTreeNode root = new HuffmanTreeNode("root", 0.5); HuffmanTreeNode node1 = new HuffmanTreeNode("node1", 1.0); HuffmanTreeNode node2 = new HuffmanTreeNode("node2", 2.0); HuffmanTreeNode node3 = new HuffmanTreeNode("node3", 3.0); HuffmanTreeNode node4 = new HuffmanTreeNode("node4", 3.5); LinkedList<HuffmanTreeNode> nodes = new LinkedList<HuffmanTreeNode>(); Collections.addAll(nodes, root, node1, node2, node3, node4); HuffmanTree huffmanTree = new HuffmanTree(); HuffmanTreeNode treeRoot = huffmanTree.createHuffmanTree(nodes); treeRoot.wideIterator(); } public HuffmanTreeNode createHuffmanTree(LinkedList<HuffmanTreeNode> nodes) {// create huffmantree insertSort(nodes, 0, nodes.size() - 1);// sort nodes using insrt sort while (nodes.size() > 1) { HuffmanTreeNode left = nodes.pollFirst();// remove the two smallest HuffmanTreeNode right = nodes.pollFirst(); HuffmanTreeNode parent = new HuffmanTreeNode(left.data + "+" + right.data, left.weight + right.weight); parent.left = left; parent.right = right; insertNode(nodes, parent); }// end while,nodes.size = 1 --> the root node return nodes.peek(); } // insert new node into nodes,and make it sorted! private void insertNode(LinkedList<HuffmanTreeNode> nodes, HuffmanTreeNode parent) { nodes.addLast(parent);// first add it,make size++,then sort it! // System.out.println("Befor: insert new node:"); // for (HuffmanTreeNode huffmanTreeNode : nodes) { // System.out.print(huffmanTreeNode.weight + " "); // } // System.out.println(); int j, low, high, mid, size = nodes.size(); low = 0; high = size - 2;// attention:the last node is not included! while (low <= high) {// final position is low mid = (low + high) / 2; if (nodes.get(mid).weight > parent.weight) { high = mid - 1; } else { low = mid + 1; } } for (j = size - 1; j > low; j--) {// move back some elements nodes.set(j, nodes.get(j - 1)); } nodes.set(low, parent); // System.out.println("After: insert new node:" + " low=" + low); // for (HuffmanTreeNode huffmanTreeNode : nodes) { // System.out.print(huffmanTreeNode.weight + " "); // } // System.out.println(); } private void insertSort(List<HuffmanTreeNode> nodes, int start, int end) {// half find insert sort int i, j, size = nodes.size(); int low, high, mid; HuffmanTreeNode tempNode; for (i = 1; i < size; i++) {// 0 - (i-1) has been sorted,now insert i low = 0; high = i - 1; tempNode = nodes.get(i); while (low <= high) {// final right position is low mid = (low + high) / 2; if (nodes.get(mid).weight > tempNode.weight) { high = mid - 1; } else { low = mid + 1; } } for (j = i; j > low; j--) {// move back some elements nodes.set(j, nodes.get(j - 1)); } nodes.set(low, tempNode); } // System.out.println("After insertsort:"); // for (HuffmanTreeNode huffmanTreeNode : nodes) { // System.out.print(huffmanTreeNode.weight + " "); // } // System.out.println(); } } class HuffmanTreeNode { String data;// define data is string double weight;// weight of the node HuffmanTreeNode left; HuffmanTreeNode right; public HuffmanTreeNode(String data, double weight) { this.data = data; this.weight = weight; } // wideIterator public void wideIterator() { // ArrayDeque:faster than stack (when used as a stack) and linkedlist(when used as a queue) Queue<HuffmanTreeNode> deque = new ArrayDeque<HuffmanTreeNode>(); deque.add(this); HuffmanTreeNode node; while ((node = deque.poll()) != null) { visit(node); if (node.left != null) { deque.add(node.left); } if (node.right != null) { deque.add(node.right); } } } // visit function private void visit(HuffmanTreeNode node) { if (node != null) { System.out.println(node.data + " " + node.weight + " "); } } }
其他数据结构内容请看下篇。 谢谢阅读，如果发现错误，请及时回复我！