Chương trình thay đổi gốc của cây nhị phân bằng Python

Giả sử, chúng ta được cung cấp một cây nhị phân và một nút nằm ở lá của cây nhị phân, chúng ta phải làm cho nút lá trở thành nút gốc của cây nhị phân. Chúng ta có thể làm theo cách sau -

• Nếu một nút có nút con bên trái, nó sẽ trở thành nút con bên phải.

• Cha của một nút trở thành nút con bên trái của nó. Trong quá trình này, liên kết của nút cha với nút đó trở nên rỗng, vì vậy nó sẽ chỉ có một nút con.

Cấu trúc nút của cây như dưới đây -

TreeNode:
   data: <integer>
   left: <pointer of TreeNode>
   right: <pointer of TreeNode>
   parent: <pointer of TreeNode>

Chúng tôi phải trả lại gốc của cây đã chuyển đổi.

Vì vậy, nếu đầu vào giống như

và gốc mới là 8; thì biểu diễn nonder của cây được chuyển đổi sẽ là - 2, 3, 4, 5, 7, 6, 8,

Nút gốc mới của cây là 8.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm trợ giúp (). Thao tác này sẽ sử dụng nút, new_par

  • nếu nút giống với nút gốc, thì

    • cha của nút:=new_par

    • nếu bên trái của nút giống với new_par, thì

      • bên trái của nút:=null

    • nếu bên phải của nút giống với new_par, thì

      • bên phải của nút:=null

    • trả về thư mục gốc

  • nếu bên trái của nút không rỗng, thì

    • right of node:=left of node

  • nếu bên trái của nút cha giống với nút, thì

    • bên trái của nút cha:=null

  • left of node:=helper (cha của node, node)

  • cha của nút:=new_par

  • nút trả lại

• trả về trình trợ giúp (lá, null)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

import collections
class TreeNode:
   def __init__(self, data, left = None, right = None, parent = None):
      self.data = data
      self.left = left
      self.right = right
      self.parent = parent
   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, parent = temp)
            else:
               temp.left = TreeNode(0, parent = temp)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data, parent = temp)
         else:
            temp.right = TreeNode(0, parent = temp)
         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, leaf):
   def helper(node, new_par):
      if node == root:
         node.parent = new_par
         if node.left == new_par:
            node.left = None
         if node.right == new_par:
            node.right = None
         return root
      if node.left:
         node.right = node.left
      if node.parent.left == node:
         node.parent.left = None
      node.left = helper(node.parent, node)
      node.parent = new_par
      return node
   return helper(leaf, None)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
root = solve(root, search_node(root, 8))
print_tree(root)

Đầu vào

root = make_tree([5, 3, 7, 2, 4, 6, 8])
root = solve(root, search_node(root, 8))

Đầu ra

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