比较两个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是否相等。而已。