Десериализовать двоичное дерево поиска из строки

Помните, что это поиск по бинарному дереву, что означает, что у каждого узла есть только два потомка, левый и правый.

(Предполагая, что N означает Null/no node): создайте свое дерево. Первый элемент в вашей входной последовательности является корневым элементом, следующие два назначаются как левый дочерний элемент корня, а затем правый дочерний элемент. Затем с помощью 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< br/> Назначить 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 как узел -> ... и т. д.

Вы строите дерево, когда анализируете свою входную строку, и используете поиск в ширину, чтобы добраться до следующего листа в этом построенном дереве, если оно имеет допустимое значение, то оно получает следующие два элемента в вашей входной строке как левый и правильные дети.

Чтобы десериализовать строку, сгенерированную с помощью обхода в ширину, вы, по сути, используете ту же механику. Используйте очередь, в которую вы помещаете ссылки на то, куда должны быть введены новые дочерние элементы. Когда вы вводите новый дочерний узел, добавьте в очередь еще две ссылки, по одной для каждого большого дочернего узла.

Так как очередь 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
          ]
        }
      ]
    }
  ]
}