Chương trình tìm ra nút ở bên phải trong cây nhị phân bằng Python

Giả sử, chúng ta được cung cấp một cây nhị phân. Chúng tôi cũng được cung cấp một con trỏ tới một nút (có tên là ‘u’) và chúng tôi phải tìm nút nằm ngay bên phải của nút được cung cấp. Nút nằm ở bên phải của nút đã cho phải ở cùng mức và nút đã cho có thể là nút lá hoặc nút bên trong.

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

và u =6, thì đầu ra sẽ là 8.

Nút nằm ở bên phải của nút 6 là nút 8, vì vậy giá trị 8 được trả lại cho chúng tôi.

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

• nếu gốc trống, thì

  • trả về null

• dq:=a new deque

• chèn root vào cuối dq

• trong khi dq không trống, thực hiện

  • dq_size:=kích thước của dq

  • temp:=một danh sách mới

  • chỉ mục:=-1

  • đối với mỗi giá trị trong phạm vi từ 0 đến dq_size, hãy thực hiện

    • node:=xóa phần tử cuối cùng khỏi dq

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

      • thêm bên trái của nút vào cuối dq

    • nếu bên phải của nút không trống, thì

      • thêm bên phải của nút vào cuối dq

    • chèn nút vào cuối tạm thời

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

      • index:=size of temp - 1

  • nếu chỉ mục giống với kích thước của temp - 1, thì

    • trả về null

  • nếu chỉ mục> -1, thì

    • trả về nhiệt độ [chỉ mục + 1]

• trả về null

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

Ví dụ

from queue import deque
class TreeNode:
   def __init__(self, val=0, left=None, right=None):
      self.val = val
      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.val == element):
      return root
   res1 = search_node(root.left, element)
   if res1:
      return res1
   res2 = search_node(root.right, element)
   return res2
def solve(root, u):
   if not root:
      return None
   dq = deque()
   dq.append(root)
   while dq:
      dq_size = len(dq)
      temp = []
      index = -1
      for _ in range(dq_size):
         node = dq.pop()
         if node.left:
            dq.appendleft(node.left)
         if node.right:
            dq.appendleft(node.right)
         temp.append(node)
         if node == u:
            index = len(temp) - 1
      if index == len(temp) - 1:
         return None
      if index > -1:
         return temp[index + 1]
   return None
root = make_tree([5, 3, 7, 2, 4, 6, 8])
u = search_node(root,6)
ret = solve(root, u)
print(ret.val)

Đầu vào

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

Đầu ra

8