删除二叉树中的叶节点

Question

我正在实施 BST，一切正常，即使是删除两个 children.The，唯一的错误是删除叶子，这似乎是一项微不足道的任务。好像还是有叶节点的引用但是我顶不上这个 issue.Putting node = None 没有删除整个 Node.I 也试过del node 没有任何 luck.If 你能发现问题就好了。

import random


class Node:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.parent = None
        self.left_child = None
        self.right_child = None
        self.level = None

class Tree:

    def __init__(self):
        self.root = None
        self.size = 0
        self.height = 0

    def _insertion(self, root, data):
        new_node = Node(data)
        if root.data < data:
            if root.right:
                return self._insertion(root.right, data)
            root.right = new_node
            root.right.parent = root
            root.right_child = root.right
            return
        if root.data > data:
            if root.left:
                return self._insertion(root.left, data)
            root.left = new_node
            root.left.parent = root
            root.left_child = root.left
            return

    def insertion(self, data):
        new_node = Node(data)
        if not self.root:
            self.root = new_node
            return
        return self._insertion(self.root, data)

    def _get_height(self, root):
        if not root:
            return -1
        left_height = self._get_height(root.left)
        right_height = self._get_height(root.right)
        return 1 + max(left_height, right_height)

    def get_height(self):
        if not self.root:
            return 0
        return self._get_height(self.root)

    def fill_random(self, num_nodes):
        for i in range(num_nodes):
            random_num = int(random.random()*100)
            self.insertion(random_num)

    def _inorder(self, root):
        if root:
            self._inorder(root.left)
            print(root.data)
            self._inorder(root.right)

    def inorder(self):
        root = self.root
        return self._inorder(root)

    def get_max(self, node):
        while node.right:
            node = node.right
        return node.data

    def search(self, data):
        root = self.root
        while root.right or root.left:
            if root.data < data:
                root = root.right
            if root.data > data:
                root = root.right
            if root.data == data:
                return root
        return None

    def _delete_node(self, root, data):
        if root:
            if root.data < data:
                return self._delete_node(root.right, data)
            if root.data > data:
                return self._delete_node(root.left, data)
            if root.data == data:
                if not root.left and not root.right:
                    root = None
                    return
                if not root.left and root.right:
                    root = root.right
                    root.right = None
                    return
                if not root.right and root.left:
                    root = root.left
                    root.left = None
                    return
                if root.right and root.left:
                    value = self.get_max(root)
                    print(f"This is the value: {value}")
                    root.data = value
                    self._delete_node(root.right, value)

    def delete_node(self, data):
        if not self.root:
            return None
        return self._delete_node(self.root, data)

if __name__ == '__main__':
    my_tree = Tree()
    my_tree.insertion(33)
    my_tree.insertion(36)
    my_tree.insertion(25)
    my_tree.insertion(20)
    my_tree.insertion(27)
    my_tree.insertion(35)
    my_tree.insertion(39)
    my_tree.delete_node(33)
    my_tree.inorder()
    my_tree.search(35)

Answer 1

这段代码没有做任何事情：

            if root.data == data:
                if not root.left and not root.right:
                    root = None
                    return

因为root是局部变量；将其重新分配给 None 不会影响树。

您需要做的是更改parent节点的right或left指针。我建议你在递归之前这样做，但你也可以通过将父节点传递给这个函数来解决它。

Answer 2

在您的 _delete_node 函数中，将 root 设置为 None 无济于事。这只会影响变量，但不会给树带来任何变化。

一个常见的“技巧”是 return root 给调用者——然后调用者负责将 returned 值分配回它在树中引用的位置.例如，如果递归调用是用 root.left 作为参数进行的，并且递归调用想要删除该节点，它将 return None，然后调用者必须分配（无论它是什么返回）到 root.left。所以现在树是按预期突变的。

以下是根据该原则改编的 delete_node 函数：

    def _delete_node(self, root, data):
        if root:
            if root.data < data:
                root.right = self._delete_node(root.right, data)
            elif root.data > data:
                root.left = self._delete_node(root.left, data)
            elif not root.left:
                return root.right
            elif not root.right:
                return root.left
            else:
                value = self.get_max(root)
                print(f"This is the value: {value}")
                root.data = value
                root.right = self._delete_node(root.right, value)
        return root

    def delete_node(self, data):
        if self.root:
            self.root = self._delete_node(self.root, data)

另说

您的 search 函数有一些问题：

while 条件应在访问其任何属性之前检查 root 是否为 None。
if块要和elif连在一起，否则执行可能会掉到第二个if块，这不是本意

这是更正后的版本：

    def search(self, data):
        root = self.root
        while root:
            if root.data < data:
                root = root.right
            elif root.data > data:
                root = root.left
            else:
                return root
        return None

改善不大

为了帮助调试这段代码，我对 inorder 方法做了一点改动，以便树打印有缩进：

    def _inorder(self, root, indent=""):
        if root:
            self._inorder(root.left, indent+"  ")
            print(indent + str(root.data))
            self._inorder(root.right, indent+"  ")

这有助于快速查看树的结构。你甚至可能想要左右切换，这样它看起来就像一棵旋转的树。

删除二叉树中的叶节点

Deleting the leaf node in a binary tree

python

data-structures

另说

改善不大