Python দিয়ে বাইনারি ট্রির রুট পরিবর্তন করার প্রোগ্রাম

মান লাগিয়ে, আমাদের একটি বাইনারি ট্রি এবং একটি নোড দেওয়া আছে যা বাইনারি ট্রির লিফে অবস্থিত। আমাদের লিফ নোডটিকে বাইনারি ট্রির রুট নোড বানাতে হবে। আমরা এটি নিচের şekilde করতে পারি:

• যদি একটি নোডের বাম চাইল্ড থাকে, তবে সেটি ডান চাইল্ড হয়ে যায়।
• একটি নোডের পেরেন্ট তার বাম চাইল্ড হয়ে যায়। এই প্রক্রিয়ায়, পেরেন্ট নোডের সেই নোডের সাথে লিংক null হয়ে যায়, তাই সেটির শুধু একটি চাইল্ড থাকবে।

ট্রির নোড কাঠামো নিচের মতো:

TreeNode:
    data: 
    left: 
    right: 
    parent: 

আমাদের কনভার্টেড ট্রির রুট রিটার্ন করতে হবে।

যেমন, ইনপুট যদি এমন হয়:

এবং নতুন রুট হল 8; তবে কনভার্টেড ট্রির ইনঅর্ডার রিপ্রেজেন্টেশন হবে: 2, 3, 4, 5, 7, 6, 8,

ট্রির নতুন রুট নোড হল 8।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:

• একটি ফাংশন helper() ডিফাইন করুন। এটি node, new_par নেবে:
  • যদি node == root হয়, তবে:
    • node.parent := new_par
    • যদি node.left == new_par হয়, তবে node.left := null
    • যদি node.right == new_par হয়, তবে node.right := null
    • root রিটার্ন করুন
  • যদি node.left null না হয়, তবে node.right := node.left
  • যদি node.parent.left == node হয়, তবে node.parent.left := null
  • node.left := helper(node.parent, node)
  • node.parent := new_par
  • node রিটার্ন করুন
• helper(leaf, null) রিটার্ন করুন

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

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)

ইনপুট

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

আউটপুট

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