樹的遍歷在Java中

我面試的研究，並正檢討樹木，我有穿越他們的時候沒有問題，但我有一個問題我一直沒能得到正確答案的身影到：樹的遍歷在Java中

編寫一個函數，該函數返回給定兩個參數的樹中的節點：指向根節點的指針和我們要返回的節點的inorder遍歷數。存儲在樹中的唯一信息是每個節點的子數。

到目前爲止，我還沒有能夠確定爲什麼我會照顧存儲在樹中的信息（孩子的數量）。除此之外，如果我們假設有像這樣的樹：

 5 
    4  7 
3 1 4

那麼序遍歷將341547但我想不通的代碼返回我想要的節點（便於討論，我假設中序遍歷數是2 - 意思是我想要值1的節點）。

我試着做一個遞歸遍歷，但我最終擰了內部計數器我有，所以我嘗試了不同的方法，只是試圖把一切都放在堆棧上，但我不知道如何正確地做到這一點。到目前爲止，我有：

public int findNode(root, position){ 
    Stack<Integer> s = new Stack<Integer>(); 
    cNode = root; //cNode = current Node 

    while(cNode.left != null) 
     cNode = cNode.left; 

    s.push(cNode); 

    while(cNode.right != null) 
    cNode = cNode.right; 

    //stuck here. 
}

的遞歸方法是比較容易，但我想不出如何檢查，如果我有我要找的＃：

public int findNode(root, position){ 
    cNode = root; 
    if(cNode != null){ 
     findNode(cNode.left, position); 
     System.out.print(cNode.data); 
     findNode(cNode.right, position); 
    } 
}

我知道這遍歷樹但它仍然沒有做到我想要的。任何幫助，將不勝感激。

來源

2012-02-01 Tsundoku

鑑於「存儲在樹中的唯一信息是每個節點的子節點數」，我猜你的示例樹是錯誤的。另外，「inorder traversal number 「究竟是？ – Gevorg 2012-02-01 20:29:30

「寫一個函數，返回一個樹中的***節點***給出兩個參數」，***樹中的一個節點***，哪個節點？在該特定索引處具有該特定值OR節點的節點（索引與在中間遍歷中一樣） – Bhushan 2012-02-01 20:33:32

你能做到這樣：

public Node findNode(Node root, int position) { 
    ArrayList<Node> a = new ArrayList<Node>(); 
    populateNodes(root, a); 
    return a.get(position); 
} 

private void populateNodes(Node node, ArrayList<Node> a) { 
    if (node == null) return; 
    populateNodes(node.left, a); 
    a.add(node); 
    populateNodes(node.right, a); 
}

注意：您不需要使用額外的數據結構，如果你不想要的，但因爲你有一個堆棧，我只是用它去。注2：正如Jim Garrison所指出的，如果你有後代數，你可以優化算法。

來源

2012-02-01 21:34:48

這是輝煌的我不知道我怎麼想不到這一點，非常感謝。 – Tsundoku 2012-02-01 22:16:17

問題不明確。「Inorder」對於二叉樹是有意義的，在這種情況下，「孩子的數量」總是兩個，除非他們的意思是「後裔的數量」，在這種情況下，您可以使用它來避免通過inorder列表進行線性搜索（O * n）因爲在每個節點你可以根據子孫的數量來決定採取哪個分支（O * log n）。

來源

2012-02-01 20:34:50

我猜這棵樹是錯的，錯過了一個孩子。既然這是我在書中的例子。 – Tsundoku 2012-02-01 20:36:30

你是什麼意思「失蹤的孩子」。二叉樹不必完全填充。 – 2012-02-01 20:38:08

而不是傳遞位置，傳遞中序遍歷數並在每個遞歸方法中追加到它。

來源

2012-02-01 20:35:42

通過使用樹的屬性來減少算法的複雜度會更好，每個節點都知道它擁有的子節點的總數。所以，如果你知道有多少孩子在左側就可以計算出當前節點的順序號下面的代碼應該工作（根就沒有左+ 1的孩子。）：

Nodeptr nthInInorder(Nodeptr root, int x){ 
Nodeptr curr = root; 
int countedIn = 0, leftchildren = 0, currIn=0; 

while(curr!=NULL){ 
    if(curr->left == NULL) 
    leftchildren = 0; 
    else 
    leftchildren = (curr->left)->data + 1; 

    currIn = countedIn + leftchildren + 1; 

    if(currIn == x) 
    return curr; 
    else if(currIn > x) 
    curr = curr->left; 
    else if(currIn < x) 
    { countedIn = currIn + 1; 
    curr = curr->right; 
    } 
    } 
    return NULL; 
}

這個算法的複雜性是O（log n）

來源

2013-01-27 20:06:28

樹的遍歷在Java中

回答

相關問題