Как я могу получить все дочерние узлы общего дерева в Python - PullRequest
Новая
       35

Как я могу получить все дочерние узлы общего дерева в Python

0 голосов
/ 13 октября 2019

Мое дерево имеет следующую структуру: tree = {'0' :( '1', '2', '3'), '1' :( '4'), '2' :( '5',«6»), «3» :(), «4» :( «7», «8»), «8» :( «9», «10», «11»)}

Как я могу написать код Python для извлечения всех заданных дочерних узлов определенного узла? Например, если я даю ему узел 4, код должен получить 7,8,9,10,11. Для узла 2 он должен получить 5, 6 и т. Д.

Я только начал изучать основы Python, но не знаю, как реализовать это для недвоичных деревьев ..

1 Ответ

1 голос
/ 13 октября 2019

Вы можете использовать очередь.

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

tree={'0':('1','2','3'), '1':('4'), '2':('5','6'), '3':(), '4':('7','8'), '8':('9','10','11')}

num = input("what you want ")

q = queue.Queue()

q.put(num)

while not q.empty():
  n = q.get()
  for s in n:
    print(s)
    if s in tree:
      q.put(tree[s])

Demo

Обратите внимание, что если у вас есть дерево tree={'0':('1'), '1':('0')} или любая другая циклическая ссылка, этот код будет работать вечно. Будьте осторожны!

...