Cho cây nhị phân và một node lá. Cần làm node lá đó trở thành root mới. Quy tắc: node có con trái → con trái thành con phải; node cha thành con trái (liên kết cha cũ bị null).
Thuật toán
- Hàm helper(node, new_par):
- Nếu node == root: gán parent = new_par, xóa liên kết cũ với new_par, trả về root
- Nếu node.left tồn tại: node.right = node.left
- Nếu node là con trái của cha: cha.left = None
- node.left = helper(node.parent, node)
- node.parent = new_par
- Trả về node
- Gọi helper(leaf, None)
Code Python
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 = [temp]
while que:
temp = que.pop(0)
if not temp.left:
temp.left = TreeNode(data, parent=temp) if data is not None else TreeNode(0, parent=temp)
break
else:
que.append(temp.left)
if not temp.right:
temp.right = TreeNode(data, parent=temp) if data is not None else 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 not root: return None
if root.data == element: return root
res1 = search_node(root.left, element)
if res1: return res1
return search_node(root.right, element)
def print_tree(root):
if root:
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)
Input
root = make_tree([5, 3, 7, 2, 4, 6, 8]); root = solve(root, search_node(root, 8))
Output
2, 3, 4, 5, 7, 6, 8,