Как представить двоичное дерево в массив с помощью Python?

Question

Я хочу преобразовать двоичное дерево в массив, используя Python, и я не знаю, как дать индекс для дерева-узла?

Я сделал это по формуле left_son = (2 * р) + 1; и right_son = (2 * p) +2; в Java Но я застрял в питоне. Есть ли какая-либо функция, чтобы дать индекс дерева-узла в Python?

Answer 1

Вы можете представить двоичное дерево в python как одномерный список точно таким же образом.

Например, если у вас есть дерево, представленное как:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15]

0корень
1 & 2 следующий уровень
дочерние элементы 1 & 2 [3, 4] и [5, 6]

Это соответствует вашей формуле.Для данного узла с индексом i дочерние элементы этого узла (2*i)+1 (2*i)+2.Это распространенный способ моделирования кучи.Вы можете прочитать больше о том, как Python использует это в своей [библиотеке heapq]. (https://docs.python.org/3.0/library/heapq.html)

Вы можете использовать это для обхода дерева на глубине с чем-то вроде:

a =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15]

def childNodes(i):
     return (2*i)+1, (2*i)+2

def traversed(a, i=0, d = 0):
    if i >= len(a):
        return 
    l, r =  childNodes(i)
    traversed(a, r, d = d+1)
    print("   "*d + str(a[i]))
    traversed(a, l, d = d+1)

traversed(a)

This Prints

         15
      6
         14
   2
         13
      5
         11
0
         10
      4
         9
   1
         8
      3
         7

Answer 2

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

class Node: 

    # A utility function to create a new node 
    def __init__(self, key): 
        self.data = key  
        self.left = None
        self.right = None


# Function to  print level order traversal of tree 
def printLevelOrder(root): 
    h = height(root) 
    for i in range(1, h+1): 
        printGivenLevel(root, i) 


# Print nodes at a given level 
def printGivenLevel(root , level): 
    if root is None: 
        return
    if level == 1: 
        print "%d" %(root.data), 
    elif level > 1 : 
        printGivenLevel(root.left , level-1) 
        printGivenLevel(root.right , level-1) 


""" Compute the height of a tree--the number of nodes 
    along the longest path from the root node down to 
    the farthest leaf node 
"""
def height(node): 
    if node is None: 
        return 0 
    else : 
        # Compute the height of each subtree  
        lheight = height(node.left) 
        rheight = height(node.right) 

        #Use the larger one 
        if lheight > rheight : 
            return lheight+1
        else: 
            return rheight+1

# Driver program to test above function 
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 

print "Level order traversal of binary tree is -"
printLevelOrder(root)