我有一个节点列表,其中每个节点都属于一棵或多棵树。(他们不一定有共同的祖先)
我想按照深度优先搜索时找到的相同顺序对节点进行排序。
假设我有一个用于将树根排序在一起的谓词,还有一个用于将共同父级的子级排序在一起的谓词。每个节点都有一个 Parent 访问器和一个 children 枚举器。出于性能原因(如果可能),我想避免使用 Children 枚举。
谓词传递给排序函数的伪代码可能是什么(如果节点 1 小于节点 2,谓词将返回布尔值)。
我有一个节点列表,其中每个节点都属于一棵或多棵树。(他们不一定有共同的祖先)
我想按照深度优先搜索时找到的相同顺序对节点进行排序。
假设我有一个用于将树根排序在一起的谓词,还有一个用于将共同父级的子级排序在一起的谓词。每个节点都有一个 Parent 访问器和一个 children 枚举器。出于性能原因(如果可能),我想避免使用 Children 枚举。
谓词传递给排序函数的伪代码可能是什么(如果节点 1 小于节点 2,谓词将返回布尔值)。
我找到了一个简单的解决方案:
对于节点,有一个从根返回路径的函数。例如,在文件系统中,文件的路径可以是:c:\directory\file.txt,其中“C:”、“directory”和“file.txt”是父节点。
谓词只需将路径比较在一起,就像简单的字符串比较一样。路径不必是字符串,路径比较函数需要从根开始逐个比较路径元素,一旦路径元素不同就返回。
结果排序与深度优先搜索相同。
我认为,您需要在节点中存储有用的信息,因此谓词可以从一对未连接的节点中选择前面的节点。
这是我的(可能不是很聪明,甚至是工作)尝试:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
*
*/
public class SortingTree {
private static class Node implements Comparable<Node> {
private final String data;
private Node p, l, r;
private int ordinal = 0;
public Node(String data) {
this.data = data;
}
public Node setLeft(Node n) {
n.ordinal = ordinal + 1;
if (ordinal == 0)
n.ordinal = 2;
else
n.ordinal = ordinal + 2;
n.p = this;
return n;
}
public Node setRight(Node n) {
if (ordinal == 0)
n.ordinal = 1;
else
n.ordinal = ordinal + 4;
n.p = this;
return n;
}
public String toString() {
return data;
}
public int compareTo(Node o) {
// check if one of args is root
if (p == null && o.p != null) return -1;
if (p != null && o.p == null) return 1;
if (p == null && o.p == null) return 0;
// check if one of args is left subtree, while other is right
if (ordinal % 2 == 0 && o.ordinal % 2 == 1) return -1;
if (ordinal % 2 == 1 && o.ordinal % 2 == 0) return 1;
// if ordinals are the same, first element is the one which parent have bigger ordinal
if (ordinal == o.ordinal) {
return o.p.ordinal - p.ordinal;
}
return ordinal - o.ordinal;
}
}
public static void main(String[] args) {
List<Node> nodes = new ArrayList<Node>();
Node root = new Node("root"); nodes.add(root);
Node left = root.setLeft(new Node("A")); nodes.add(left);
Node leftLeft = left.setLeft(new Node("C")); nodes.add(leftLeft); nodes.add(leftLeft.setLeft(new Node("D")));
nodes.add(left.setRight(new Node("E")));
Node right = root.setRight(new Node("B")); nodes.add(right);
nodes.add(right.setLeft(new Node("F"))); nodes.add(right.setRight(new Node("G")));
Collections.sort(nodes);
System.out.println(nodes);
}
}