如何修改我的方法以打印整个字符串而不是二叉树中的一个元素？

Question

所以我设法构建了我的 string 方法来打印我的二叉树中的元素，但问题是我希望它将整个二叉树打印为 one 字符串不是元素分开的。我的尝试是创建一个附加元素的列表，然后只打印列表。

当我尝试这种方法时，问题是当从树中获取元素时，列表只打印最新的元素，即长度 = 1。当我尝试全局创建列表时，一切都很好，但我想避免全局变量。我将 link 整个代码，但特别是需要修复的 string 方法。代码 linked 与全局列表 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

您可以 return 来自递归调用的节点并在调用方法中累积，而不是使用全局变量来累积结果。

请参阅我定义的 traverse 方法。它正在对树进行有序遍历。 string()方法就变成了traverse().

返回结果的str()

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()

Answer 2

您可以使用您的原始代码，只需对方法字符串进行少量更改。

需要添加列表 '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 3

您可以通过将迭代合并到 class 中来简化 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()

为了对二叉树进行更有趣的测试，您可以从源文件中读取每个字符并将其添加到结构中。可以在代码中添加三个项目来完成此操作：

import sys
已修改 main 函数以从文件中获取字符。
一个 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 class。上面显示的内容不完整，但显示了需要添加的代码以赋予二叉树额外的功能。

如何修改我的方法以打印整个字符串而不是二叉树中的一个元素？

How do I modify my method to print the entire string instead of just one element in my binary tree?

python

binary-tree

binary-search-tree

python-3.x