2011-08-03 66 views
1

我需要編寫一個函數來查找符合特殊條件的前一個/下一個葉節點,這個節點位於單根樹中的任何節點。 (在父一階)java alogrithm:從樹中的任意節點查找符合特殊條件的前/後葉節點

該API將是這樣的:

Node findNextLeafNode(Node currentNode, Condition condition); 
Node findPretLeafNode(Node currentNode, Condition condition); 

其中currentNode處於樹中的任何節點,並且Node被定義爲:

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(); 
} 

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; 
} 

回答

0

這可能是誇大的方式爲你所需要的,但它可以支持你想要什麼:

有一個圖的遍歷語言:Gremlin。通常在像Neo4j之類的東西上加上螺栓,但是可以打包任何圖形數據結構(例如單根的定向樹)以支持API。看看Blueprints項目,瞭解它是如何完成的。

[編輯:少重的東西]

也許JGraphT是你想要的。也請看this question on SO。這不是一個確切的重複,但你應該覺得它有幫助。

+0

謝謝,對我來說太重了。 –

0

爲您的樹編寫一個可以從任何節點初始化並使用前/後/後序遍歷(當然,它應該是雙向的)的迭代器。 這基本上是寫一個簡單的算法,至少對我來說似乎是基本的。 一旦你有一個迭代器,你所需要的就是將你的方式迭代到下一個葉子節點,並且條件適合它。 如果您遇到任何特定部件問題,請提問,我會改進我的答案。

0

基於你已經定義了你的接口的事實,並且你說圖遍歷庫太重了,你可能應該自己寫一下。這將是一個絕對微不足道的代碼量。 (This page包含一些代碼,如果你需要幫助。)

(對於你的API的一個建議:不要把boolean isRoot();方法放在Node上,除非你有足夠的理由這樣做,否則這是一種浪費,構建樹的代碼只應該引用根節點)。

+0

謝謝,我不應該這麼懶惰:)午餐後寫一個getNext的方法.... –

+0

@jkraybill:我把那個放在那裏。沒有位,因爲它是一個接口。 – alphazero