从字符串反序列化二进制搜索树

问题描述：

只是练习并注意到它很容易序列化（通过深度优先搜索遍历）一个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

哪种编程语言？这是您忘记添加的最重要的标签。其次，你有什么尝试，你卡在哪里？ – trincot

3应该有孩子N N – Smiley

答

请记住，这是二进制树搜索，这意味着每个节点只有两个孩子，左和右。

（假设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您输入的字符串，并使用广度优先搜索到达这个下一个叶建立树，如果它有一个有效的值，然后它将输入字符串中的下两个元素分配为左侧和右侧的子元素。

答

要对通过广度优先遍历生成的字符串进行反串行化，基本上使用相同的机制。使用一个队列，您可以将引用放到要注入新孩子的地方。在注入新的子节点时，在队列中添加两个更多的引用，每个大孩子一个引用。

由于队列是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 
      ] 
     } 
     ] 
    } 
    ] 
}

从字符串反序列化二进制搜索树

相关推荐