用 Python 修复错误的二叉树的程序

假设我们有一个二叉树有一个问题; 一个节点的右子节点指针在二叉树中错误地指向同一级别的另一个节点。因此，为了解决这个问题，我们必须找到具有这个错误的节点并删除该节点及其子代，但保留它指错的节点。我们返回修复后的二叉树的根节点。

因此，如果输入如下：

我们可以看到4和6之间有一个错误的链接。节点4的右子节点指向6。

那么输出，修正后树的中序表示将为-2、3、5、6、7、8，

删除节点4，因为它指向错误的节点6。

要解决这个问题，我们将按照以下步骤进行 –

• q：包含根的新 deque
• p：一个新的 map
• visited：一个新的 set
• while q 不为空，做以下操作
  • cur：q 的最左侧的元素

  • 如果 “cur” 存在于 “visited” 中，则

    • is_left：p[p[cur,0]]

    • grand_p：p[p[cur,0]]

    • 如果 is_left 不为空，则

    • grand_p 的左侧 = null

    • 否则，

    • grand_p 的右侧 = null

    • 返回 root

  • 将cur添加到 visited 中

  • 如果 cur 的左侧不为空，则

    • p[cur的左侧]：新元组(cur, 1)

    • 将cur的左侧插入到q的末尾

  • 如果 cur 的右侧不为空，则

    • p[cur的右侧]：新元组(cur, 0)

    • 将cur的右侧插入到q的末尾

• 返回 root

以下是示例。

更多Python相关文章，请阅读：Python 教程

例子

import collections
class TreeNode:
    def __init__(self, data, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right
def insert(temp,data):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)
def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree
def search_node(root, element):
    if (root == None):
        return None
    if (root.data == element):
        return root
    res1 = search_node(root.left, element)
    if res1:
        return res1
    res2 = search_node(root.right, element)
    return res2
def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.data, end = ', ')
        print_tree(root.right)
def solve(root):
    q = collections.deque([root])
    p, visited = dict(), set()
    while q:
        cur = q.popleft()
        if cur in visited:
            grand_p, is_left = p[p[cur][0]]
            if is_left: grand_p.left = None
            else: grand_p.right = None
            return root
        visited.add(cur)
        if cur.left:
            p[cur.left] = (cur, 1)
            q.append(cur.left)
        if cur.right:
            p[cur.right] = (cur, 0)
            q.append(cur.right)
    return root
root = make_tree([5, 3, 7, 2, 4, 6, 8])
link_from = search_node(root, 4)
link_to = search_node(root, 6)
link_from.right = link_to
print_tree(solve(root))

输入

root = make_tree([5, 3, 7, 2, 4, 6, 8])
link_from = search_node(root, 4)
link_to = search_node(root, 6)
link_from.right = link_to

输出

2, 3, 5, 6, 7, 8,