如何查找有序字典中的所有元素，實現爲具有密鑰k的二叉樹k

給定一個二叉樹，我需要實現findAllElements（k）方法來查找樹中的所有元素，其中的鍵值等於k 。如何查找有序字典中的所有元素，實現爲具有密鑰k的二叉樹k

我的想法是你第一次遇到一個帶有鍵k的元素。所有具有相同密鑰的元素應該位於左側子樹的右側子樹或右側子樹的左側子樹中。但我被告知這可能並非如此？

我只需要找到一種方法來實現算法。所以需要僞代碼。

我可能應該添加這個抱歉。但是實現方式是左子樹包含的鍵小於或等於根中的鍵，而右子樹包含的鍵大於或等於根中的鍵。

來源

2013-02-28 Nick

你需要一個算法，但你不明白你的樹是怎麼樣的？ – SomeWittyUsername 2013-02-28 18:53:52

是什麼讓你覺得我不明白我的樹長什麼樣子？ – Nick 2013-03-01 20:01:59

好吧，如果你明白了，你就不會寫下「*我被告知這可能不是這種情況*」，而你對帖子的編輯只會強制這個假設 – SomeWittyUsername 2013-03-01 21:26:49

思想，我會回來，並解釋其結果應該是與我交談的老師了。所以如果你執行一個方法findElement（k），它將找到一個關鍵字等於k的元素，它找到的元素應該是樹中鍵k最高的元素（讓我們表示這個元素V）。

然後從這個元素V中，包含key = k的其他元素將位於左子子樹（尤其是一直到右側）或右子子樹（特別是一直到左側）。因此，對於左邊的孩子繼續到下一個節點右邊的孩子，直到找到具有key = k的元素...現在...以該節點爲根的子樹中的每個元素都必須有一個key = k（這是部分我起初不認識），因此任何遍歷這個完整的子樹都可以完成查找和存儲這個子樹中的所有元素（訪問它中的每個節點）。這種類型的事情必須爲正確的孩子重複，但要訪問每個左邊的孩子，直到找到具有key = k的元素。那麼以此元素作爲其根的子樹就具有其中所有其他具有key = k的元素，並且可以通過再次遍歷該子樹找到它們。

這只是一個詞的描述，顯然，抱歉的長度和任何混淆。希望這會幫助其他人試圖解決類似的問題。

來源

2013-03-01 20:03:47 Nick

看看當前節點。如果其密鑰高於k，則搜索左側子樹。如果較低，則搜索右側子樹。如果相等，則搜索左側和右側子樹（並在結果中包含當前節點）。

這樣做是從根節點遞歸地開始的。

來源

2013-02-28 18:54:09

不好的建議。假設它不僅僅是一個二叉樹，而且是一個**二叉搜索樹**（不確定OP是否理解這種差異），重複存儲必須定義明確，並且要麼在左側，要麼在右側子樹中 - 這是專用定義的特定BST實現 – SomeWittyUsername 2013-02-28 19:00:11

他沒有說這是一個「二叉搜索樹」，而只是一個「二叉樹」。 – 2013-02-28 19:17:50

但標籤說BST。 ... – 2013-02-28 19:21:09

這取決於你的樹實現，通過二叉樹我假設你的意思是二叉搜索樹，並且你使用運算符<來比較這個鍵。也就是說，節點的左側子樹只包含密鑰數小於節點密鑰的節點（<），而節點的右側子樹只包含節點密鑰爲的節點，而不是節點密鑰的（！<）。

例如

如果在樹多等於鍵，這樣做

k < current_node_key, search left subtree 
k > current_node_key, search right subtree 
k == current_node_key, record current node , then search right tree

來源

2013-02-28 19:06:03 lostyzd

如何查找有序字典中的所有元素，實現爲具有密鑰k的二叉樹k

回答

相關問題