মান লাগিয়ে, আমাদের একটি বাইনারি ট্রি দেওয়া আছে যাতে একটি সমস্যা আছে: একটি নোডের ডান চাইল্ড পয়েন্টার ভুলভাবে একই লেভেলের অন্য একটি নোডকে পয়েন্ট করছে। এই সমস্যা ঠিক করতে, আমাদের সেই নোডটি খুঁজে বের করতে হবে যেটিতে এই ত্রুটি আছে এবং সেই নোডটি এবং তার ডিসেন্ডেন্টগুলো ডিলিট করতে হবে সिवা সেই নোডের যেটি ভুলভাবে পয়েন্ট করছে। আমরা ঠিক করা বাইনারি ট্রির রুট নোড রিটার্ন করব।
যেমন, ইনপুট যদি এমন হয়:
আমরা দেখতে পাচ্ছি 4 এবং 6-এর মধ্যে একটি ভুল লিংক আছে। 4-এর ডান চাইল্ড পয়েন্টার 6-কে পয়েন্ট করছে।
তবে আউটপুট, কোরেক্টেড ট্রির ইনঅর্ডার রিপ্রেজেন্টেশন হবে: 2, 3, 5, 6, 7, 8,
নোড 4 ডিলিট হয়েছে কারণ তার 6-র সাথে একটি ভুল লিংক ছিল।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- q := রুট ধারণকারী একটি নতুন deque
- p := একটি নতুন ম্যাপ
- visited := একটি নতুন সেট
- q খালি না হওয়া পর্যন্ত:
- cur := q-এর বামপাশের এলিমেন্ট পপ করুন
- যদি cur visited-এ থাকে, তবে:
- is_left := p[p[cur][0]]
- grand_p := p[p[cur][0]]
- যদি is_left null না হয়, তবে grand_p.left := null
- অন্যথায়, grand_p.right := null
- root রিটার্ন করুন
- cur visited-এ যোগ করুন
- যদি cur.left null না হয়, তবে p[cur.left] := (cur, 1) এবং cur.left q-তে যোগ করুন
- যদি cur.right null না হয়, তবে p[cur.right] := (cur, 0) এবং cur.right q-তে যোগ করুন
- root রিটার্ন করুন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
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,
