從python中的二進制序列創建一個二叉樹

我想從二進制序列如「100101」二進制創建一棵樹，然後我想這樣創建樹。（基本上1裝置到正確的和0的手段去左邊）從python中的二進制序列創建一個二叉樹

       <Root node> 
            | 
            1 
           /
            0 
           /
           0 
           \ 
            1 
           /
           0 
           \ 
            1

所以我沒有在這裏是代碼：其中值將是串序列（前值=「1001」）

def _inserto(root,value): 
    for i in value: 
     if root == None: 
      root = BSTNode(i) 
      current = root 
     elif i == "1": 
      if current.right is not None: 
       current.right = BSTNode(i) 
       current = current.right 
      else: 
       current.right = BSTNode(i) 
       current = current.right 
     elif i == "0": 
      if (current.left is not None): 
       current.left = BSTNode(i) 
       current = current.left 
      else: 
       current.left =BSTNode(i) 
       current = current.left 
    return root

現在的問題是，如果我想輸入類似「01」的另一個序列，樹看起來應該是這樣

      <Root Node> 
           | 
           1 
          /
           0 
          /\ 
          0 1 
          \ 
           1 
          /
          0 
          \ 
           1

，但我真的很不好受，因爲我的功能G希望覆蓋老樹。

來源

2012-07-22 Wobblester

這是什麼部分，*確切*有問題嗎？您也可以在python中保留對最後一個節點的外部引用。你知道python也有類和對象嗎？ – Marcin 2012-07-22 20:46:54

「基本上1代表右移，0代表左移」Err ...從你的圖表中看來，1代表左移。你的圖是錯的，還是我讀錯了？ – 2012-07-22 20:46:57

@MarkByers我在圖表和'_insert'的代碼之間分享你的「err ...」 - 以1的初始根開始，接下來是0 <1，所以它向左，但是0不是<0 ，所以它應該是正確的（但顯示爲左邊）...我希望OP能夠澄清三個可能的結果中的哪一個是實際需要的。 – 2012-07-22 21:04:01

問題在於處理現有節點的代碼。如果存在，代碼將用新的BSTNode覆蓋它，丟失它下面的所有現有節點。你需要的是這樣的：

elif i == "1": 
     if current.right is None: 
      current.right = BSTNode(i) 
     current = current.right 
    elif i == "0": 
     if root.left is None: 
      current.left = BSTNode(i) 
     current = current.left

如果沒有一個已經存在這將只分配一個節點，然後設置當前這個新的節點。

來源

2012-07-22 23:17:28

從python中的二進制序列創建一個二叉樹

回答

相關問題