Помогите разобраться, как построить бинарное дерево на 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()