1


class Node:
    def __init__(self,data):
        self.left= None
        self.right=None
        self.data=data

    def degree(self):
        n=0
        if left:
            n=n+1
        if right:
            n=n+1
        return n
    def find(self,data):
        if self.data:
            if data ==self.data:
                return True
            elif data>self.data:
                if self.right:
                    return self.right.find(data)
                else:
                    return False
            elif data<self.data:
                if self.left:
                    return self.left.find(data)
                else:
                    return False
        else:
            return False

    def insert(self,data):
        if self.data:

            if data<self.data:
                if self.left is None:
                    self.left=Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
    def printTree(self):
        if self.left:
            self.left.printTree()
        print(self.data),
        if self.right:
            self.right.printTree()
    def depth_first(self,root):
        res=[]
        if root:
            res.append(root.data)
            res=res+self.depth_first(root.left)
            res=res+self.depth_first(root.right)



a=Node(1)
a.insert(2)
a.insert(3)
a.insert(0)
a.printTree()

я исправила и добавила параметр depth( но выводит тоже самое, почему?)

 def depth_first(self,root):
        res=[]
        if root:
            res.append(root.data)
            res=res+self.depth_first(root.left)
            res=res+self.depth_first(root.right)



a=Node(10)
a.insert(2)
a.insert(3)
a.insert(0)
a.insert(1)
a.insert(15)
a.insert(45)
a.insert(60)
a.insert(17)
a.insert(6)
a.printTree(depth=1)```
13
  • Если я правильно понял вопрос, это возможно в терминале только для полных деревьев. Уточните вопрос
    – dIm0n
    15 окт 2020 в 17:06
  • у меня не полное ? 15 окт 2020 в 18:44
  • Ну вам лучше знать :) В метках просто бинарное
    – dIm0n
    15 окт 2020 в 18:45
  • что значит полное ? 15 окт 2020 в 18:49
  • 1
    Мне показалось, что надо ввести, а не вывести. Тогда любое бинарное дерево можно. Вот пример geeksforgeeks.org/print-binary-tree-2-dimensions
    – dIm0n
    15 окт 2020 в 19:01

2 ответа 2

2

для печати красивого дерева нам понадобится добавить расчет самой левой его части для того, что бы сдвинуть остальное дерево на экране

class Node:
    # остальной класс Node остается как есть, добавим несколько новых методов, которые нам понадобятся

    def get_min_x(self, x=0):
        """вычисляет координату Х самой левой точки дерева"""
        return min(
            self.left.get_min_x(x-1) if self.left else x,
            self.right.get_min_x(x + 1) if self.right else x,
        )
        
    def prepare_position_to_print(self, x_position, y_position, result_tree=[]):
        """подготавливаем текущий лист дерева для печати"""
        while len(result_tree) < y_position:
            result_tree.append([])
        while len(result_tree[y_position-1]) <= x_position:
            result_tree[y_position-1].append(' ')  # по уму бы здесь не добавлять два пробела, а сначала вычислить самое длинное число в дереве, что бы здесь печатать достаточное количество пробелов
        result_tree[y_position-1][x_position] = str(self.data)
        if self.left:
            self.left.prepare_position_to_print(x_position=x_position-1, y_position=y_position+1, result_tree=result_tree)
        if self.right:
            self.right.prepare_position_to_print(x_position=x_position+1, y_position=y_position+1, result_tree=result_tree)

    def print_real_tree(self):
        """печатаем дерево"""
        minimum_x = self.get_min_x()
        result_tree = []
        self.prepare_position_to_print(
            x_position=-minimum_x,
            y_position=1,
            result_tree=result_tree
        )
        for level in result_tree:
            print('  '.join(level))

a=Node(3)
a.insert(5)
a.insert(2)
a.insert(0)
a.insert(4)
a.insert(7)
a.insert(9)
a.print_real_tree()


получаем результат

      3
   2     5
0     4     7
               9

Edit: Вообще, этот алгоритм надо переработать. Он не будет нормально работать для деревьев когда ветки сначала расходятся, потом начинают сходиться.

Edit 2: изменил алгоритм, что бы отрисовывались деревья любого типа

class Node:
    def __init__(self, data=None, values=[]):
        self.left = None
        self.right = None
        self.data = data
        self.x = None
        for value in values:
            self.insert(value)

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data=data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data=data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def get_max_width_of_data(self):
        return max(
            len(str(self.data)),
            self.left.get_max_width_of_data() if self.left else 0,
            self.right.get_max_width_of_data() if self.right else 0,
        )

    def count_all(self):
        return sum([self.left.count_all() if self.left else 0, self.right.count_all() if self.right else 0, 1])

    def count_left(self):
        return self.left.count_all() if self.left else 0

    def count_right(self):
        return self.right.count_all() if self.right else 0

    def prepare_level_to_print(self, max_width_of_data, x_position, y_position, result_tree=[]):
        left_line = 0
        right_line = 0
        if self.left:
            left_line = self.left.count_right() + 1
        if self.right:
            right_line = self.right.count_left() + 1
        while len(result_tree) < y_position:
            result_tree.append([])
        while len(result_tree[y_position-1]) <= x_position + right_line + 1:
            result_tree[y_position-1].append(' ' * max_width_of_data)
        template = '{:0>'+str(max_width_of_data)+'}'
        result_tree[y_position-1][x_position] = template.format(self.data)
        if self.left:
            for x in range(x_position - left_line, x_position):
                result_tree[y_position - 1][x] = '─' * max_width_of_data
            result_tree[y_position - 1][x_position - left_line] = '┌{}'.format('─' * (max_width_of_data-1))
            self.left.prepare_level_to_print(
                max_width_of_data=max_width_of_data,
                x_position=x_position - left_line, y_position=y_position+1, result_tree=result_tree
            )
        if self.right:
            for x in range(x_position + 1, x_position + right_line):
                result_tree[y_position - 1][x] = '─' * max_width_of_data
            result_tree[y_position - 1][x_position + right_line] = '{}┐'.format('─' * (max_width_of_data-1))
            self.right.prepare_level_to_print(
                max_width_of_data=max_width_of_data,
                x_position=x_position + right_line, y_position=y_position+1, result_tree=result_tree
            )

    def print_real_tree(self):
        result_tree = []
        max_width_of_data = self.get_max_width_of_data()
        self.prepare_level_to_print(
            max_width_of_data=max_width_of_data,
            x_position=self.count_left() + 1,
            y_position=1,
            result_tree=result_tree
        )
        for level in result_tree:
            print(' '.join(level))


tree = Node(values=[30, 1, 2, 3, 0, 10, 15, 45, 50, 39, 60, 17, 6, 11, 13, 12, 14, 37, 35, 31])
tree.print_real_tree()

результат работы скрипта

      ┌─ ── ── ── ── ── ── ── ── ── ── 30 ── ── ── ── ─┐   
   ┌─ 01 ─┐                                        ┌─ 45 ─┐   
   00    02 ─┐                                  ┌─ 39    50 ─┐   
            03 ── ─┐                         ┌─ 37          60   
               ┌─ 10 ── ── ── ── ─┐       ┌─ 35   
               06    ┌─ ── ── ── 15 ─┐    31   
                     11 ── ─┐       17   
                        ┌─ 13 ─┐   
                        12    14   
12
  • круто! но у меня при большем ввидении чисел получается. что все дерево справа 15 окт 2020 в 20:00
  • укажи порядок чисел в котором ты добавляешь их к дереву 15 окт 2020 в 20:01
  • a=Node(1) a.insert(2) a.insert(3) a.insert(0) a.insert(10) a.insert(15) a.insert(45) a.insert(60) a.insert(17) a.insert(6) 15 окт 2020 в 20:02
  • указать в коде или здесь? 15 окт 2020 в 20:02
  • ну все правильно , ты числа вводишь практически по возрастанию, понятно, что оно у тебя уедет вправо сильно. Попробуй вручную нарисовать это дерево на листочке бумаги, увидишь, что получится 15 окт 2020 в 20:04
1

Если надо просто красиво напечатать дерево, то в метод printTree() можно добавить параметр depth, отвечающий за число пробелов перед выводимыми данными. При старте depth=0, при печати а в рекурсии этот параметр увеличивается на 1.

    def printTree(self, depth=0):
        if self.left:
            self.left.printTree(depth=depth+1)
        print(' ' * depth, self.data),
        if self.right:
            self.right.printTree(depth=depth+1)
5
  • я исправила, но выводит тоже самое 15 окт 2020 в 18:47
  • def depth_first(self,root): res=[] if root: res.append(root.data) res=res+self.depth_first(root.left) res=res+self.depth_first(root.right) a=Node(1) a.insert(2) a.insert(3) a.insert(0) a.printTree(depth=1) 15 окт 2020 в 18:47
  • что именно делает depth ? 15 окт 2020 в 19:16
  • Параметров depth считает количество пробелов, которое должно быть перед распечатанным узлом.
    – roddar92
    15 окт 2020 в 20:02
  • cпасибо. у меня почему-то не сработало. сейчас пробую другим способом, написанном в комментарии, а у вас так получается? ваш более короткий 15 окт 2020 в 20:03

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.