Python: 使用列表创建二叉搜索树

Question

我的代码的 objective 是从 txt 文件中获取每个单独的单词并将其放入列表中，然后使用该列表制作二叉搜索树以计算每个单词的频率并打印每个单词按字母顺序排列的单词及其出现频率。中的每个单词只能包含字母、数字、- 或 ' 我的初学者编程知识无法做到的部分是使用我拥有的列表制作二叉搜索树（我只能插入整个列表在一个节点中，而不是将每个单词放在一个节点中来制作树）。到目前为止我的代码是这样的：

def read_words(filename):
    openfile = open(filename, "r")
    templist = []
    letterslist = []
    for lines in openfile:
        for i in lines:
            ii = i.lower()
            letterslist.append(ii)
    for p in letterslist:
        if p not in ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',"'","-",' '] and p.isdigit() == False:
            letterslist.remove(p)      
    wordslist = list("".join(letterslist).split())
    return wordslist

class BinaryTree:
    class _Node:
        def __init__(self, value, left=None, right=None):
            self._left = left
            self._right = right
            self._value = value
            self._count = 1


    def __init__(self):
        self.root = None

    def isEmpty(self):
        return self.root == None

    def insert(self, value) :
        if self.isEmpty() :
            self.root = self._Node(value)
            return
        parent = None
        pointer = self.root
        while (pointer != None) :
            if value == pointer._value:
                pointer._count += 1
                return

            elif value < pointer._value:
                parent = pointer
                pointer = pointer._left

            else :
                parent = pointer
                pointer = pointer._right            

        if (value <= parent._value) :
            parent._left = self._Node(value)
        else :
            parent._right = self._Node(value)    

    def printTree(self):
        pointer = self.root
        if pointer._left is not None:
            pointer._left.printTree()
        print(str(pointer._value) + " " + str(pointer._count))
        if pointer._right is not None:
            pointer._right.printTree()




    def createTree(self,words):
        if len(words) > 0:
            for word in words:
                BinaryTree().insert(word)
            return BinaryTree()
        else:
            return None

    def search(self,tree, word):
        node = tree
        depth = 0
        count = 0
        while True:
            print(node.value)
            depth += 1
            if node.value == word:
                count = node.count
                break
            elif word < node.value:
                node = node.left
            elif word > node.value:
                node = node.right
        return depth, count


def main():
    words = read_words('sample.txt')
    b = BinaryTree()
    b.insert(words)
    b.createTree(words)
    b.printTree()

Answer 1

由于您是初学者，我建议您使用递归而不是迭代来实现树方法，因为这会使实现更简单。虽然递归一开始可能看起来有点困难，但它通常是最简单的方法。

这是一个二叉树的实现草案，它使用递归来插入、搜索和打印树，它应该支持您需要的功能。

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.count = 1

    def __str__(self):
        return 'value: {0}, count: {1}'.format(self.value, self.count)

def insert(root, value):
    if not root:
        return Node(value)
    elif root.value == value:
        root.count += 1
    elif value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)

    return root

def create(seq):
    root = None
    for word in seq:
        root = insert(root, word)

    return root

def search(root, word, depth=1):
    if not root:
        return 0, 0
    elif root.value == word:
        return depth, root.count
    elif word < root.value:
        return search(root.left, word, depth + 1)
    else:
        return search(root.right, word, depth + 1)

def print_tree(root):
    if root:
        print_tree(root.left)
        print root
        print_tree(root.right)

src = ['foo', 'bar', 'foobar', 'bar', 'barfoo']
tree = create(src)
print_tree(tree)

for word in src:
    print 'search {0}, result: {1}'.format(word, search(tree, word))

# Output
# value: bar, count: 2
# value: barfoo, count: 1
# value: foo, count: 1
# value: foobar, count: 1
# search foo, result: (1, 1)
# search bar, result: (2, 2)
# search foobar, result: (2, 1)
# search bar, result: (2, 2)
# search barfoo, result: (3, 1)

Answer 2

为了回答你的直接问题，你将所有单词放在一个节点中的原因是因为 main() 中的以下语句：

b.insert(words)

插入函数创建一个 Node 并将节点的值设置为您传入的项目。相反，您需要为列表中的每个项目创建一个节点，这就是您的 createTree() 功能。前面的b.insert不需要。

删除那条线使您的树形成正确，但揭示了数据结构设计的一个基本问题，即 printTree() 方法。该方法似乎旨在遍历树并在任何 child 上递归调用自身。在您的初始版本中，此函数有效，因为树是 mal-formed，整个列表中只有一个节点（打印函数只是打印该值，因为 right 和 left 都是空的）。

然而，对于正确形成的树，printTree() 函数现在会尝试在左右后代上调用自身。然而，后代是 _Node 类型，而不是 BinaryTree 类型，并且没有为 _Node objects.

声明的方法 printTree()

您可以通过以下两种方式之一挽救您的代码并解决这个新错误。首先，您可以将 BinaryTree.printTree() 函数实现为 _Node.printTree()。你不能直接复制和粘贴，但函数的逻辑不必改变太多。或者您可以将方法保留在原处，但将每个 _left 或 _right 节点包装在新的 BinaryTree 中，以便它们具有必要的 printTree() 方法。这样做会使方法留在原处，但您仍然必须在 _Node.

中实现某种辅助遍历方法

最后，您可以将所有 _Node objects 更改为 _BinaryTree objects。

节点和树之间的语义差异是范围之一。一个节点应该只知道它自己，它的直接children（左和右），可能还有它的parent。另一方面，一棵树可以知道它的任何后代，无论相距多远。这是通过将 any child 节点视为自己的树来实现的。即使是没有任何 children 的叶子也可以被认为是一棵深度为 0 的树。这种行为让树递归地工作。您的代码将两者混合在一起。

Python: 使用列表创建二叉搜索树

Python: Create a Binary search Tree using a list

python

nodes

binary-search-tree