Рекурсивная функция для создания бинарного дерева поиска - PullRequest
Новая
       57

Рекурсивная функция для создания бинарного дерева поиска

1 голос
/ 03 мая 2020

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

Вопрос в следующем: Учитывая отсортированный (в порядке возрастания) массив с уникальными целочисленными элементами, напишите алгоритм для создания двоичного дерева поиска с минимальной высотой.

Вот моя попытка. 

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

class binaryTree:
    def __init__(self,nodes,root):
        self.nodes = nodes
        self.root = root

def minimalTree(sortedArray):
    if not sortedArray:
        return None

    else:
        lengthArray = len(sortedArray)
        middle = lengthArray//2
        print("middle = ", middle)
        root = Node(sortedArray[middle])
        leftArray = array.array('i',[])
        rightArray = array.array('i',[])
        if middle == 0:
            return root
        if middle > 0:
            leftArray = sortedArray[0:middle]
            root.left = Node(leftArray[len(leftArray)//2])

        if middle + 1 < lengthArray: 
            rightArray = sortedArray[middle+1:lengthArray]
            root.right = Node(leftArray[len(rightArray)//2])

        return minimalTree(leftArray),minimalTree(rightArray)

Как видите, я на самом деле не использую класс binaryTree, но я не уверен, что он полезен, поскольку дерево может быть задано его root.

Тем не менее я борюсь с рекурсивными алгоритмами, и я не понимаю, почему этот ничего не возвращает.

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

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

1 Ответ

1 голос
/ 03 мая 2020

Необходимые исправления в функции minimalTree

Требуется базовый случай, который возвращается, когда массив пуст 

if lengthArray == 0:
  return None

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

# Array split a middle
leftArray = sortedArray[0:middle]
rightArray = sortedArray[middle+1:lengthArray]

# Left side recursion
root.left = minimalTree(leftArray)

# Right side recursion
root.right = minimalTree(rightArray)

Вам необходимо вернуть root

return root

код минимального дерева после рефакторинга выше 

def minimalTree(sortedArray):
    lengthArray = len(sortedArray)

    # Base case of recursion
    if lengthArray == 0:
      return None

    # Assign middle
    middle = lengthArray//2
    root = Node(sortedArray[middle])

    # Split Left & Right sides
    leftArray = sortedArray[0:middle]
    rightArray = sortedArray[middle+1:lengthArray]

    # Left & right recursions
    root.left = minimalTree(leftArray)
    root.right = minimalTree(rightArray)

    return root

Дерево отображения 

def display(node): 
    if not node: 
        return

    print (node.value)
    display(node.left)
    display(node.right)

Тест 

tree = minimalTree([1, 2, 3, 4, 5])
display(tree)

Выход 

3
2
1
5
4
...