如何在python中表示二叉樹？

目前我表示以下面的方式的二進制樹：如何在python中表示二叉樹？

[None,2,[None,3,None]]

樹上述植根於2. None意味着該分支是空的。

我寧願在列表中實現這一點。有沒有更好的方法來做到這一點（不訴諸創建類）？

來源

2011-05-31 Frankie Ribery

+10

爲什麼aribtrary限制「而不是訴諸創建類」？我認爲做這個*的最好方法是*定義一個類。 – 2011-05-31 11:53:00

「更好的方式」在哪方面？更高效？ – phynfo 2011-05-31 12:16:30

它可以表示使用平面列表的二進制樹，如所描述here。這種方法浪費多少取決於樹的形狀。

我很好奇，爲什麼你堅持避免類。如果你想把它包裝在一個類中，你可以定義一個乾淨的API並隱藏最終用戶的實現細節。

來源

2011-05-31 11:55:26 NPE

如果你想表示一個完整的二叉樹（即具有所有節點的兩個孩子，除了葉子），那麼你可以只使用一個平面列表的代表樹。

你可以很容易地確定父親和這樣一個節點的兩個孩子：

def leftChild(lst,i): 
    try: 
    return lst[i*2] 
    except IndexError: 
    return None 

def rightChild(lst,i): 
    try: 
    return lst[i*2+1] 
    except IndexError: 
    return None 

def father(lst,i): 
    try: 
    return lst[i/2] 
    except IndexError: 
    return None

來源

2011-05-31 12:20:23 phynfo

這裏是我的方法：數組的數組，其中索引爲0的項目是根項目：

[['Level A', 'A1', 'A2'], ['Level B', 'B1', 'B2'], ['Level C', 'C1', 'C2']]

類可以做一個簡單的應用程序過於複雜，特別是如果你處理像上述表示的簡單的樹木。

來源

2013-08-14 02:12:21

如何在python中表示二叉樹？

回答

相關問題