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 нет. Не подскажите, почему так происходит? 7 фев 2019 в 14:38
  • 1
    Ссылок нет, но значения передаются по ссылке в Питоне: a = []; b = a; b.append(1) посмотрите чему будет равен а 7 фев 2019 в 14:40
  • Вот оно что. Надо все-таки подтянуть питон) Теперь понятно, почему так можно было использовать. Но почему когда вызываю метод myAdd, то данные перезаписываются, а не сохраняются, как новые объекты? Например, при выводе дерева, выводились левая часть, корень и правая 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()

Ваш ответ

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

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