從字符串反序列化二進制搜索樹

Question

只是練習並注意到它很容易序列化（通過深度優先搜索遍歷）一個bst並反序列化到樹中。但是，如果序列化是通過麪包優先搜索遍歷完成的，我很難對其進行反序列化。

例如，給定輸入：5,2,11，N，3,7,19，N，N，6,8，N，N，N，N，N，N 尋找輸出 -

 5 
    / \ 
    2  11 
/\ /\ 
N 3 7 19 
    /\ /\ 
    6 8 N N 
    /\/\ 
    N N N N 

Answer 1

請記住，這是二進制樹搜索，這意味着每個節點只有兩個孩子，左和右。

（假設N代表空/無節點）： 建立你的樹。輸入序列中的第一個元素是根元素，接下來的兩個元素分配爲根的左側子元素，然後是右側子元素。然後使用bfs進入你的樹。如果孩子是N，則轉到下一個孩子，如果孩子是一個值，則將輸入序列中的下兩個值分配爲該節點的左側和右側孩子。如此。

例如：
5,2,11，N，3,7,19，N，N，6,8，N，N，N，N，N，N
分配5爲根。

考慮5作爲節點 - >它是一個值，分配子節點：
2,11，N，3,7,19，N，N，6,8，N，N，N，N，N ，N //在處理5之後剩餘的輸入
將2指定爲左側子節點。
11，N，3,7,19，N，N，6,8，N，N，N，N，N，N
將11指定爲正確的孩子。
//成品在部門0

整個廣度考慮2作爲節點 - >它是一個值，分配小孩：
N，3,7,19，N，N，6,8，N，N- ，N，N，N，N
將N指定爲左邊的孩子。
3,7,19，N，N，6,8，N，N，N，N，N，N
將3指定爲正確的孩子。

考慮11節點 - >它是一個值，分配小孩：
7,19，N，N，6,8，N，N，N，N，N，N
分配7爲左兒童。
19，N，N，6,8，N，N，N，N，N，N
將19指定爲正確的孩子。
//完成整個深度1

考慮N爲節點 - >不是值，繼續下一個廣度節點。
考慮3作爲節點 - >它是一個值，指定子節點：
N，N，6,8，N，N，N，N，N，N
將N指定爲左子節點。
N，6,8，N，N，N，N，N，N
將N指定爲正確的孩子。

考慮7爲節點 - > ...等

你建立一棵樹，你analise您輸入的字符串，並使用廣度優先搜索到達這個下一個葉建立樹，如果它有一個有效的值，然後它將輸入字符串中的下兩個元素分配爲左側和右側的子元素。

Answer 2

要對通過廣度優先遍歷生成的字符串進行反串行化，基本上使用相同的機制。使用一個隊列，您可以將引用放到要注入新孩子的地方。在注入新的子節點時，在隊列中添加兩個更多的引用，每個大孩子一個引用。

由於隊列是FIFO，所以子節點的注入將以寬度優先的順序發生。

這裏是它會怎樣看在Python：

def to_tree(serialised): 
    container = [None] 
    leaves = [[container, 0]] # put the reference to the root on the queue 

    for value in serialised.split(","): 
     children, childIndex = leaves.pop(0) # pull from queue 
     if value != 'N': 
      node = children[childIndex] = { 
       "value": value, 
       "children": [None, None] 
      } 
      # append the new 2 child references to the queue 
      leaves.append([node["children"], 0]) 
      leaves.append([node["children"], 1]) 
     if len(leaves) == 0: # should not happen if input is complete 
      break 

    return container[0] # return the root 

# Example call 
tree = to_tree("5,2,11,N,3,7,19,N,N,6,8,N,N,N,N,N,N") 

# Output the result in JSON format 
import json 
print(json.dumps(tree, indent=2)) 

上面的輸出是：

{ 
    "value": "5", 
    "children": [ 
    { 
     "value": "2", 
     "children": [ 
     null, 
     { 
      "value": "3", 
      "children": [ 
      null, 
      null 
      ] 
     } 
     ] 
    }, 
    { 
     "value": "11", 
     "children": [ 
     { 
      "value": "7", 
      "children": [ 
      { 
       "value": "6", 
       "children": [ 
       null, 
       null 
       ] 
      }, 
      { 
       "value": "8", 
       "children": [ 
       null, 
       null 
       ] 
      } 
      ] 
     }, 
     { 
      "value": "19", 
      "children": [ 
      null, 
      null 
      ] 
     } 
     ] 
    } 
    ] 
}