Рекурсивное создание двоичного дерева с учетом строкового выражения в префиксной нотации в Python - PullRequest
Новая
       13

Рекурсивное создание двоичного дерева с учетом строкового выражения в префиксной нотации в Python

0 голосов
/ 24 ноября 2018

Представление LinkedBinaryTree, которое должно быть выведено
import LinkedBinaryTree 

def create_expression_tree(prefix_exp_str):

    def create_expression_tree_helper(prefix_exp, start_pos):
        start_pos += 1
        op = ['+', '-', '*', '/']
        elem = prefix_exp[start_pos]
        if elem == ' ':
            elem = prefix_exp[start_pos+1]
            start_pos += 1

        if elem not in op:
            return LinkedBinaryTree.LinkedBinaryTree.Node(int(elem))
        else:
            left = create_expression_tree_helper(prefix_exp, start_pos)
            right = create_expression_tree_helper(prefix_exp, start_pos+2)
            return LinkedBinaryTree.LinkedBinaryTree.Node(elem, left, right)

    tree = LinkedBinaryTree.LinkedBinaryTree(create_expression_tree_helper(prefix_exp_str, -1))

    return tree

tree1 = create_expression_tree('* 2 + - 15 6 4')
for i in tree1.preorder():
    print(i.data, end='')

Я реализовал свой собственный класс двоичного дерева, который показан ниже.Preorder () - это генератор для моего LinkedBinaryTree, который выдает значения дерева в порядке префикса.С помощью этого кода я вывожу * 2 + -151, но он должен выводить * 2 + -1564, если дерево двоичных выражений было создано правильно.Мне известно, что существует проблема с числами, превышающими 1 цифру, но я не уверен, как ее исправить, не ставя под угрозу время выполнения (т. Е. Используя нарезку).Также я не уверен, почему он опускает некоторые из токенов.Есть идеи?(Реализация должна выполняться за линейное время и не использовать никаких дополнительных параметров в определенной мной вспомогательной функции).

import ArrayQueue

class LinkedBinaryTree:

    class Node:
        def __init__(self, data, left=None, right=None):
            self.data = data
            self.parent = None
            self.left = left
            if (self.left is not None):
                self.left.parent = self
            self.right = right
            if (self.right is not None):
                self.right.parent = self

    def __init__(self, root=None):
        self.root = root
        self.size = self.subtree_count(root)

    def __len__(self):
        return self.size

    def is_empty(self):
        return len(self) == 0

    def subtree_count(self, root):
        if (root is None):
            return 0
        else:
            left_count = self.subtree_count(root.left)
            right_count = self.subtree_count(root.right)
            return 1 + left_count + right_count


    def sum(self):
        return self.subtree_sum(self.root)

    def subtree_sum(self, root):
        if (root is None):
            return 0
        else:
            left_sum = self.subtree_sum(root.left)
            right_sum = self.subtree_sum(root.right)
            return root.data + left_sum + right_sum


    def height(self):
        return self.subtree_height(self.root)

    def subtree_height(self, root):
        if (root.left is None and root.right is None):
            return 0
        elif (root.left is  None):
            return 1 + self.subtree_height(root.right)
        elif (root.right is  None):
            return 1 + self.subtree_height(root.left)
        else:
            left_height = self.subtree_height(root.left)
            right_height = self.subtree_height(root.right)
            return 1 + max(left_height, right_height)


    def preorder(self):
        yield from self.subtree_preorder(self.root)

    def subtree_preorder(self, root):
        if(root is None):
            return
        else:
            yield root
            yield from self.subtree_preorder(root.left)
            yield from self.subtree_preorder(root.right)


    def postorder(self):
        yield from self.subtree_postorder(self.root)

    def subtree_postorder(self, root):
        if(root is None):
            return
        else:
            yield from self.subtree_postorder(root.left)
            yield from self.subtree_postorder(root.right)
            yield root


    def inorder(self):
        yield from self.subtree_inorder(self.root)

    def subtree_inorder(self, root):
        if(root is None):
            return
        else:
            yield from self.subtree_inorder(root.left)
            yield root
            yield from self.subtree_inorder(root.right)


    def breadth_first(self):
        if (self.is_empty()):
            return
        line = ArrayQueue.ArrayQueue()
        line.enqueue(self.root)
        while (line.is_empty() == False):
            curr_node = line.dequeue()
            yield curr_node
            if (curr_node.left is not None):
                line.enqueue(curr_node.left)
            if (curr_node.right is not None):
                line.enqueue(curr_node.right)

    def __iter__(self):
        for node in self.breadth_first():
            yield node.data

Я добавил здесь код для класса LinkedBinaryTree.Класс ArrayQueue, который используется в реализации метода обхода в ширину, является просто базовой очередью, использующей список Python в качестве базовой структуры данных.

1 Ответ

0 голосов
/ 25 ноября 2018

Две проблемы с вашим кодом:

  • вы обрабатывали символы один за другим, в то время как могли присутствовать многозначные числа (исправлено путем разделения выражения на список)
  • вы не учли тот факт, что цепочечные операторные выражения могут быть длиннее, чем просто ваше стандартное приращение (исправлено добавлением свойства size к Node

Итак, вот новый Nodeкласс 

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.parent = None
        self.left = left
        if (self.left is not None):
            self.left.parent = self
        self.right = right
        if (self.right is not None):
            self.right.parent = self

    @property
    def size(self):
        l = 1
        if self.left is not None:
            l += self.left.size
        if self.right is not None:
            l += self.right.size
        return l

и вот новый создатель дерева 

def create_expression_tree(prefix_exp_str):

    expr_lst = prefix_exp_str.split(" ")

    op = {'+': None, '-': None, '*': None, '/': None}

    def create_expression_tree_helper(prefix_exp, start_pos):
        start_pos += 1
        elem = prefix_exp[start_pos]

        node = None

        if elem not in op:
            node = LinkedBinaryTree.Node(int(elem))
        else:
            left = create_expression_tree_helper(prefix_exp, start_pos)
            incr = left.size
            right = create_expression_tree_helper(prefix_exp, start_pos+incr)
            node = LinkedBinaryTree.Node(elem, left, right)

        return node

    tree = LinkedBinaryTree(create_expression_tree_helper(expr_lst, -1))

    return tree

РЕДАКТИРОВАТЬ вот версия, не требующая изменения Node класса 

def create_expression_tree(prefix_exp_str):

    expr_lst = prefix_exp_str.split(" ")

    op = {'+': None, '-': None, '*': None, '/': None}

    def create_expression_tree_helper(prefix_exp, start_pos):
        start_pos += 1
        elem = prefix_exp[start_pos]

        node = None
        size = 1

        if elem not in op:
            node = LinkedBinaryTree.Node(int(elem))
        else:
            left, left_size   = create_expression_tree_helper(prefix_exp, start_pos)
            right, right_size = create_expression_tree_helper(prefix_exp, start_pos+left_size)

            node  = LinkedBinaryTree.Node(elem, left, right)
            size += left_size + right_size

        return node, size

    tree = LinkedBinaryTree(create_expression_tree_helper(expr_lst, -1)[0])

    return tree
...