Печать бинарного дерева на питоне - PullRequest
Новая
       22

Печать бинарного дерева на питоне

0 голосов
/ 11 декабря 2019

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

497985
406204
477464

Но программа должна напечатать это: 

.....497985
406204
.....477464

Я не знаю, в чем проблема. Я начинающий в программировании, так что если кто-нибудь может мне помочь, это было бы здорово

from numpy.random import randint
import random
from timeit import default_timer as timer


class binarytree:
    def __init__(self):
        self.elem = 0
        self.left = None
        self.right = None


def printtree(tree, h):
    if tree is not None:
        printtree(tree.right, h+1)
        for i in range(1, h):
            print(end = ".....")
        print(tree.elem)
        printtree(tree.left, h+1)


def generate(tree, N, h):
    if N == 0:
        tree = None
    else:
        tree = binarytree()
        x = randint(0, 1000000)
        tree.elem = int(x)
        generate(tree.left, N // 2, h)
        generate(tree.right, N - N // 2 - 1, h)
    printtree(tree, h)

tree = binarytree()
generate(tree, 3, 0)

1 Ответ

1 голос
/ 11 декабря 2019

Я переписал ваш код, чтобы он был немного более Pythonic, и исправил то, что казалось некоторыми ошибками: 

from  random import randrange

class BinaryTree:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    @classmethod
    def generate_random_tree(cls, depth):
        if depth > 0:
            return cls(randrange(1000000),
                       cls.generate_random_tree(depth - 1),
                       cls.generate_random_tree(depth - 1))
        return None

    def __str__(self):
        """
        Overloaded method to format tree as string
        """
        return "\n".join(self._format())

    def _format(self, cur_depth=0):
        """
        Format tree as string given current depth. This is a generator of
        strings which represent lines of the representation.
        """
        if self.right is not None:
            yield from self.right._format(cur_depth + 1)
        yield "{}{}".format("." * cur_depth, self.val)
        if self.left is not None:
            yield from self.left._format(cur_depth + 1)

print(BinaryTree.generate_random_tree(4))
print()
print(BinaryTree(1,
                 BinaryTree(2),
                 BinaryTree(3,
                            BinaryTree(4),
                            BinaryTree(5))))

Это выводит дерево, которое растет из корня в середине. слева направо: 

...829201
..620327
...479879
.746527
...226199
..463199
...498695
987559
...280755
..168727
...603817
.233132
...294525
..927571
...263402

..5
.3
..4
1
.2

Здесь напечатано одно случайное дерево и одно дерево, которое я построил вручную. Я написал это так, чтобы «правильное» поддерево печаталось сверху - вы можете поменять его, если хотите.

Вы можете внести некоторые дополнительные изменения в это, сделав больше точек одновременно (что, я думаю,был ваш h параметр?), или адаптировать биты к любой структуре программы, которую вы хотите.

Этот код работает, потому что он сначала гарантирует, что он строит целое дерево, а затем печатает его. Это четкое разграничение позволяет убедиться, что вы все понимаете правильно. Ваш код был немного запутан в этом отношении - ваша функция generate создавала новый BinaryTree при каждом вызове, но вы никогда не связывали ни одного из них друг с другом! Это потому, что когда вы делаете tree = ... внутри своей функции, все, что вы делаете, это изменяет то, на что указывает локальное имя tree - оно не меняет атрибут дерева с более высокого уровня, который вы передаете ему!

Ваш генератор также вызывает printtree каждый раз, но printtree также вызывает сам себя ... Кажется, это не совсем правильно.

В моей программе этот бит генерируетслучайное дерево: 

    def generate_random_tree(cls, depth):
        if depth > 0:
            return cls(randrange(1000000),
                       cls.generate_random_tree(depth - 1),
                       cls.generate_random_tree(depth - 1))
        return None

Бит метода класса - это просто объектно-ориентированный материал Python, который не очень важен для алгоритма. Главное, что нужно увидеть, это то, что он генерирует два новых меньших дерева, и они в итоге становятся атрибутами left и right дерева, которое оно возвращает. (Это также работает, потому что я немного переписал __init__).

Этот бит в основном печатает дерево: 

    def _format(self, cur_depth=0):
        """
        Format tree as string given current depth. This is a generator of
        strings which represent lines of the representation.
        """
        if self.right is not None:
            yield from self.right._format(cur_depth + 1)
        yield "{}{}".format("." * cur_depth, self.val)
        if self.left is not None:
            yield from self.left._format(cur_depth + 1)

Это генератор строк - но вы могли бы сделатьон напрямую печатает дерево, изменяя каждый yield ... на print(...) и удаляя yield from s. Ключевыми вещами здесь являются cur_depth, который позволяет функции знать, как глубоко в дереве она находится в данный момент, поэтому он знает, сколько точек печатать, и тот факт, что он рекурсивно вызывает себя для левого и правого поддеревьев (и вы должны проверить, если они None или нет, конечно.)

(Эту часть вы можете изменить, чтобы заново ввести h).

...