时间戳

首页 > 解决方案 > 如何在不达到 Python 中的最大迭代次数的情况下将字符串数组添加到二叉树中？

python - 如何在不达到 Python 中的最大迭代次数的情况下将字符串数组添加到二叉树中？

问题描述

我有一本包含 370100 个元素（字符串）的单词字典。我需要将它们添加到二叉树中以对它们进行排序和查找。在不达到 python 的最大迭代次数的情况下，我将如何做到这一点？我尝试使用 sys.setrecursionlimit 但它很慢并最终吐出 zsh：segmentation fault python tree.py。

import sys

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)

def toArr(txtfile):
txtArr = []
file = txtfile
for line in file:
    txtArr.append(line)
return txtArr



dictionary = open('dictionary.txt', 'r')
dic = toArr(dictionary)
sys.setrecursionlimit(370100)

tree = create(dic)

print_tree(tree)

这就是我所拥有的。任何解决方案将不胜感激！:)

标签： pythonrecursionbinary-tree

解决方案

我将假设您的代码没有任何问题（至少没有太大问题），而是您的数据有问题。如果您的输入已排序，您最终会出现堆栈溢出——这种方法假设数据是随机分散的。否则，你最终会得到一棵不平衡的树和堆栈溢出。使用我自己的 250K 单词的测试列表，如果我对它们进行洗牌，我就能让你的代码正常工作，如果我对它们进行排序，我就能让你的代码中断。

我对您的代码进行了修改，以将您的一些函数转换为方法：

class Node():

    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 print_tree(self):
        if self.left:
            self.left.print_tree()

        print(self)

        if self.right:
            self.right.print_tree()

    def search(self, word, depth=1):
        if self.value == word:
            return depth, self.count

        if word < self.value:
            if self.left:
                return self.left.search(word, depth + 1)
        else:
            if self.right:
                return self.right.search(word, depth + 1)

        return 0, 0

def insert(root, value):
    if not root:
        return Node(value)

    if 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 toArr(txtfile):
    with open(txtfile) as file:
        return [line.rstrip('\n') for line in file]

array = toArr('dictionary.txt')

tree = create(array)

tree.print_tree()

推荐阅读