我使用類：class Node: def __init__(self, value): self.key = value self.left = None self.right = None self.parent = None我創(chuàng)建了這棵樹(shù)：n_12 = Node(12)n_15 = Node(15)n_3 = Node(3)n_7 = Node(7)n_1 = Node(1)n_2 = Node(2)n_not1 = Node(-1)n_12.right = n_15n_12.left = n_3n_3.right = n_7n_3.left = n_1n_1.right = n_2n_1.left = n_not1n_12.parent = Nonen_15.parent = n_12n_3.parent = n_12n_7.parent = n_3n_1.parent = n_3n_2.parent = n_1n_not1.parent = n_1我試過(guò)這段代碼：def rightRotate(t): if t == None or t.left == None: return None n = t l = t.left r = t.right lr = t.left.right ll = t.left.left t = t.left t.right = n if r != None: t.right.right = r if lr != None: t.right.left = lr if ll != None: t.left = ll但它沒(méi)有用，它使用根節(jié)點(diǎn)n_12刪除了一些節(jié)點(diǎn)。為什么它不起作用，我不明白為什么我沒(méi)有所有節(jié)點(diǎn)。如果我打電話rightRotate(n_1)，我有一個(gè)無(wú)限循環(huán)。
1 回答
MMTTMM
TA貢獻(xiàn)1869條經(jīng)驗(yàn) 獲得超4個(gè)贊
你寫(xiě)了"I have an infinite loop"，但你的代碼沒(méi)有循環(huán)，所以這一定發(fā)生在你代碼的其他地方。
我看到兩個(gè)問(wèn)題：
1) 賦值應(yīng)該是無(wú)條件的
if lr != None:
t.right.left = lr
時(shí)也需要這個(gè)賦值lr is None。如果不是，t.right.left將保持等于那一刻l的那個(gè)t，所以你確實(shí)在你的樹(shù)中留下了一個(gè)循環(huán)。
2）雙線程
您的樹(shù)是雙線程的，即它也有parent鏈接。但是這些不會(huì)在您的rightRotate功能中更新。因此，要么不使用parent鏈接（這是更可取的），要么調(diào)整您的代碼，以便鏈接也parent根據(jù)輪換進(jìn)行更新。
其他備注：
可以簡(jiǎn)化以下代碼：
if r != None:
t.right.right = r # was already equal to r
if lr != None:
t.right.left = lr # see above. should not be behind a condition
if ll != None:
t.left = ll # was already equal to ll
這樣就可以簡(jiǎn)化為：
t.right.left = lr
甚至：
n.left = lr
最終代碼
通過(guò)上述更改，您的功能可以是：
class Node:
def __init__(self, value):
self.key = value
self.left = None
self.right = None
self.parent = None
def rightRotate(node):
if node is None or node.left is None:
return node
parent = node.parent
left = node.left
left_right = left.right
# change edge 1
if parent: # find out if node is a left or right child of node
if parent.left == node:
parent.left = left
else:
parent.right = left
left.parent = parent
# change edge 2
left.right = node
node.parent = left
# change edge 3
node.left = left_right
if left_right:
left_right.parent = node
return left # the node that took the position of node
# your code to build the tree
n_12 = Node(12)
n_15 = Node(15)
n_3 = Node(3)
n_7 = Node(7)
n_1 = Node(1)
n_2 = Node(2)
n_not1 = Node(-1)
n_12.right = n_15
n_12.left = n_3
n_3.right = n_7
n_3.left = n_1
n_1.right = n_2
n_1.left = n_not1
n_12.parent = None
n_15.parent = n_12
n_3.parent = n_12
n_7.parent = n_3
n_1.parent = n_3
n_2.parent = n_1
n_not1.parent = n_1
# rotate the root
root = n_12
root = rightRotate(root) # returns the node that took the place of n_12
只需刪除帶有的行parent即可獲得單線程版本。
添加回答
舉報(bào)
0/150
提交
取消