[Vicious--算法] 数据结构的实现（持续完整中）
 |
Spike
2007-07-03
补充方法：普里姆最小生成树
加入新二维数组：轻边集，加入无向联通图的双向边方法：添加双向边
package graph;
/**
* @author B.Chen
*
*/
public class Graph {
/**
* 节点数
*/
private int length;
/**
* 链表
*/
private GraphList[] list;
/**
* 权集
*/
private int[][] weight;
/**
* 轻边集
*/
private int[][] lightSide;
/**
* @param length
*/
public Graph(int length) {
this.length = length;
list = new GraphList[length];
weight = new int[length][length];
lightSide = new int[length][length];
}
/**
* @param v
*/
public void dfs(int v) {
int[] ajd = new int[length];
int ajdlength = list[v].getAjd(ajd);
list[v].visitable = true;
System.out.print(v + " ");
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!list[w].visitable) {
dfs(w);
}
}
}
/**
* 深度优先遍历
*/
public void dfsTravel() {
for (int i = 0; i < length; i++) {
list[i].visitable = false;
}
for (int i = 0; i < length; i++) {
if (!list[i].visitable) {
dfs(i);
}
}
}
/**
* 广度优先遍历
*/
public void bfsTravel() {
for (int i = 0; i < length; i++) {
list[i].visitable = false;
}
bfs();
}
/**
* bfs
*/
private void bfs() {
Queue queue = new Queue();
for (int index = 0; index < length; index++) {
if (!list[index].visitable) {
queue.addQueue(index);
list[index].visitable = true;
System.out.print(index + " ");
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] adj = new int[length];
int ajdlength = list[temp].getAjd(adj);
for (int i = 0; i < ajdlength; i++) {
int w = adj[i];
if (!list[w].visitable) {
System.out.print(w + " ");
queue.addQueue(w);
list[w].visitable = true;
}
}
}
}
}
}
/**
* 长度
*/
public void length() {
System.out.println(length);
}
/**
* @return boolean
*/
public boolean isEmpty() {
return length == 0;
}
/**
* @param info
*/
public void addGraph(int info) {
for (int i = 0; i < length; i++) {
if (list[i] == null) {
GraphList g = new GraphList();
g.addNode(info);
list[i] = g;
break;
}
}
}
/**
* 添加有向图的一条边
* @param vfrom
* @param vto
* @param value 权
*/
public void addSide(int vfrom, int vto, int value) {
list[vfrom].addNode(vto);
weight[vfrom][vto] = value;
}
/**
* 添加无向图的一条边
* @param vfrom
* @param vto
* @param value
*/
public void addDoubleSide(int vfrom, int vto, int value) {
list[vfrom].addNode(vto);
list[vto].addNode(vfrom);
weight[vfrom][vto] = value;
weight[vto][vfrom] = value;
}
/**
* 打印图
*/
public void print() {
for (int i = 0; i < length; i++) {
GraphNode current = list[i].first;
while (current != null) {
System.out.print(current.info + " ");
current = current.link;
}
System.out.println();
}
}
/**
* Dijkstra
*
* @param v
* @return int[]
*/
public int[] shortPath(int v) {
int[] shortPath = new int[length];
boolean[] weightFound = new boolean[length];
for (int i = 0; i < length; i++) {
// 趋近无穷
shortPath[i] = 9999;
weightFound[i] = false;
}
shortPath[v] = 0;
weightFound[v] = true;
Queue queue = new Queue();
queue.addQueue(v);
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!weightFound[w]) {
if (shortPath[w] > shortPath[temp] + weight[temp][w]) {
shortPath[w] = shortPath[temp] + weight[temp][w];
}
}
}
int minWeightNode = 0;
for (int i = 0; i < length; i++) {
if (!weightFound[i]) {
minWeightNode = i;
for (int j = 0; j < length; j++) {
if (!weightFound[j]) {
if (shortPath[j] < shortPath[minWeightNode]) {
minWeightNode = j;
}
}
}
break;
}
}
if (!weightFound[minWeightNode]) {
weightFound[minWeightNode] = true;
queue.addQueue(minWeightNode);
}
}
return shortPath;
}
/**
* 普里姆最小生成树
*
* @param v
*/
public void primMST(int v) {
boolean[] visited = new boolean[length];
for (int i = 0; i < length; i++) {
visited[i] = false;
for (int j = 0; j < length; j++) {
lightSide[i][j] = 9999;
}
}
visited[v] = true;
Queue queue = new Queue();
queue.addQueue(v);
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
lightSide[temp][w] = weight[temp][w];
}
// 找到最小边
int minSide = 0;
int vfrom =0;
int vto = 0;
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (visited[i] && visited[j]) {
continue;
}
minSide = lightSide[i][j];
vfrom = i;
vto = j;
for (int k = 0; k < length; k++) {
for (int l = 0; l < length; l++) {
if (visited[k] && visited[l]) {
continue;
}
if (lightSide[k][l] < minSide) {
minSide = lightSide[k][l];
vfrom = k;
vto = l;
}
}
}
break;
}
}
//将最小边的节点vto设为true，并输出vto
if (!visited[vto]) {
visited[vto] = true;
System.out.print(vfrom+"==>" + vto+", ");
queue.addQueue(vto);
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
Graph graph = new Graph(6);
System.out.println("create graph start");
for (int i = 0; i < 6; i++) {
graph.addGraph(i);
}
graph.addDoubleSide(0, 1, 1);
graph.addDoubleSide(0, 2, 8);
graph.addDoubleSide(0, 3, 7);
graph.addDoubleSide(1, 2, 5);
graph.addDoubleSide(1, 4, 5);
graph.addDoubleSide(1, 5, 2);
graph.addDoubleSide(1, 3, 10);
graph.addDoubleSide(2, 4, 3);
graph.addDoubleSide(4, 5, 6);
graph.addDoubleSide(5, 3, 4);
graph.print();
System.out.println("create graph end");
graph.primMST(3);
}
}替leon发的 |
 |
leon_a
2007-07-04
补充方法：克鲁斯卡尔最小生成树
增加属性：等价类 修改初始化权重
package graph;
/**
* @author B.Chen
*
*/
public class Graph {
/**
* 节点数
*/
private int length;
/**
* 链表
*/
private GraphList[] list;
/**
* 权集
*/
private int[][] weight;
/**
* 轻边集
*/
private int[][] lightSide;
/**
* 等价类
*/
private int[] replaceValue;
/**
* @param length
*/
public Graph(int length) {
this.length = length;
list = new GraphList[length];
weight = new int[length][length];
lightSide = new int[length][length];
replaceValue = new int[length];
for(int i=0;i<length;i++) {
replaceValue[i] = i;
for(int j=0;j<length;j++) {
weight[i][j] = 9999;
}
}
}
/**
* @param v
*/
public void dfs(int v) {
int[] ajd = new int[length];
int ajdlength = list[v].getAjd(ajd);
list[v].visitable = true;
System.out.print(v + " ");
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!list[w].visitable) {
dfs(w);
}
}
}
/**
* 深度优先遍历
*/
public void dfsTravel() {
for (int i = 0; i < length; i++) {
list[i].visitable = false;
}
for (int i = 0; i < length; i++) {
if (!list[i].visitable) {
dfs(i);
}
}
}
/**
* 广度优先遍历
*/
public void bfsTravel() {
for (int i = 0; i < length; i++) {
list[i].visitable = false;
}
bfs();
}
/**
* bfs
*/
private void bfs() {
Queue queue = new Queue();
for (int index = 0; index < length; index++) {
if (!list[index].visitable) {
queue.addQueue(index);
list[index].visitable = true;
System.out.print(index + " ");
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] adj = new int[length];
int ajdlength = list[temp].getAjd(adj);
for (int i = 0; i < ajdlength; i++) {
int w = adj[i];
if (!list[w].visitable) {
System.out.print(w + " ");
queue.addQueue(w);
list[w].visitable = true;
}
}
}
}
}
}
/**
* 长度
*/
public void length() {
System.out.println(length);
}
/**
* @return boolean
*/
public boolean isEmpty() {
return length == 0;
}
/**
* @param info
*/
public void addGraph(int info) {
for (int i = 0; i < length; i++) {
if (list[i] == null) {
GraphList g = new GraphList();
g.addNode(info);
list[i] = g;
break;
}
}
}
/**
* 添加有向图的一条边
* @param vfrom
* @param vto
* @param value 权
*/
public void addSide(int vfrom, int vto, int value) {
list[vfrom].addNode(vto);
weight[vfrom][vto] = value;
}
/**
* 添加无向图的一条边
* @param vfrom
* @param vto
* @param value
*/
public void addDoubleSide(int vfrom, int vto, int value) {
list[vfrom].addNode(vto);
list[vto].addNode(vfrom);
weight[vfrom][vto] = value;
weight[vto][vfrom] = value;
}
/**
* 打印图
*/
public void print() {
for (int i = 0; i < length; i++) {
GraphNode current = list[i].first;
while (current != null) {
System.out.print(current.info + " ");
current = current.link;
}
System.out.println();
}
}
/**
* Dijkstra
*
* @param v
* @return int[]
*/
public int[] shortPath(int v) {
int[] shortPath = new int[length];
boolean[] weightFound = new boolean[length];
for (int i = 0; i < length; i++) {
// 趋近无穷
shortPath[i] = 9999;
weightFound[i] = false;
}
shortPath[v] = 0;
weightFound[v] = true;
Queue queue = new Queue();
queue.addQueue(v);
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!weightFound[w]) {
if (shortPath[w] > shortPath[temp] + weight[temp][w]) {
shortPath[w] = shortPath[temp] + weight[temp][w];
}
}
}
int minWeightNode = 0;
for (int i = 0; i < length; i++) {
if (!weightFound[i]) {
minWeightNode = i;
for (int j = 0; j < length; j++) {
if (!weightFound[j]) {
if (shortPath[j] < shortPath[minWeightNode]) {
minWeightNode = j;
}
}
}
break;
}
}
if (!weightFound[minWeightNode]) {
weightFound[minWeightNode] = true;
queue.addQueue(minWeightNode);
}
}
return shortPath;
}
/**
* 普里姆最小生成树
*
* @param v
*/
public void primMST(int v) {
boolean[] visited = new boolean[length];
for (int i = 0; i < length; i++) {
visited[i] = false;
for (int j = 0; j < length; j++) {
lightSide[i][j] = 9999;
}
}
visited[v] = true;
Queue queue = new Queue();
queue.addQueue(v);
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
lightSide[temp][w] = weight[temp][w];
}
// 找到最小边
int minSide = 0;
int vfrom =0;
int vto = 0;
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (visited[i] && visited[j]) {
continue;
}
minSide = lightSide[i][j];
vfrom = i;
vto = j;
for (int k = 0; k < length; k++) {
for (int l = 0; l < length; l++) {
if (visited[k] && visited[l]) {
continue;
}
if (lightSide[k][l] < minSide) {
minSide = lightSide[k][l];
vfrom = k;
vto = l;
}
}
}
break;
}
}
//将最小边的节点vto设为true，并输出vto
if (!visited[vto]) {
visited[vto] = true;
System.out.print(vfrom+"==>" + vto+", ");
queue.addQueue(vto);
}
}
}
/**
* 克鲁斯卡尔最小生成树
*/
public void kruskalMST() {
int m = 0;
while (m < length - 1) {
// 找到最小边
int minSide = 0;
int vfrom = 0;
int vto = 0;
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (replaceValue[i] == replaceValue[j]) {
continue;
}
minSide = weight[i][j];
vfrom = i;
vto = j;
for (int k = 0; k < length; k++) {
for (int l = 0; l < length; l++) {
if (replaceValue[k] == replaceValue[l]) {
continue;
}
if (weight[k][l] < minSide) {
minSide = weight[k][l];
vfrom = k;
vto = l;
}
}
}
break;
}
}
if (replaceValue[vfrom] != replaceValue[vto]) {
System.out.print(vfrom + "==>" + vto + ", ");
for (int i = 0; i < length; i++) {
if (replaceValue[i] == replaceValue[vfrom]) {
replaceValue[i] = replaceValue[vto];
}
}
m++;
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
Graph graph = new Graph(6);
System.out.println("create graph start");
for (int i = 0; i < 6; i++) {
graph.addGraph(i);
}
graph.addDoubleSide(0, 1, 1);
graph.addDoubleSide(0, 2, 8);
graph.addDoubleSide(0, 3, 7);
graph.addDoubleSide(1, 2, 5);
graph.addDoubleSide(1, 4, 5);
graph.addDoubleSide(1, 5, 4);
graph.addDoubleSide(1, 3, 10);
graph.addDoubleSide(2, 4, 3);
graph.addDoubleSide(4, 5, 6);
graph.addDoubleSide(5, 3, 2);
graph.print();
System.out.println("create graph end");
graph.kruskalMST();
}
}
|
|
leon_a
2007-07-05
补充一点关于版权的东西，原创文章，转载请注明作者与原文链接
|
|
leon_a
2007-07-06
对最短路径的一种改进，记录从v到u经过的边以及之间的最短路径
/**
* Dijkstra
*
* @param v
* @param u
* @return int
*/
public int shortPath(int v,int u) {
int[] shortPath = new int[length];
boolean[] weightFound = new boolean[length];
int[] previous = new int[length];
for (int i = 0; i < length; i++) {
// 趋近无穷
shortPath[i] = 9999;
previous[i] = 9999;
weightFound[i] = false;
}
shortPath[v] = 0;
weightFound[v] = true;
Queue queue = new Queue();
queue.addQueue(v);
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!weightFound[w]) {
if (shortPath[w] > shortPath[temp] + weight[temp][w]) {
shortPath[w] = shortPath[temp] + weight[temp][w];
previous[w] = temp;
}
}
}
int minWeightNode = 0;
for (int i = 0; i < length; i++) {
if (!weightFound[i]) {
minWeightNode = i;
for (int j = 0; j < length; j++) {
if (!weightFound[j]) {
if (shortPath[j] < shortPath[minWeightNode]) {
minWeightNode = j;
}
}
}
break;
}
}
if (!weightFound[minWeightNode]) {
weightFound[minWeightNode] = true;
queue.addQueue(minWeightNode);
}
}
//记录经过的边
Stack stack = new Stack();
int s = u;
while(previous[s] != 9999) {
stack.push(s);
s = previous[s];
}
stack.push(v);
while(stack.stackTop.link != null) {
int from = stack.top();
stack.pop();
int to = stack.top();
System.out.print(from+"==>"+to+", ");
}
return shortPath[u];
}
|
|
leon_a
2007-07-06
补充方法:弗洛伊德最小路径。floyd算法原理果然很简单！！！感叹前人的智慧
/**
* 佛洛伊德最短路径
*
* @param v
* @return int[]
*/
public int[] floydShortPath(int v) {
// 初始化矩阵
int[][] spath = new int[length][length];
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (i == j) {
spath[i][j] = 0;
} else {
spath[i][j] = weight[i][j];
}
}
}
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
for (int k = 0; k < length; k++) {
if (spath[i][j] + spath[k][i] < spath[j][k]) {
spath[j][k] = spath[i][j] + spath[k][i];
}
}
}
}
int[] resultArray = new int[length];
for (int i = 0; i < length; i++) {
resultArray[i] = spath[v][i];
}
return resultArray;
}
|
|
leon_a
2007-07-06
到此为止，与图有关的算法实现的差不多了，还有AOE网和拓扑排序，这两个实现起来非常简单，简单说说原理就可以
AOE网是求两点之间最大路径，应用迪杰科斯特算法稍微改进一下就OK 拓扑排序可以应用DFS来做。 相关的算法正确性证明，我就不献丑了，我的数学功底很差。 然后准备做树有关的数据结构 链表，队列，堆栈的数据结构太简单就不写了 |
|
leon_a
2007-07-10
首先抛块砖头,然后再慢慢写
Tree开始了！！
package tree;
public class TreeNode {
TreeNode llink;
TreeNode rlink;
int info;
}
|
|
leon_a
2007-07-10
懒了一天，现在给出删除节点代码
package tree;
public class Tree {
TreeNode root;
public Tree() {
}
public boolean isEmpty() {
return root == null;
}
// 插入
public void insertBinaryTree(int info) {
TreeNode node = new TreeNode();
node.info = info;
if (root == null) {
root = node;
} else {
TreeNode currentNode = root;
TreeNode parent;
while (currentNode != null) {
parent = currentNode;
if (info > currentNode.info) {
currentNode = currentNode.rlink;
if (currentNode == null) {
parent.rlink = node;
}
} else if (info < currentNode.info) {
currentNode = currentNode.llink;
if (currentNode == null) {
parent.llink = node;
}
}
}
}
}
// 删除
public void treeDelete(int info) {
TreeNode tNode = serach(info);
TreeNode deleteNode = new TreeNode();
TreeNode dNodeChild = new TreeNode();
if (tNode == null) {
System.out.println("node is not exists");
} else if (tNode.llink == null || tNode.rlink == null) {
deleteNode = tNode;
} else {
deleteNode = treeSuccessor(tNode);
}
if (deleteNode.llink != null) {
dNodeChild = deleteNode.llink;
} else {
dNodeChild = deleteNode.rlink;
}
if (getFatherNode(deleteNode) == null) {
root = dNodeChild;
} else {
if (deleteNode == getFatherNode(deleteNode).llink) {
getFatherNode(deleteNode).llink = dNodeChild;
} else {
getFatherNode(deleteNode).rlink = dNodeChild;
}
}
if (deleteNode != tNode) {
tNode.info = deleteNode.info;
}
}
// 搜索
public TreeNode serach(int info) {
return treeSerach(root, info);
}
// 搜索
public TreeNode treeSerach(TreeNode tNode, int info) {
if (tNode == null || tNode.info == info) {
return tNode;
}
if (info < tNode.info) {
return treeSerach(tNode.llink, info);
} else {
return treeSerach(tNode.rlink, info);
}
}
// 最大节点
public TreeNode treeMaxiMum(TreeNode tNode) {
while (tNode.rlink != null) {
tNode = tNode.rlink;
}
return tNode;
}
// 最小节点
public TreeNode treeMiniMun(TreeNode tNode) {
while (tNode.llink != null) {
tNode = tNode.llink;
}
return tNode;
}
// 找后继
public TreeNode treeSuccessor(TreeNode tNode) {
if (tNode.rlink != null) {
return treeMiniMun(tNode.rlink);
}
TreeNode currentNode = getFatherNode(tNode);
while (currentNode != null && tNode == currentNode.rlink) {
tNode = currentNode;
currentNode = getFatherNode(tNode);
}
return currentNode;
}
// 找前驱
public TreeNode treePrecursor(TreeNode tNode) {
if (tNode.llink != null) {
return treeMaxiMum(tNode.llink);
}
TreeNode currentNode = getFatherNode(tNode);
while (currentNode != null && tNode == currentNode.llink) {
tNode = currentNode;
currentNode = getFatherNode(tNode);
}
return currentNode;
}
// 找节点的父节点
public TreeNode getFatherNode(TreeNode tNode) {
TreeNode current = root;
TreeNode trailCurrent = null;
while (current != null) {
if (current.info == tNode.info) {
break;
}
trailCurrent = current;
if (tNode.info < current.info) {
current = current.llink;
} else {
current = current.rlink;
}
}
return trailCurrent;
}
// 中序遍历
public void inOrder(TreeNode tNode) {
if (tNode != null) {
inOrder(tNode.llink);
System.out.print(tNode.info + " ");
inOrder(tNode.rlink);
}
}
// 打印树
public void printTree() {
System.out.println("inOrder");
inOrder(root);
System.out.println();
System.out.println("preOrder");
preOrder(root);
System.out.println();
System.out.println("postOrder");
postOrder(root);
System.out.println();
}
// 前序遍历
public void preOrder(TreeNode tNode) {
if (tNode != null) {
System.out.print(tNode.info + " ");
preOrder(tNode.llink);
preOrder(tNode.rlink);
}
}
// 后序遍历
public void postOrder(TreeNode tNode) {
if (tNode != null) {
postOrder(tNode.llink);
postOrder(tNode.rlink);
System.out.print(tNode.info + " ");
}
}
public static void main(String[] args) {
Tree tree = new Tree();
System.out.println("insert tree start");
tree.insertBinaryTree(15);
tree.insertBinaryTree(5);
tree.insertBinaryTree(16);
tree.insertBinaryTree(3);
tree.insertBinaryTree(12);
tree.insertBinaryTree(20);
tree.insertBinaryTree(10);
tree.insertBinaryTree(13);
tree.insertBinaryTree(18);
tree.insertBinaryTree(23);
tree.insertBinaryTree(6);
tree.insertBinaryTree(7);
System.out.println("insert tree end");
System.out.println("print tree start");
tree.treeDelete(15);
tree.printTree();
System.out.println("print tree end");
}
}
|
|
leon_a
2007-07-12
至此，二叉树的基本操作已经结束（霍夫曼树过两天写）。
然后开始B树与AVL平衡树的数据结构实现。 最近在研究乱七八糟的问题～～～，拖下了数据结构的学习，郁闷。 |
|
leon_a
2007-07-13
恩，今天心情不错，哈夫曼树奉上,有点垃圾，回家继续改
package tree;
/**
* @author B.Chen
*/
public class HuffmanTree {
/**
* 根节点
*/
public TreeNode root;
/**
* 数组下表
*/
public int nodeSize;
/**
* 长度
*/
public int length;
/**
* 哈夫曼节点数组
*/
public TreeNode[] nodeList;
/**
* 访问控制
*/
public boolean[] visited;
/**
* @param length
*/
public HuffmanTree(int length) {
this.length = length;
nodeList = new TreeNode[2 * length-1];
visited = new boolean[2*length-1];
}
/**
* @param info
*/
public void addNode(int info) {
TreeNode tNode = new TreeNode();
tNode.info = info;
if (nodeSize < length) {
nodeList[nodeSize++] = tNode;
} else {
System.out.println("out of size");
}
}
/**
* 构造哈夫曼树
*/
public void createHuffmanTree() {
int j = length;
while (nodeList[2*length -2] == null) {
TreeNode lNode = getMiniMumNode();
TreeNode rNode = getMiniMumNode();
TreeNode tNode = new TreeNode();
System.out.println(lNode.info + " " + rNode.info);
tNode.llink = lNode;
tNode.rlink = rNode;
tNode.info = lNode.info + rNode.info;
nodeList[j++] = tNode;
}
root = nodeList[2 * length - 2];
}
/**
* @return TreeNode
*/
public TreeNode getMiniMumNode() {
TreeNode tNode = null;
int size = 0;
for(int i=0;i<2*length-1;i++) {
if(!visited[i] && nodeList[i] != null) {
tNode = nodeList[i];
size = i;
for(int j=0;j<2*length-1;j++) {
if(!visited[j] && nodeList[j] != null) {
if(tNode.info > nodeList[j].info) {
tNode = nodeList[j];
size = j;
}
}
}
}
}
visited[size] = true;
return tNode;
}
/**
* 中序遍历
*
* @param tNode
*/
public void inOrder(TreeNode tNode) {
if (tNode != null) {
inOrder(tNode.llink);
System.out.print(tNode.info + " ");
inOrder(tNode.rlink);
}
}
/**
* 打印
*/
public void printHuffmanTree() {
System.out.println("inOrder");
inOrder(root);
}
/**
* @param args
*/
public static void main(String[] args) {
HuffmanTree hTree = new HuffmanTree(6);
hTree.addNode(4);
hTree.addNode(4);
hTree.addNode(4);
hTree.addNode(4);
hTree.addNode(5);
hTree.addNode(6);
hTree.createHuffmanTree();
hTree.printHuffmanTree();
}
}
|
