1
単一ルートツリー内の任意のノードから特殊条件を満たす前/次の葉ノードを見つける関数を書く必要があります。java alogrithm：ツリー内の任意のノードから特殊条件を満たす前/次の葉ノードを見つける
interface Node{
/** @return the Node's parent or null if Node is root */
Node getParent();
/** @return true if node is root */
boolean isRoot();
/** @return non-null array of child nodes (zero length for leaf nodes) */
Node[] getChildren();
/** @return the number of child nodes. If node is leaf, value is 0 */
int getChildCount();
}
そして：currentNodeは、ツリー内の任意のノードであり、Nodeは以下のように定義される
Node findNextLeafNode(Node currentNode, Condition condition);
Node findPretLeafNode(Node currentNode, Condition condition);
：
（親最初の順序で）APIは、このようなものになるだろうConditionインターフェイスは、指定された
Nodeに対して制約をチェックするセマンティクスを定義します。
interface Condition{
/** @return true if provided node meets the condition */
boolean check(Node node);
}
私の質問：
は、このような一般的なシナリオのための既存のライブラリやアルゴリズムがありますか？私は、スタックベースまたは再帰的アルゴリズムのいずれかにオープンしています。擬似コード、オープンソースライブラリへのリンク、またはあなた自身のコードを共有したいと思った場合は、感謝します。
（ない場合は、私は再び同じホイールを発明し、共有のために、後でそれをここに貼り付けるために時間を費やす必要があります。）
感謝。
----------------------------- getNext（）.........メソッドを書く
// currentNode must be descendant of root
public static Node getNextNode(Node currentNode, Node root)
{
// 1. if is has child, next is its first child
if (currentNode.getChildSize() > 0) {
return currentNode.getChildren()[0];
}
// 2. if it has no child, check if its is the last child of his parent
else {
// if it is root and has no children, return null
if (currentNode == root) {
return null;
}
// else should have parent which is or under root;
Node parent = currentNode.getParent();
int index = getIndex(currentNode);
if (!isLastofParent(currentNode)) {
// ----a. if not last, next is his parent's next
return currentNode.getParent().getChildren()[index + 1];
}
else {
// ----b. if it is the last one, return its parent's next right if there is. while until root
Node tmp = parent;
while (tmp != root) {
int parentIndex = getIndex(tmp);
if (!isLastofParent(tmp)) {
return tmp.getParent().getChildren()[parentIndex + 1];
}
tmp = tmp.getParent();
}
}
}
return null;
}
private static boolean isLastofParent(Node node)
{
if (getIndex(node) == node.getParent().getChildSize() - 1) {
return true;
}
return false;
}
private static int getIndex(Node currentNode)
{
Node parent = currentNode.getParent();
for (int i = 0; i < parent.getChildSize(); i++) {
if (parent.getChildren()[i] == currentNode) {
return i;
}
}
//TODO: error condition handling, will not happen if tree not change
return -1;
}
------------------------完全な検索がより簡単に............
ですpublic static Node getNextFailNode(Node currentNode, Node root, Condition condition)
{
boolean foundCurrentNode = false;
Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
Node tmp = stack.pop();
System.out.println("-popup---------" +tmp+ " ");
if (foundCurrentNode && checkCondition(tmp, condition)) {
return tmp;
}
if (tmp == currentNode) {
foundCurrentNode = true;
}
if (tmp.getChildSize() > 0) {
for (int i = tmp.getChildSize() - 1; i >= 0; i--) {
stack.push(tmp.getChildren()[i]);
}
}
}
return null;
}
ありがとう、あまりにも重いです。 –