распечатка списка python из бинарного дерева python

Question

Я хочу определить функцию, которая возвращает список значений узлов дерева. Список находится в порядке уровня (сверху вниз, слева направо), если отсутствует дочерний элемент , то в его местоположении вставлено «None».

Это реализация двоичного дерева

class BinaryTree: 

def __init__(self, data, left = None, right = None): 

    self.left = left 
    self.right = right 

def insert_left(self, data): 
    self.left = BinaryTree(data, left=self.left) 

def insert_right(self, data): 
    self.right = BinaryTree(data, right=self.right) 

def set_value(self, val): 
    self.key = val 

def get_value(self): 
    return self.key 

def create_string(self, indent): 
    string = str(self.key) + '---+' 
    if self.left: 
     string += '\n(l)' + indent + self.left.create_string(indent + ' ') 
    if self.right: 
     string += '\n(r)' + indent + self.right.create_string(indent + ' ') 
    return string 

def __str__(self): 
    return self.create_string(' ') 

def return_list(self, templist): 
    templist.append(self.key) 
    if self.left is None: 
     templist.append(None) 
    else: 
     self.left.return_list(templist) 
    if self.right is None: 
     templist.append(None) 
    else: 
     self.right.return_list(templist) 

def main():  
    tree = BinaryTree(3) 
    tree.insert_left(29) 
    tree.insert_right(4) 
    right = tree.get_right_subtree() 
    left = tree.get_left_subtree() 
    left.insert_left(26) 
    right.insert_right(2) 
    right2 = right.get_right_subtree() 
    right2.insert_left(9) 
    templist = [] 
    tree.return_list(templist) 
main()  

Answer 1

Добавление всего файла .py Если запустить это должно работать

from collections import deque 

class BinaryTree: 
    def __init__(self, data, left = None, right = None): 
     self.key = data 
     self.left = left 
     self.right = right 

    def insert_left(self, data): 
     self.left = BinaryTree(data, left=self.left) 

    def insert_right(self, data): 
     self.right = BinaryTree(data, right=self.right) 

    def get_left_subtree(self): 
     return self.left 

    def get_right_subtree(self): 
     return self.right 

    def set_value(self, val): 
     self.key = val 

    def get_value(self): 
     return self.key 

    def create_string(self, indent): 
     string = str(self.key) + '---+' 
     if self.left: 
      string += '\n(l)' + indent + self.left.create_string(indent + ' ') 
     if self.right: 
      string += '\n(r)' + indent + self.right.create_string(indent + ' ') 
     return string 

    def __str__(self): 
     return self.create_string(' ') 

    def return_list(self, templist): 
     templist.append(self.key) 
     if self.left is None: 
      templist.append(None) 
     else: 
      self.left.return_list(templist) 
     if self.right is None: 
      templist.append(None) 
     else: 
      self.right.return_list(templist) 


def return_b_list(tree,templist,queue): 
    if tree is None: 
     return; 
    queue.append(tree) 
    while len(queue) !=0: 
     node = queue.popleft() 
     if node is None: 
      templist.append(None) 
     else: 
      templist.append(node.key) 
      queue.append(node.left) 
      queue.append(node.right) 




def main():  
    tree = BinaryTree(3) 
    tree.insert_left(29) 
    tree.insert_right(4) 
    right = tree.get_right_subtree() 
    left = tree.get_left_subtree() 
    left.insert_left(26) 
    right.insert_right(2) 
    right2 = right.get_right_subtree() 
    right2.insert_left(9) 
    templist = [] 
    queue = deque() # you should do a from collections import deque 
    return_b_list(tree,templist,queue) 
    print tree.create_string(' ') 
    print templist 

main() 

Answer 2

вы должны передать пустой список этой функции

def return_list(self, templist): 
    templist.append(self.key) 
    if self.left is None: 
     templist.append(None) 
    else: 
     self.left.return_list(templist) 
    if self.right is None: 
     templist.append(None) 
    else: 
     self.right.return_list(templist) 

после того, как вы вызываете этот метод TempList будет иметь список, который вы хотите

Answer 3

Если вы точно ищете ширину первого поиска, то этот метод может помочь

def return_b_list(tree,templist,queue): 
    if tree is None: 
     return; 
    queue.append(tree) 
    while len(queue) !=0: 
     node = queue.popleft() 
     if node is None: 
      templist.append(None) 
     else: 
      templist.append(node.key) 
      queue.append(node.left) 
      queue.append(node.right) 

Как позвонить? (Этот метод не должен быть частью класса)

def main():  
    tree = BinaryTree(3) 
    tree.insert_left(29) 
    tree.insert_right(4) 
    right = tree.get_right_subtree() 
    left = tree.get_left_subtree() 
    left.insert_left(26) 
    right.insert_right(2) 
    right2 = right.get_right_subtree() 
    right2.insert_left(9) 
    templist = [] 
    queue = deque() # you should do a from collections import deque 
    return_b_list(tree,templist,queue) 
    print templist 

Answer 4

Это не ответ, но просто хотел бы добавить результат, что я получаю и разъяснение

$ python binarayTree.py 
3---+ 
(l) 29---+ 
(l)  26---+ 
(r) 4---+ 
(r)  2---+ 
(l)   9---+ 

[3, 29, 4, 26, None, None, 2, None, None, 9, None, None, None] 

Вот объяснение результата список

first level 3 
second level 29,4 
third level 26, None, None ,2 
fourth level None, None,9, None, None, None