โปรแกรมค้นหาโหนดทางด้านขวาในไบนารีทรีโดยใช้ Python

สมมติว่าเราได้รับไบนารีทรี นอกจากนี้เรายังได้รับตัวชี้ไปยังโหนด (ชื่อ 'u') และเราต้องหาโหนดที่ตั้งอยู่ทางขวาของโหนดที่ให้มา โหนดที่อยู่ทางด้านขวาของโหนดที่กำหนดจะต้องอยู่ในระดับเดียวกัน และโหนดที่กำหนดอาจเป็นโหนดปลายสุดหรือโหนดภายในก็ได้

ดังนั้นหากอินพุตเป็นแบบ

และ u =6 ผลลัพธ์จะเป็น 8

โหนดที่อยู่ทางด้านขวาของโหนด 6 คือโหนด 8 ดังนั้นค่า 8 จะถูกส่งคืนมาที่เรา

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้ารูทว่างก็

  • คืนค่า null

• dq :=เดคใหม่

• แทรกรูทที่ส่วนท้ายของ dq

• ในขณะที่ dq ไม่ว่างเปล่าให้ทำ

  • dq_size :=ขนาดของ dq

  • temp :=รายการใหม่

  • ดัชนี :=-1

  • สำหรับแต่ละค่าในช่วง 0 ถึง dq_size ทำ

    • node :=ลบองค์ประกอบสุดท้ายออกจาก dq

    • ถ้าด้านซ้ายของโหนดไม่ว่างแล้ว

      • เพิ่มด้านซ้ายของโหนดต่อท้าย dq

    • หากทางขวาของโหนดไม่ว่าง

      • เพิ่มด้านขวาของโหนดต่อท้าย dq

    • แทรกโหนดเมื่อสิ้นสุดอุณหภูมิ

    • ถ้าโหนดเหมือนกับ u แล้ว

      • ดัชนี :=ขนาดอุณหภูมิ - 1

  • หากดัชนีเท่ากับขนาดของ temp - 1 แล้ว

    • คืนค่า null

  • ถ้าดัชนี> -1 แล้ว

    • กลับ temp[ดัชนี + 1]

• คืนค่า null

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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)

อินพุต

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

ผลลัพธ์

8