Python:使用列表创建二进制搜索树 [英] Python: Create a Binary search Tree using a list

问题描述

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

The objective of my code is to get each seperate word from a txt file and put it into a list and then making a binary search tree using that list to count the frequency of each word and printing each word in alphabetical order along with its frequency. Each word in the can only contain letters, numbers, -, or ' The part that I am unable to do with my beginner programming knowledge is to make the Binary Search Tree using the list I have (I am only able to insert the whole list in one Node instead of putting each word in a Node to make the tree). The code I have so far is this:

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

推荐答案

由于您是初学者，我建议您使用递归而不是迭代的方式来实现树方法，因为这将使实现更简单.虽然一开始递归似乎有点困难，但是通常这是最简单的方法.

Since you're a beginner I'd advice to implement the tree methods with recursion instead of iteration since this will result to simpler implementation. While recursion might seem a bit difficult concept at first often it is the easiest approach.

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

Here's a draft implementation of a binary tree which uses recursion for insertion, searching and printing the tree, it should support the functionality you need.

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)

这篇关于Python:使用列表创建二进制搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！