使用 Python 修復錯誤二叉樹的程式

假設，我們得到了一棵存在問題的二叉樹；其中一個節點的右子節點指標錯誤地指向了二叉樹中同一層級的另一個節點。因此，為了解決這個問題，我們必須找出存在此錯誤的節點，並刪除該節點及其後代，除了它錯誤指向的節點。我們返回修復後的二叉樹的根節點。

因此，如果輸入類似於

我們可以看到節點 4 和 6 之間存在錯誤連結。節點 4 的右子節點指標指向節點 6。

那麼輸出，已更正樹的中序表示將為 - 2、3、5、6、7、8。

節點 4 被刪除，因為它與節點 6 有錯誤連結。

為了解決這個問題，我們將遵循以下步驟 -

  • q := 一個包含根節點的新雙端佇列

  • p := 一個新的對映

  • visited := 一個新的集合

  • 當 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

      • 返回根節點

    • 將 cur 新增到 visited 中

    • 如果 cur 的左子節點不為空，則

      • p[cur 的左子節點] := 一個新的元組 (cur, 1)

      • 將 cur 的左子節點插入到 q 的末尾

    • 如果 cur 的右子節點不為空，則

      • p[cur 的右子節點] := 一個新的元組 (cur, 0)

      • 將 cur 的右子節點插入到 q 的末尾

  • 返回根節點

讓我們檢視以下實現以獲得更好的理解 -

示例

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,

更新於: 2021-05-29

178 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告

© . All rights reserved.