比較兩個bsts

Question

我想創建一個函數來比較兩個bst，看看它們是否相同。

這是我迄今爲止

def same(self,another): 
    same = False 
    for j in another: 
     for i in self: 
      if self[i] == another[j]: 
       same = True 

    return same 

，我就來測試一下是這樣，first.same（另一個），看看他們是相同的方式。

---

這是我更新的功能：

def same(self, another): 
    is_same = False 
    if self == None and another == None: 
     is_same = True 
    if self is not None and another is not None: 
     is_same = ((self._root == rs._root) and identical(self._left, rs._left) and identical(self._right, rs._right)) 

    return is_another 

這是我想出了，但任何事情我有了這個功能，我都會得到一個錯誤的測試。

Answer 1

我不會直接給出答案，但這裏是你如何做到的。

在BST中，左側節點小於或等於根節點，右側節點大於根節點，此屬性遞歸地應用於每個節點。

因此，對於每一個節點，你做到以下幾點

1）如果（bst1node.data == bst2node.data）檢查左，右節點：

回報比較（bst1node.left，bst2node.left）& & compare（bst1node.right，bst2node.right）;

2.）if（bst1node.data！= bst2node.data）{return false}; 3）最後，當比較超越葉子時會發生什麼？

if（bst1node == null & & bst2node == null）return true;

如果一個節點爲空，且其他不爲空，則返回false;

有了這些條件，您應該能夠檢查兩個BST是否相等。而已。