পাইথন ব্যবহার করে বাইনারি ট্রিতে ডানদিকে নোড খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন, আমাদের একটি বাইনারি গাছ দেওয়া হয়েছে। আমাদের একটি নোডের জন্য একটি পয়েন্টারও দেওয়া হয়েছে (নাম 'u') এবং আমাদের প্রদত্ত নোডের ঠিক ডানদিকে অবস্থিত নোডটি খুঁজে বের করতে হবে। প্রদত্ত নোডের ডানদিকে অবস্থিত নোডটিকে অবশ্যই একই স্তরে থাকতে হবে এবং প্রদত্ত নোডটি হয় একটি লিফ নোড বা একটি অভ্যন্তরীণ নোড হতে পারে৷

সুতরাং, যদি ইনপুট মত হয়

এবং u =6, তাহলে আউটপুট হবে 8।

নোড 6 এর ডানদিকে অবস্থিত নোডটি নোড 8, তাই মান 8 আমাদের কাছে ফেরত দেওয়া হয়৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

যদি রুট খালি থাকে, তাহলে
- রিটার্ন নাল
dq :=একটি নতুন ডিক
dq
এর শেষে রুট সন্নিবেশ করান
যখন dq খালি নয়, করুন
- dq_size :=dq এর আকার
- temp :=একটি নতুন তালিকা
- সূচক :=-1
- 0 থেকে dq_size রেঞ্জের প্রতিটি মানের জন্য, করুন
  - node :=dq
    থেকে শেষ উপাদান মুছে দিন
  - যদি নোডের বাম অংশ খালি না হয়, তাহলে
    - dq
      এর শেষে নোডের বাম অংশ যোগ করুন
  - যদি নোডের ডানদিকে খালি না হয়, তাহলে
    - dq
      -এর শেষে নোডের ডানদিকে যোগ করুন
  - টেম্পের শেষে নোড সন্নিবেশ করুন
  - যদি নোড u এর মত হয়, তাহলে
    - সূচক :=তাপমাত্রার আকার - 1
- যদি সূচকটি তাপমাত্রা - 1 এর আকারের সমান হয়, তাহলে
  - রিটার্ন নাল
- যদি সূচক> -1, তাহলে
  - রিটার্ন টেম্প[ইনডেক্স + 1]
রিটার্ন নাল

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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)