关于bst删除节点时的两个疑问 #9

Activity

1. PegasusWang commented on Jun 10, 2018

   

   PegasusWang

   on Jun 10, 2018

   Last edited by PegasusWang

   Owner

   More actions

   1. 第一个问题，插入的时候 30 是不会成为 70 的左孩子的，按照 bst 的插入特性，30 只会插入到 root 的左子树，因为比 root 的 60 要小，所以这个前提不会成立。

   2. 删除两个孩子的内部节点有三个步骤：

   • 找到待删除节点 N 的后继节点 S
   • 复制节点 S 到节点 N
   • 从 N 的右子树中删除节点 S，并更新其删除后继节点后的右子树
     这里赋值的意思是表明把当前子树的右子树更新为删除后继节点后的子树，假如右子树此时为 None 了，不更新的话依然指向老的右子树节点，而此时右子树应该是 None。

   你可以给 Bst 加上个中序遍历的方法：

      def inorder_trav(self, subtree):
          if subtree is not None:
              self.inorder_trav(subtree.left)
              print(subtree.key)
              self.inorder_trav(subtree.right)

   然后直接测试：

   def test_bst_tree():
       bst = BST.build_from(NODE_LIST)
       for node_dict in NODE_LIST:
           key = node_dict['key']
           assert bst.get(key) == key
       assert bst.size == len(NODE_LIST)
       assert bst.get(-1) is None    # 单例的 None 我们用 is 来比较
   
       assert bst.bst_min() == 1
       bst.remove(29) # 直接删除一个包含两个孩子的内部节点
       print('\n')
       bst.inorder_trav(bst.root)
       print('\n')

   你会看到赋值和不赋值之间的差别。
   最后，交换的地方确实有个手误，感谢及时发现，已经合并。不知道有没有表述清楚呢？

   👍React with 👍1Reacted by 非法操作
2. hjlarry commented on Jun 11, 2018

   

   hjlarry

   on Jun 11, 2018

   ContributorAuthor

   More actions

   感谢大佬 两个问题都已想明白了
3. PegasusWang commented on Jun 12, 2018

   

   PegasusWang

   on Jun 12, 2018

   Owner

   More actions

   好，如果解答了你的疑问这个 issue 我就 close 了
4. PegasusWang

   closed this as completedon Jun 12, 2018