Как мне изменить мой метод для печати всей строки вместо одного элемента в моем двоичном дереве?

Question

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

Когда я пытаюсь использовать этот подход, проблема заключается в том, что при получении элементов из дерева список печатает только самый последний элемент, то есть length = 1. Когда я попытался создать список глобально, все в порядке, но у меня c хотите избежать глобальных переменных. Я свяжу весь код, но в особенности его метод string, который нужно исправить. Код связан с глобальным списком l1.

l1 = []

class BinaryTree:

    def __init__(self):
        """Constructor for the binary tree."""
        self._root = None
        self._left = None
        self._right = None
        self._size = 0
        self.l = []

    def add(self, root):
        """Add a given element to the binary tree."""
        if self._root:
            if root < self._root:
                if self._left is None:
                    self._left = BinaryTree()
                self._left.add(root)
                self._size += 1
            elif root > self._root:
                if self._right is None:
                    self._right = BinaryTree()
                self._right.add(root)
                self._size += 1
        else:
            self._root = root
            self._size = 1

    def string(self):
        '''Prints the entire tree as a string.'''
        #current = self._root
        if self._left:
            self._left.string()
        #print(self._root)
        l1.append(self._root)
        if self._right:
            self._right.string()
        return l1

    def len(self):
        '''Returns the size of the tree (# of elements in the tree).'''
        return self._size

def new():
    """Creates new instance."""
    return BinaryTree()

def main():
    test = new() # Test for new BT
    test.add('c')
    test.add('b')
    test.add('a')
    print(test.string())
    assert test.len() == 3

if __name__ == '__main__': main()

Answer 1

Вы можете использовать свой исходный код только с небольшим изменением строки метода.

Необходимо добавить список 'll' в качестве параметра по умолчанию и добавить его к рекурсивным вызовам следующим образом.

  def string(self, ll = []):
        '''Prints the entire tree as a string.'''
        #current = self._root
        if self._left:
            self._left.string(ll)
        #print(self._root)
        ll.append(self._root)
        if self._right:
            self._right.string(ll)
        return ll

Answer 2

Вы можете упростить свой метод string, включив итерацию в свой класс. Если используется такая методика, вычисление размера структуры может также использовать функцию, как показано в методе __len__, показанном ниже:

#! /usr/bin/env python3
def main():
    test = Node()
    test.add('c')
    test.add('b')
    test.add('a')
    print(test)
    assert len(test) == 3


class Node:

    def __init__(self):
        """Initializes a single node to be used in a Binary Tree."""
        self.__data = None
        self.__left = None
        self.__right = None

    def add(self, data):
        """Incorporates a data value into the Binary Tree structure."""
        if self.__data is None:
            self.__data = data
        elif data < self.__data:
            if self.__left is None:
                self.__left = type(self)()
            self.__left.add(data)
        elif data > self.__data:
            if self.__right is None:
                self.__right = type(self)()
            self.__right.add(data)

    def __str__(self):
        """Converts a Binary Tree into a string suitable for printing."""
        return ''.join(map(str, self))

    def __iter__(self):
        """Iterates over all values in the underlying tree structure."""
        if self.__data is not None:
            if self.__left is not None:
                yield from self.__left
            yield self.__data
            if self.__right is not None:
                yield from self.__right

    def __len__(self):
        """Counts how many data values are stored in the underlying tree."""
        return sum(1 for _ in self)


if __name__ == '__main__':
    main()

Для более интересного теста двоичного дерева вы может прочитать каждый символ из исходного файла и добавить его в структуру. Три кода могут быть добавлены в код для выполнения sh this:

1. import sys
2. A main, модифицированная для получения символов из файла.
3. Метод update, который может помочь с обработкой итерируемых объектов.

---

import sys


def main():
    test = Node()
    with open(sys.argv[0]) as file:
        test.update(character for line in file for character in line)
    print(test)
    print('There are', len(test), 'unique characters in this file.')


class Node:

    def update(self, iterable):
        """Takes all items from an iterable and adds them to the tree."""
        for item in iterable:
            self.add(item)

Убедитесь, что вы добавили метод update в класс Node. То, что показано выше, является неполным, но показывает код, который необходимо добавить, чтобы дать бинарному дереву дополнительную функциональность.

Answer 3

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

См. Метод traverse, который я определил. Это делает упорядоченный обход дерева. Метод string() просто становится str() результата, возвращаемого traverse().

class BinaryTree:

    def __init__(self):
        """Constructor for the binary tree."""
        self._root = None
        self._left = None
        self._right = None
        self._size = 0
        self.l = []

    def add(self, root):
        """Add a given element to the binary tree."""
        if self._root:
            if root < self._root:
                if self._left is None:
                    self._left = BinaryTree()
                self._left.add(root)
                self._size += 1
            elif root > self._root:
                if self._right is None:
                    self._right = BinaryTree()
                self._right.add(root)
                self._size += 1
        else:
            self._root = root
            self._size = 1

    def traverse(self):
        '''Prints the entire tree as a string.'''
        to_print = []
        if self._left:
            to_print.extend(self._left.traverse())
        to_print.append(self._root)
        if self._right:
            to_print.extend(self._right.traverse())
        return to_print

    def string(self):
        return str(self.traverse())

    def len(self):
        '''Returns the size of the tree (# of elements in the tree).'''
        return self._size


def new():
    """Creates new instance."""
    return BinaryTree()


def main():
    test = new()  # Test for new BT
    test.add('c')
    test.add('b')
    test.add('a')
    print(test.traverse())
    assert test.len() == 3


if __name__ == '__main__':
    main()