二叉搜索树，试图实现一个删除节点的方法，指针有问题

Question

我在 Whosebug 上发现了另一个很好的线程，打算 link 它 removing a node from a binary search tree using recursion 。这是我从中获取代码的地方，它看起来像这样：

import random
from time import time

class BinaryNode:

    def __init__(self, value = None):
        """Create binary node"""
        self.value = value
        self.left = None
        self.right = None

    def add(self, val):
        """Adds a new node to the tree containing this value"""
        if val <= self.value:
            if self.left:
                self.left.add(val)
            else:
                self.left = BinaryNode(val)
        else:
            if self.right:
                self.right.add(val)
            else:
                self.right = BinaryNode(val)

    def delete(self):
        """
         Remove value of self from BinaryTree. Works in conjunction with remove
         method in BinaryTree
        """

        if self.left == self.right == None:
            return None
        if self.left == None:
            return self.right
        if self.right == None:
            return self.left

        child = self.left
        grandchild = child.right
        if grandchild:
            while grandchild.right:
                child = grandchild
                grandchild = child.right
            self.value = grandchild.value
            child.right = grandchild.left
        else:
            self.left = child.left
            self.value = child.value

        return self

class BinaryTree:

    def __init__(self):
        """Create empty binary tree"""
        self.root = None

    def add(self, value):
        """Insert value into proper location in Binary Tree"""
        if self.root is None:
            self.root = BinaryNode(value)
        else:
            self.root.add(value)

    def contains(self, target):
        """Check whether BST contains target value"""

        node = self.root
        while node:
            if target == node.value:
                return True
            if target < node.value:
                node = node.left
            else:
                node = node.right

        return False

    def remove(self, value):
        """Remove value from tree"""

        if self.root:
            self.root = self.removeFromParent(self.root, value)

    def removeFromParent(self, parent, value):
        """remove value from tree rooted at parent"""
        if parent is None:
            return None

        if value == parent.value:
            return parent.delete()
        elif value < parent.value:
            parent.left = self.removeFromParent(parent.left, value)
        else:
            parent.right = self.removeFromParent(parent.right, value)

        return parent

如果我们关注 BinaryNode class 下的 delete 方法，我需要一些帮助来理解指针，我之前已经把自己的二进制搜索树放在一起但我无法理解, self.left 是指针吗？什么是self.left.right（参见grandchild），这是一个指针，从"start"，即将成为root，到child，然后再到right（到grandchild）。 delete 方法不需要要删除哪个值的参数对我来说也感觉有点奇怪，我没有看到其他任何地方使用该方法...

Answer 1

left 和 right 属性是 object。实际上，它们被实现为 object 引用，a.k.a。指针。

self.left.right 是 self 的 left-then-right grandchild（你的临时 "root"）。 **自己*最多可以有四个孙辈；这是第二个（从左往右数），左边child右边child.

delete 确实有一个参数：self。这就是它知道要删除哪个节点的方式。该方法未在其他地方使用，因为 none 的其他方法需要删除节点。您正在开发供外部使用的 class，而不是 self-sufficient 应用程序。

这是否足够好地回答您当前的困惑？尝试用铅笔画出这棵树，并完成这些方法。在逐步执行代码时擦除和重绘指针。也许更好，使用两种颜色，这样你就有了 "before" 和 "after" 指针，并在进行时对更改进行编号。

我不会说 self 充当哨兵节点； "sentinel" 概念更多的是在特定点停止迭代。

至于 pointer/object 二分法，我怀疑您遇到麻烦的原因之一是 Python 不允许您经常将两者分开。每个变量值都是对变量 object.

的引用

具体来说，self.right.left 最终是对 grandchild 的参考。但是，Python run-time 系统使用它来让您直接访问 grandchild object。换句话说，你无法真正分辨出区别。无论哪种方式都可以考虑；当它适合您的目的时更改（例如抓住 left 字段就好像它是 object，然后重置 left 就好像它是一个指针）。 Python 使这成为一种量子态：波和粒子。

免责声明：您将最终获得使用熟悉的星号传递参数的能力，以获取指向某物的指针，例如*my_list。在那种情况下，你 do 有明显的区别......但是 Python 会尽快将波函数折叠回粒子。现在不用担心，只要知道它会在稍后出现，这样您就不会对到那时为止所学的东西失去信心。

二叉搜索树，试图实现一个删除节点的方法，指针有问题

Binary searchtree, trying to implement a remove node method, trouble with pointers

python

pointers

nodes

binary-search-tree