2008-03-01
数据结构（java实现）
1 树与哈夫曼树
在8×8的棋盘上分布着n个骑士，他们想约在某一个格中聚会。骑士每天可以像国际象棋中的马那样移动一次，可以从中间向8个方向移动，请你计算n个骑士的最早聚会地点和要走多少天，要求尽早聚会，且n个人走的总步数最少，先到聚会地点的骑士可以不再移动等待其他的骑士。
从键盘输入n（0<n<=64），然后一次输入n个其实的初始位置xi，yi（0<=xi,y<=7）。屏幕输出以空格分割的三个数，分别为聚会的点（x，y） 以及要走的天数。
○ ○
○ ○
◎
○ ○
○ ○
骑士走法（中间为起始位置，空为走到位置）
下面开始写数据结构的基本代码：
1 节点类
2 邻接表表示图的链表类
3 图类
4 队列
5 堆栈
6 图的最短路径算法
8 普里姆最小生成树
9 克鲁斯卡尔最小生成树
增加属性：等价类
修改初始化权重
10 对最短路径的一种改进，记录从v到u经过的边以及之间的最短路径
11 弗洛伊德最小路径。floyd算法原理果然很简单！！！
以上写完了图下面开始Tree
12 Tree
13 删除节点
以上是二叉树的基本操作
14 哈夫曼树
全排列是一种比较烦人的东西。本文讨论如何在不使用递归的情况下，让全排列结果能够被遍历（也就是实现 Iterator 接口），使得全排列的提供者能随时提供“下一个”全排列结果，直到给出所有的排列。
通常全排列是不可排序的，因为不同的遍历方式会按不同的顺序得到结果（如交换法、滚动法等）。我们需要选择一种方式，每次枚举都能得到唯一的结果，绝不重复。因为只有这样的方式才能用来遍历。那就是：
全排列树。想象一下，树中的每个节点就是一个全排列结果，其子节点是将其交换变化而来的。举个例子，
根节点为 (1, 2, 3) 的树，其一级子节点就是 (1, 2, 3) (2, 1, 3) (3, 1, 2) 三个，分别是从排列中的 [0]-[0] 交换、[0]-[1] 交换和 [0]-[2]交换得来的。而二级子节点，排列中的位置 [0] 不变，从 [1] 开始和其他位置交换。(2, 1, 3) 的子节点为 (2, 1, 3) 和 (2, 3, 1) 两个。以此类推到下一级，直到无法交换位置为止。实际上，(1, 2, 3) 的全排列树一共就是三层。
你可能看到了：这里不是有重复的节点了吗？没关系。虽然枝节点有重复，但叶子节点是绝无重复的。我们只需要遍历这棵树的最底层，就能得到所有全排列。
遍历的时候，如何确定“上一个”和“下一个”叶子节点的位置呢？用一个很直观的表示法：每个节点的子节点都从 0 开始标上号，根节点就不用标号了，然后根据叶子节点的路径将标号组合成一个数组，就是每个节点的位置。例如上面那棵树中的叶子节点(2, 1, 3)，位置就是 {1, 0}。它的下一个位置就是 {1, 1}，再下一个位置是 {2, 0}，不信把整个树画出来自己对对看。
实际上，因为叶子节点的位置都是绝对的，我就不一定非要从第一个结果来排起。给出任意一个排列结果，我都可以找到它在这棵树中的位置，然后直接求得下一个位置和下一个位置的排列结果。
基本的思路就是这些，然后就是用代码来实现。至于怎么思考实现的就略去了，下面是代码：
使用方法：
package tree;
public class TreeNode {
TreeNode llink;
TreeNode rlink;
int info;
}
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");
}
}
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();
}
}
在8×8的棋盘上分布着n个骑士，他们想约在某一个格中聚会。骑士每天可以像国际象棋中的马那样移动一次，可以从中间向8个方向移动，请你计算n个骑士的最早聚会地点和要走多少天，要求尽早聚会，且n个人走的总步数最少，先到聚会地点的骑士可以不再移动等待其他的骑士。
从键盘输入n（0<n<=64），然后一次输入n个其实的初始位置xi，yi（0<=xi,y<=7）。屏幕输出以空格分割的三个数，分别为聚会的点（x，y） 以及要走的天数。
○ ○
○ ○
◎
○ ○
○ ○
骑士走法（中间为起始位置，空为走到位置）
package convex;
public class Point {
public int x, y;
public Point(int x, int y) {
if (x > 7 || y > 7) {
throw new RuntimeException("out of matrix");
}
this.x = x;
this.y = y;
}
public String toString() {
return "x=" + x + ",y=" + y;
}
}
package convex;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import convex.Point;
public class Algo {
private boolean[][] flg = new boolean[8][8];
private int[][] shortPath = new int[8][8];
//最短距离矩阵
public int[][] distanceSq(Point p1) {
djkst(p1);
return shortPath;
}
//BFS
private void djkst(Point p1) {
Point[] queue = new Point[64];
flg[p1.x][p1.y] = true;
queue[0] = p1;
int j=0;
int queueSize = 1;
while (j < queue.length) {
Point temp = queue[j];
Point[] list = getList(temp);
for(int i=0;i < list.length;i++) {
if(list[i] != null) {
Point w = list[i];
if (!flg[w.x][w.y]) {
shortPath[w.x][w.y] = shortPath[temp.x][temp.y] + 1;
queue[queueSize++] = w;
flg[w.x][w.y] = true;
}
}
}
j++;
}
}
//可行步数集
private static Point[] getList(Point point) {
Point[] list = new Point[8];
int length = 0;
if (point.x + 2 <= 7 && point.y + 1 <= 7) {
list[length++] = new Point(point.x + 2, point.y + 1);
}
if (point.x - 2 >= 0 && point.y - 1 >= 0) {
list[length++] = new Point(point.x - 2, point.y - 1);
}
if (point.x + 1 <= 7 && point.y + 2 <= 7) {
list[length++] = new Point(point.x + 1, point.y + 2);
}
if (point.x - 1 >= 0 && point.y - 2 >= 0) {
list[length++] = new Point(point.x - 1, point.y - 2);
}
if (point.x + 2 <= 7 && point.y - 1 >= 0) {
list[length++] = new Point(point.x + 2, point.y - 1);
}
if (point.x - 2 >= 0 && point.y + 1 <= 7) {
list[length++] = new Point(point.x - 2, point.y + 1);
}
if (point.x + 1 <= 7 && point.y - 2 >= 0) {
list[length++] = new Point(point.x + 1, point.y - 2);
}
if (point.x - 1 >= 0 && point.y + 2 <= 7) {
list[length++] = new Point(point.x - 1, point.y + 2);
}
return list;
}
public static int[] method(Point[] points, int i,int j,Object[] pointList) {
int maxDay = 0;
int distance = 0;
for(int k=0;k<pointList.length;k++) {
int day = ((int[][])pointList[k])[i][j];
distance += day;
if(maxDay<day) {
maxDay = day;
}
}
return new int[]{maxDay,distance};
}
public static void main(String[] args) throws IOException {
//数据输入
//数据输入格式：第一个数字是骑士n，第2，3个数字是第一个骑士的坐标，依次类推。
//每个数字之间以空格区分
BufferedReader stdin =
new BufferedReader(
new InputStreamReader(System.in));
String line = stdin.readLine();
StringTokenizer st = new StringTokenizer(line);
int pointLength = Integer.parseInt(st.nextToken());
Point[] points = new Point[pointLength];
for(int i=0;i<points.length;i++) {
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
points[i] = new Point(x,y);
}
Object[] pointList = new Object[points.length];
for (int j = 0; j < points.length; j++) {
pointList[j] = new Algo().distanceSq(points[j]);
}
int minDay = 999999999;
int minDistance = 999999999;
for(int i=0;i<7;i++) {
for(int j=0;j<7;j++) {
int[] result = Algo.method(points, i,j,pointList);
//找最短天数，最短天数相同，找最短距离
if (minDay > result[0]) {
minDay = result[0];
minDistance = result[1];
} else if(minDay == result[0]) {
if(minDistance > result[1]) {
minDistance = result[1];
}
}
}
}
for(int i=0;i<7;i++) {
for(int j=0;j<7;j++) {
int[] result = Algo.method(points, i,j,pointList);
if(minDay == result[0] && minDistance == result[1]) {
System.out.println(i+" " + j +" "+ minDay);
}
}
}
}
}
下面开始写数据结构的基本代码：
1 节点类
package graph;
public class GraphNode {
public GraphNode link;
public int info;
}
2 邻接表表示图的链表类
package graph;
public class GraphList {
public GraphNode first;
public GraphNode last;
public boolean visitable;
public int getAjd(int[] ajd) {
GraphNode current = first;
int length = 0;
while(current != null) {
ajd[length++] = current.info;
current = current.link;
}
return length;
}
public void addNode(int v) {
GraphNode node = new GraphNode();
node.info = v;
if(first == null) {
first = node;
last = node;
} else {
last.link = node;
last = node;
}
}
}
3 图类
package graph;
public class Graph {
private int length;
private GraphList[] list;
public Graph(int length) {
this.length = length;
list = new GraphList[length];
}
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();
}
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);
}
public boolean isEmpty() {
return length == 0;
}
//添加节点
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;
}
}
}
//添加边
public void addSide(int vfrom,int vto) {
list[vfrom].addNode(vto);
}
//打印图
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();
}
}
public static void main(String[] args) {
Graph graph = new Graph(11);
System.out.println("create graph start");
for(int i=0;i<11;i++) {
graph.addGraph(i);
}
graph.addSide(0, 1);
graph.addSide(0, 5);
graph.addSide(1, 2);
graph.addSide(1, 3);
graph.addSide(1, 5);
graph.addSide(2, 4);
graph.addSide(4, 3);
graph.addSide(5, 6);
graph.addSide(6, 8 );
graph.addSide(7, 3);
graph.addSide(7, 8 );
graph.addSide(8, 10);
graph.addSide(9, 4);
graph.addSide(9, 7);
graph.addSide(9, 10);
graph.print();
System.out.println("create graph end");
graph.bfsTravel();
}
}
4 队列
package graph;
public class Queue {
public GraphNode first;
public GraphNode last;
public int count;
public void addQueue(int info) {
GraphNode node = new GraphNode();
node.info = info;
if(first == null) {
first = node;
last = node;
} else {
last.link = node;
last = last.link;
}
count++;
}
public void deleteQueue() {
if(first == null) {
System.out.println("null queue");
} else {
first = first.link;
count--;
}
}
public boolean isEmpty() {
return count == 0;
}
public int front() {
if(first == null) {
return -1;
}
return first.info;
}
public int back() {
if(last == null) {
return -1;
}
return last.info;
}
}
5 堆栈
package graph;
public class Stack {
public GraphNode stackTop;
public int count;
public void push(int info) {
GraphNode node = new GraphNode();
node.info = info;
node.link = stackTop;
stackTop = node;
count++;
}
public void pop() {
if(stackTop == null) {
System.out.println("null stack");
} else {
stackTop = stackTop.link;
count--;
}
}
public int top() {
if(stackTop == null) {
return -1;
}
return stackTop.info;
}
}
6 图的最短路径算法
package graph;
public class Graph {
private int length;
private GraphList[] list;
private int[][] weight;
public Graph(int length) {
this.length = length;
list = new GraphList[length];
weight = new int[length][length];
}
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();
}
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[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!list[w].visitable) {
System.out.print(w + " ");
queue.addQueue(w);
list[w].visitable = true;
}
}
}
}
}
}
// 最短路径
private 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;
}
// 长度
public void length() {
System.out.println(length);
}
public boolean isEmpty() {
return length == 0;
}
// 添加节点
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;
}
}
}
// 添加边
public void addSide(int vfrom, int vto, int value) {
list[vfrom].addNode(vto);
weight[vfrom][vto] = 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();
}
}
public static void main(String[] args) {
Graph graph = new Graph(5);
System.out.println("create graph start");
for (int i = 0; i < 5; i++) {
graph.addGraph(i);
}
graph.addSide(0, 1, 16);
graph.addSide(0, 3, 2);
graph.addSide(0, 4, 3);
graph.addSide(3, 4, 7);
graph.addSide(3, 1, 12);
graph.addSide(4, 1, 10);
graph.addSide(4, 3, 5);
graph.addSide(4, 2, 4);
graph.addSide(2, 1, 3);
graph.addSide(1, 2, 5);
graph.print();
System.out.println("create graph end");
int[] shortPath = graph.shortPath(0);
for (int i = 0; i < shortPath.length; i++) {
System.out.print(shortPath[i] + " ");
}
}
}
8 普里姆最小生成树
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);
}
}
9 克鲁斯卡尔最小生成树
增加属性：等价类
修改初始化权重
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();
}
}
10 对最短路径的一种改进，记录从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];
}
11 弗洛伊德最小路径。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;
}
以上写完了图下面开始Tree
12 Tree
package tree;
public class TreeNode {
TreeNode llink;
TreeNode rlink;
int info;
}
13 删除节点
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");
}
}
以上是二叉树的基本操作
14 哈夫曼树
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();
}
}
全排列是一种比较烦人的东西。本文讨论如何在不使用递归的情况下，让全排列结果能够被遍历（也就是实现 Iterator 接口），使得全排列的提供者能随时提供“下一个”全排列结果，直到给出所有的排列。
通常全排列是不可排序的，因为不同的遍历方式会按不同的顺序得到结果（如交换法、滚动法等）。我们需要选择一种方式，每次枚举都能得到唯一的结果，绝不重复。因为只有这样的方式才能用来遍历。那就是：
全排列树。想象一下，树中的每个节点就是一个全排列结果，其子节点是将其交换变化而来的。举个例子，
根节点为 (1, 2, 3) 的树，其一级子节点就是 (1, 2, 3) (2, 1, 3) (3, 1, 2) 三个，分别是从排列中的 [0]-[0] 交换、[0]-[1] 交换和 [0]-[2]交换得来的。而二级子节点，排列中的位置 [0] 不变，从 [1] 开始和其他位置交换。(2, 1, 3) 的子节点为 (2, 1, 3) 和 (2, 3, 1) 两个。以此类推到下一级，直到无法交换位置为止。实际上，(1, 2, 3) 的全排列树一共就是三层。
你可能看到了：这里不是有重复的节点了吗？没关系。虽然枝节点有重复，但叶子节点是绝无重复的。我们只需要遍历这棵树的最底层，就能得到所有全排列。
遍历的时候，如何确定“上一个”和“下一个”叶子节点的位置呢？用一个很直观的表示法：每个节点的子节点都从 0 开始标上号，根节点就不用标号了，然后根据叶子节点的路径将标号组合成一个数组，就是每个节点的位置。例如上面那棵树中的叶子节点(2, 1, 3)，位置就是 {1, 0}。它的下一个位置就是 {1, 1}，再下一个位置是 {2, 0}，不信把整个树画出来自己对对看。
实际上，因为叶子节点的位置都是绝对的，我就不一定非要从第一个结果来排起。给出任意一个排列结果，我都可以找到它在这棵树中的位置，然后直接求得下一个位置和下一个位置的排列结果。
基本的思路就是这些，然后就是用代码来实现。至于怎么思考实现的就略去了，下面是代码：
import sun.reflect.generics.reflectiveObjects.NotImplementedException;
import java.util.Iterator;
/**
* 全排列树 -- 可遍历的全排列
*/
class SortTree implements Iterator {
private int level;
private int[] defaultArr; // {1, 2, 3, 4, 5, ...} 这样一个数组
private int[] currentPosition;
public SortTree(int level) {
this.level = level;
init();
}
private void init() {
defaultArr = new int[level];
for (int i = 0; i < level; i++) {
defaultArr[i] = i;
}
currentPosition = getBeforeStartPosition();
}
/**
* 获得指定位置的全排列
*
* @param position 全排列在树中的位置
*
* @return 处于指定位置的全排列
*/
public int[] getValue(int[] position) {
int[] cloned = defaultArr.clone();
if (position.length != level - 1) {
System.out.println("invalid position level");
return new int[0];
}
for (int i = 0; i < position.length; i++) {
swap(cloned, i, i + position[i]);
}
return cloned;
}
/**
* 获得指定的全排列的位置
*
* @param value 全排列中的一项
*
* @return 指定的项在全排列树中的位置
*/
public int[] getPosition(int[] value) {
int[] cloned = defaultArr.clone();
int[] position = new int[value.length - 1];
for (int i = 0; i < value.length - 1; i++) {
int pointer = 0;
if (value[i] == cloned[i]) {
position[i] = 0;
} else {
pointer++;
while (pointer < value.length) {
if (value[i] == cloned[pointer]) {
swap(cloned, i, pointer);
position[i] = pointer - i;
}
pointer++;
}
}
}
return position;
}
/**
* 获得下一个位置
*
* @param position 当前位置
*
* @return 下一个位置
*/
public int[] getNextPosition(int[] position) {
int[] result = position.clone();
for (int i = result.length - 1; i >= 0; i--) {
int upper = result.length - i;
if (result[i] + 1 <= upper) {
result[i] += 1;
break;
} else {
result[i] = 0;
}
}
return result;
}
/**
* 是否还有下一个位置
*
* @param position 当前位置
*
* @return 如果还有则返回 true。
*/
public boolean hasNextPosition(int[] position) {
for (int i = 0; i < position.length; i++) {
if (position[i] != defaultArr.length - i - 1) {
return true;
}
}
return false;
}
/**
* 获得第一个位置之前的位置
*
* @return 第一个位置之前的位置
*/
public int[] getBeforeStartPosition() {
int[] position = new int[defaultArr.length - 1];
position[position.length - 1] = -1;
return position;
}
private void swap(int[] ints, int a, int b) {
int t = ints[a];
ints[a] = ints[b];
ints[b] = t;
}
public boolean hasNext() {
return hasNextPosition(currentPosition);
}
public Object next() {
currentPosition = getNextPosition(currentPosition);
return getValue(currentPosition);
}
public void remove() {
throw new NotImplementedException();
}
}
使用方法：
SortTree tree = new SortTree(6);
int counter = 0;
while (tree.hasNext()) {
int[] sort = (int[]) tree.next();
printArray(sort);
counter++;
}
System.out.println("一共 " + counter + " 个结果");
评论排行榜