0

Помогите разобраться, как построить бинарное дерево на Python 3 в скобочной записи?

Структура бинарного дерева следующая:

< бд > ::= < пусто > | (< бд > < буква >< бд >)
< пусто > ::=

И вот пример, соответствующий это структуре (B(C))A(D). В данном случае A - корень дерева

На данный момент получилось сделать процедуру, которая извлекает все буквы из скобочной записи (конечно, довольно кривенько выглядит), но как построить дерево - не получается.

Сам код:

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

class Tree:
    def __init__(self):
        self.root = None

    def myAdd(self, node, data, key):
        if key == None:
            node = Node(data)
        if key == 'left':
            node.left = Node(data)
        if key == 'right':
            node.right = Node(data)

    def addToTree(self, expression):
        self._addToTree(expression, self.root)

    # обработка строки с извлечением букв
    def _addToTree(self, expression, node, key=None):
        if expression:
            if len(expression) == 1:
                self.myAdd(node, expression[0], key)
            else:
                brackets = 0
                index_sym = 0
                expression = list(''.join(expression))
                for inx, sym in enumerate(expression):
                    if sym == '(': brackets += 1
                    if sym == ')': brackets -= 1
                    if (sym != '(') and (sym != ')'): index_sym = inx
                    if (brackets == 0) and (sym != ')') and (sym != '('):
                        index_sym = inx
                        break
                self._addToTree(expression[index_sym], node )
                self._addToTree(expression[1:index_sym], node, 'left')
                self._addToTree(expression[index_sym+2:-1], node, 'right')

    def printTree(self):
        if (self.root != None):
            self._printTree(self.root)

    def _printTree(self, node):
        if (node != None):
            self._printTree(node.left)
            print( str(node.data), end= ' ' )
            self._printTree(node.right)


tree = Tree()
tree.addToTree('((c)b(d))a(((g)f(h))e)')
tree.printTree()

2 ответа 2

2

Для решения задачи лучше всего стоит реализовать процесс восходящего синтаксического анализа "перенос-свёрта". Представьте себе пустой стек и вашу строку (назовём её входной буфер):

stack = []
input = '(B(C))A(D)'

Будем читать символы по-одному из входного буфера в стек и анализировать вершину стека на предмет "интересности"

Шаг 1. ничего интересного

stack = ['(']
input = 'B(C))A(D)'

Шаг 2. ничего интересного

stack = ['(', 'B']
input = '(C))A(D)'

Шаг 3. ничего интересного

stack = ['(', 'B', '(']
input = 'C))A(D)'

Шаг 4. По-прежнему ничего интересного

stack = ['(', 'B', '(', 'C']
input = '))A(D)'

Шаг 5. Уже что-то! Три символа на вершине стека '(', 'C', ')' можно свернуть в вершину дерева со значением 'C' До свёртки:

stack = ['(', 'B', '(', 'C', ')']
input = ')A(D)'

После:

stack = ['(', 'B', Node('C')]

Шаг 6. Делаем ещё перенос:

stack = ['(', 'B', Node('C'), ')']
input = 'A(D)'

И сворачиваем:

stack = [Node('B', None, Node('C'))]

Шаг 7. Переносим:

stack = [Node('B', None, Node('C')), 'A']
input = '(D)'

Шаг 8,9,10. Переносим:

stack = [Node('B', None, Node('C')), 'A', '(', 'D', ')']
input = ''

Шаг 11. Сворачиваем:

stack = [Node('B', None, Node('C')), 'A', Node('D')]

Шаг 12. Сворачиваем:

stack = [Node('A', Node('B', None, Node('C')), Node('D')]

Шаг 13. Входной буфер пуст. В стеке готовое дерево синтаксического разбора :)

Как это выглядело бы в коде:

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

LEFT_BRACKET = 0
RIGHT_BRACKET = 1
DATA = 2
NODE = 3

class Token:
  def __init__(symbol):
    self.value = symbol
    if symbol == '(':
      self.type = LEFT_BRACKET
    elif symbol == ')':
      self.type = RIGHT_BRACKET
    elif symbol.isalpha():
      self.type = DATA
    else:
      self.type = NODE

def try_reduce(stack):
   """
     Набор правил для свёртки. Можно тоже описать каждое правило классом.
     Сколько токенов нужно посмотреть, с какими токенами сравнить и на какой токен 
     заменить.
   """
   for rule in rules:
      result = rule.check(stack)
      if result:
         return;

stack = []
inp_string = '(B(C))A(D)'
while (True):
  if try_reduce(stack):
    continue
  if not len(a):
    return;

  stack.append(Token(a[0]))
  a = a[1:]


Реализацию класса Rule оставлю на додумывание. Прошу прощения за возможные неточности - синтаксическими анализаторами я на самом деле не занимаюсь

3
  • Спасибо за такую подробную реализацию со стеком, но хотелось бы без его использования сделать, а рекурсией (если возможно). Находил вопрос с реализацией дерева на Python, но там дерево бинарного поиска. И каким-то образом, когда передается self.rootв метод _add, то эта переменная выглядит, как ссылка, хотя ссылок в Python нет. Не подскажите, почему так происходит? Commented 7 февр. 2019 в 14:38
  • 1
    Ссылок нет, но значения передаются по ссылке в Питоне: a = []; b = a; b.append(1) посмотрите чему будет равен а Commented 7 февр. 2019 в 14:40
  • Вот оно что. Надо все-таки подтянуть питон) Теперь понятно, почему так можно было использовать. Но почему когда вызываю метод myAdd, то данные перезаписываются, а не сохраняются, как новые объекты? Например, при выводе дерева, выводились левая часть, корень и правая Commented 7 февр. 2019 в 15:00
0

По предыдущему алгоритму (на паскале) получилось сделать следующее:

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

    def __str__(self):
        return str(self.data)

class Tree:
    def __init__(self, expression):
        self.root = None
        self.add(expression)

    def add(self, expression):
        token_list = list(''.join(expression))
        self.root = self._addToTree(token_list)

    def _addToTree(self, token_list):
        if token_list:
            brackets = 0
            index_sym = 0
            for inx, sym in enumerate(token_list):
                if sym == '(': brackets += 1
                if sym == ')': brackets -= 1
                if (sym != '(') and (sym != ')'): index_sym = inx
                if (brackets == 0) and (sym != ')') and (sym != '('):
                    index_sym = inx
                    break
            return Node(self._addToTree(token_list[1:index_sym]),
                        self._addToTree(token_list[index_sym+2:-1]),
                        token_list[index_sym])

    def InOrder(self):
        self._InOrder(self.root)

    def _InOrder(self, node):
        if (node != None):
            self._InOrder(node.left)
            print( str(node.data), end= ' ' )
            self._InOrder(node.right)

    def PreOrder(self):
        self._PreOrder(self.root)

    def _PreOrder(self, node):
        if (node != None):
            print( str(node.data), end= ' ' )
            self._PreOrder(node.left)
            self._PreOrder(node.right)

    def PostOrder(self):
        self._PostOrder(self.root)

    def _PostOrder(self, node):
        if (node != None):
            self._PostOrder(node.left)
            self._PostOrder(node.right)
            print( str(node.data), end= ' ' )

tree = Tree('((c)b(d))a(((g)f(h))e)')

print('Прямой обход')
tree.PreOrder()

print()
print('Концевой обход')
tree.PostOrder()

print()
print('Обратный обход')
tree.InOrder()

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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