Список всех элементов двоичного дерева - PullRequest
Новая
       9

Список всех элементов двоичного дерева

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

Будучи новичком, я пытался реализовать Binary Tree на python. И были доступны, чтобы реализовать много успешно только с одной проблемой, что я не могу вернуть список всех элементов (traverse()) в двоичном дереве. Я использую два класса: Node и BinaryTree.

Node Class 

class Node:
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None

Метод обхода для возврата всех элементов двоичного дерева. 

    def traverse(self): #<-- Problem here
        tree_elements = []
        if self.left != None:
            self.left.traverse()

        tree_elements.append(self.value)

        #debug
        print(self.value, end=" ")

        if self.right != None:
            self.right.traverse()
        return tree_elements

    def addNode(self, node):
        if node.value < self.value and node.value != self.value:
            if self.left == None:
                self.left = node
            else:
                self.left.addNode(node)
        elif node.value > self.value and node.value != self.value:
            if self.right == None:
                self.right = node
            else:
                self.right.addNode(node)

    def search(self, val):
        if val == self.value:
            return "Found"

        elif val < self.value:
            if self.left != None:
                return self.left.search(val)
            else:
                return "Not Found "
        elif val > self.value:
            if self.right != None:
                return self.right.search(val)
            else:
                return "Not Found"

Двоичное дерево 

class BinaryTree:
    def __init__(self):
        self.root = None

    def addVlaue(self, val):
        node = Node(val)
        if self.root == None:
            self.root = node
        else:
            self.root.addNode(node)

     def search(self, val):
         if self.root == None:
             return False
         else:
             return self.root.search(val)

    def traverse(self):
         if self.root == None:
             return "no data"
        else:
            return self.root.traverse()

Проблема:

traverse метод должен вернуть все элементы в двоичном дереве, но я получаю только первое значение дерева.

пример:

элементы: 100 18 46 5 65 5 31 71 94 43 # вход в дерево

вывод из дерева: 5 18 31 43 46 65 71 94 100 #ожидаемый вывод

[100] # выход из дерева

1 Ответ

2 голосов
/ 03 октября 2019

Список tree_elements должен проходить по рекурсивным вызовам, собирая каждый узел по пути. Другими словами, он должен передаваться в качестве аргумента traverse вызовам (кроме случаев, когда вызывается traverse для корневого узла).

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

Попробуйте эту реализацию: 

def traverse(self, tree_elements=None):
    if tree_elements is None:
        tree_elements = []
   if self.left != None:
        self.left.traverse(tree_elements=tree_elements)
    tree_elements.append(self.value)
    if self.right != None:
        self.right.traverse(tree_elements=tree_elements)
    return tree_elements
...