我正在處理我以這種方式表示的通用樹：
class GenericTree:
""" A tree in which each node can have any number of children.
Each node is linked to its parent and to its immediate sibling on the right
"""
def __init__(self, data):
self._data = data
self._child = None
self._sibling = None
self._parent = None
我必須鏡像它，并且允許遞回。我以這種方式解決了它：
def mirror(self):
""" Modifies this tree by mirroring it, that is, reverses the order
of all children of this node and of all its descendants
- MUST work in O(n) where n is the number of nodes
- MUST change the order of nodes, NOT the data (so don't touch the data !)
- DON'T create new nodes
- It is acceptable to use a recursive method.
Example:
a <- Becomes: a
├b ├i
│├c ├e
│└d │├h
├e │├g
│├f │└f
│├g └b
│└h ├d
└i └c
"""
mylist=[] #Initializing a list
if self._child: #If GenTree has children:
current=self._child #initalizing the variable for the while loop
while current: #until there are root's sons
mylist.append(current) #I put it them in the list
current=current._sibling #Going ahead to put all the sons in the list
self._child=mylist[-1] #The _child is now the "rightest" one, i.e. the son that points to None
#Now I iterate within the list in the opposite direction:
for i in range(-len(mylist),0):
mylist[i]._sibling=mylist[i 1] if i<-1 else None #I go from right to left #and I reverse in this way the sense of the list (if the sons were ROOT|->a->b->c, now they should be ROOT|->c->b->a
for i in range(-len(mylist),0):
mylist[i].mirror() #Doing the recursion for each son using them as roots
但它不起作用：這是我的代碼生成的錯誤示例：
AssertionError: Children sizes are different !
ACTUAL EXPECTED
a a
├b ├b
│└d │├d <--- DIFFERENT !
└e │└c
└e
我究竟做錯了什么？
uj5u.com熱心網友回復：
考慮以下：
for i in range(-1, -10, -1):
print(i)
-1
-2
-3
-4
-5
-6
-7
-8
-9
如果您打算反轉串列中的兄弟姐妹，這就是您想要做的，但是您要做的是從開始-9并轉到-1，即從串列的開頭到結尾。
因此，節點 at 的兄弟節點-1成為節點 at-2等，直到元素 at 0or的兄弟節點-len(mylist)變為None。
改變你的回圈如下：
for i in range(-1, -len(mylist), -1):
mylist[i]._sibling=mylist[i-1]
mylist[0]._sibling = None
為了避免負面索引的所有麻煩，您還可以反轉您的串列并從一開始就對其進行索引，如下所示：
mylist.reverse()
for i in range(len(mylist)-1):
mylist[i]._sibling = mylist[i 1]
mylist[-1]._sibling = None
uj5u.com熱心網友回復：
正如其他人解釋的那樣，即使使用負索引，您仍然可以按原始順序訪問串列項。
不過，我想指出，此類代碼挑戰旨在讓您不使用標準串列作為幫助程式，而是在不使用此類輔助資料結構的情況下解決此問題。
您可以通過使用 3 個參考遍歷鏈表來反轉鏈表，一個在另一個后面，另一個在它前面。在 Python 中，您甚至可以使用 2 個參考和元組賦值來實作。
由于兄弟結構本質上是一個鏈表，您可以使用該方法：
def mirror(self):
# Reverse linked list of siblings
prev = None
current = self._child
while current:
current.mirror() # Recursion
# Create backwards link and move forward
current._sibling, prev, current = prev, current, current._sibling
self._child = prev
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/407525.html
標籤：