Предзаказ обхода сбалансированного бинарного дерева - PullRequest
Новая
       24

Предзаказ обхода сбалансированного бинарного дерева

0 голосов
/ 15 февраля 2019

Я выполняю предварительно упорядоченный обход сбалансированного дерева, созданного из отсортированного массива, и не получаю ожидаемых результатов.

Я провел много исследований по этому вопросу, и это последнее средство.Я пробовал разные варианты обходов (по почте и по порядку), которые не дали ожидаемых результатов.Код ниже.

import sys


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


# function to convert sorted array to a
# balanced BST
# input : sorted array of integers
# output: root node of balanced BST
def sort_array_to_bst(arr):
    if not arr:
        return None

    # find middle
    mid = (len(arr)) / 2
    mid = int(mid)

    # make the middle element the root
    root = Node(arr[mid])

    # left subtree of root has all
    # values <arr[mid]
    root.left = sort_array_to_bst(arr[:mid])

    # right subtree of root has all
    # values >arr[mid]
    root.right = sort_array_to_bst(arr[mid + 1:])
    return root


# A utility function to print the pre-order
# traversal of the BST
def pre_order(node):
    if not node:
        return
    if root:

        sys.stdout.write(str(node.data) + ' ')
        pre_order(node.left)
        #sys.stdout.write(str(node.data) + ' ')
        pre_order(node.right)
        #sys.stdout.write(str(node.data) + ' ')

if __name__ == '__main__':
    arr = []
    for line in sys.stdin.readline().strip().split(" "):
        arr.append(line)
    # arr = [7, 898, 157, 397, 57, 178, 26, 679]
    # Expected Output = 178 57 26 157 679 397 898
    narr = arr[1:]
    narr.sort()
    root = sort_array_to_bst(narr)
    pre_order(root)

Массив, вводимый через stdin, равен 7 898 157 397 57 178 26 679, а ожидаемый результат равен 178 57 26 157 679 397 898.Фактический выход составляет 397 178 157 26 679 57 898

1 Ответ

0 голосов
/ 15 февраля 2019

Разобрался.Массив не был отсортирован должным образом.Я изменил narr.sort() на narr = sorted(narr, key=int).Который отсортировал массив, вероятно,

...