【原创】Java与数据结构(中篇：树)

本文主要是介绍【原创】Java与数据结构(中篇：树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 + "  ");
}
}
}