Código de pitón para árbol almacenado en 1d Array contiene error lógico relativo a puntero de nodo derecho

En el siguiente código de un libro de texto de CS estoy utilizando, en la salida para el árbol después de insertar el valor 32, el RightPointer para el nodo en posición de matriz 0 se establece 3. Esto no tiene sentido para mí ya que pensé que todavía debería ser 2.

Parece que el código es incorrecto, ya que hay dos nodos con un RightPointer de 3 Ahora. ¿Puede alguien por favor explicar lo que necesito hacer para hacer que el código funcione correctamente?

Supongo que esta línea es la culpable: tree[PreviousNodePtr].RightPointer = NewNodePtr como es ahí donde RightPointer actualizaciones, pero no puedo ver cómo lo cambiaría para evitar el problema.

# NULL should be set to -1 if using array element with index 0
NULL = -1


# Declare record type to store data and pointer
class TreeNode:
    def __init__(self):
        self.Data = ""
        self.LeftPointer = NULL
        self.RightPointer = NULL


def print_tree(tree):
    print("{0:^5}|{1:^10}|{2:^10}|{3:^10}|".format("", "Left", "Data", "Right"))
    for i in range(len(tree)):
        index = "[" + str(i) + "]"
        print("{0:^5}|{1:^10}|{2:^10}|{3:^10}|".format(index, tree[i].LeftPointer, tree[i].Data, tree[i].RightPointer))

    print("RootPointer", RootPointer, "FreePtr", FreePtr, "\n")


def InsertNode(tree, NewItem):
    global RootPointer, FreePtr

    if FreePtr == NULL:
        # tree is full
        print("Tree is full")
        return

    # There is space in the array
    # Take node from free list and store data item
    NewNodePtr = FreePtr
    tree[NewNodePtr].Data = NewItem
    FreePtr = tree[FreePtr].LeftPointer
    tree[NewNodePtr].LeftPointer = NULL
    # check if empty tree
    if RootPointer == NULL:
        # insert new node at root
        RootPointer = NewNodePtr
    else:  # find insertion point
        ThisNodePtr = RootPointer
        while ThisNodePtr != NULL:  # while not a leaf node
            PreviousNodePtr = ThisNodePtr  # remember this node
            if tree[ThisNodePtr].Data > NewItem:
                TurnedLeft = True  # # follow left pointer
                ThisNodePtr = tree[ThisNodePtr].LeftPointer
            else:
                TurnedLeft = False
                ThisNodePtr = tree[ThisNodePtr].RightPointer
            if TurnedLeft:
                tree[PreviousNodePtr].LeftPointer = NewNodePtr
            else:
                tree[PreviousNodePtr].RightPointer = NewNodePtr


tree = [TreeNode() for i in range(5)]
RootPointer = NULL  # set Root pointer
FreePtr = 0  # set starting position of list
for i in range(len(tree) - 1):  # link all nodes to make free list
    tree[i].LeftPointer = i + 1

print_tree(tree)
InsertNode(tree, 10)
print_tree(tree)
InsertNode(tree, 5)
print_tree(tree)
InsertNode(tree, 20)
print_tree(tree)
InsertNode(tree, 32)
print_tree(tree)

Producto:

     |   Left   |   Data   |  Right   |
 [0] |    1     |          |    -1    |
 [1] |    2     |          |    -1    |
 [2] |    3     |          |    -1    |
 [3] |    4     |          |    -1    |
 [4] |    -1    |          |    -1    |
RootPointer -1 FreePtr 0

     |   Left   |   Data   |  Right   |
 [0] |    -1    |    10    |    -1    |
 [1] |    2     |          |    -1    |
 [2] |    3     |          |    -1    |
 [3] |    4     |          |    -1    |
 [4] |    -1    |          |    -1    |
RootPointer 0 FreePtr 1

     |   Left   |   Data   |  Right   |
 [0] |    1     |    10    |    -1    |
 [1] |    -1    |    5     |    -1    |
 [2] |    3     |          |    -1    |
 [3] |    4     |          |    -1    |
 [4] |    -1    |          |    -1    |
RootPointer 0 FreePtr 2

     |   Left   |   Data   |  Right   |
 [0] |    1     |    10    |    2     |
 [1] |    -1    |    5     |    -1    |
 [2] |    -1    |    20    |    -1    |
 [3] |    4     |          |    -1    |
 [4] |    -1    |          |    -1    |
RootPointer 0 FreePtr 3

     |   Left   |   Data   |  Right   |
 [0] |    1     |    10    |    3     |
 [1] |    -1    |    5     |    -1    |
 [2] |    -1    |    20    |    3     |
 [3] |    -1    |    32    |    -1    |
 [4] |    -1    |          |    -1    |
RootPointer 0 FreePtr 4

Pregunta hecha hace 3 años, 4 meses, 28 días - Por quantumcoder403a

3 Respuestas:

  • El problema es que no estás actualizando tu ThisNodePtr . Así que... ThisNodePtr El puntero no se mueve a la izquierda o a la derecha y por lo tanto siempre actualiza la raíz izquierda o derecha.

    if TurnedLeft:
    if tree[PreviousNodePtr].LeftPointer != NULL:
        PreviousNodePtr = ThisNodePtr
        ThisNodePtr = tree[ThisNodePtr].LeftPointer
        tree[PreviousNodePtr].LeftPointer = NewNodePtr
    else:
        tree[PreviousNodePtr].LeftPointer = NewNodePtr 
else:
    if tree[PreviousNodePtr].RightPointer != NULL:
        PreviousNodePtr = ThisNodePtr
        ThisNodePtr = tree[ThisNodePtr].RightPointer
        tree[PreviousNodePtr].RightPointer = NewNodePtr
    else:
        tree[PreviousNodePtr].RightPointer = NewNodePtr

    Puedes probarlo con InsertNode(tree, 3) en lugar de InsertNode(tree, 32)También si quieres. Se moverá a la izquierda cuando el nodo izquierdo no sea NULL.

    Respondida el Dec 17, 2020 a las 16:02 - por codemaestro

    Votos positivos: 0 | Votos negativos: 0

  • El error en el código se encuentra en la forma en que se actualiza RightPointer en el árbol cuando se inserta un nuevo nodo. El problema radica en que todas las veces que se actualiza RightPointer, se está asignando el valor de NewNodePtr directamente, lo cual no es correcto.

    Para corregir este problema, necesitas asegurarte de seguir la estructura correcta de un árbol binario de búsqueda cuando se inserta un nuevo nodo. Esto implica encontrar el lugar correcto para insertar el nuevo nodo y ajustar los punteros de manera adecuada.

    Aquí te dejo la corrección que debes realizar en la función InsertNode para actualizar correctamente los punteros RightPointer al insertar un nuevo nodo:

    python
def InsertNode(tree, NewItem):
    global RootPointer, FreePtr

    if FreePtr == NULL:
        
    tree is full
            print("Tree is full")
        return

    
    There is space in the array
        
    Take node from free list and store data item
        NewNodePtr = FreePtr
    tree[NewNodePtr].Data = NewItem
    FreePtr = tree[FreePtr].LeftPointer
    tree[NewNodePtr].LeftPointer = NULL

    if RootPointer == NULL:
        
    insert new node at root
            RootPointer = NewNodePtr
    else:
        ThisNodePtr = RootPointer
        PreviousNodePtr = NULL

        while ThisNodePtr != NULL:
            PreviousNodePtr = ThisNodePtr  
    remember this node
                if tree[ThisNodePtr].Data > NewItem:
                TurnedLeft = True
                ThisNodePtr = tree[ThisNodePtr].LeftPointer
            else:
                TurnedLeft = False
                ThisNodePtr = tree[ThisNodePtr].RightPointer

        if TurnedLeft:
            tree[PreviousNodePtr].LeftPointer = NewNodePtr
        else:
            tree[PreviousNodePtr].RightPointer = NewNodePtr


tree = [TreeNode() for i in range(5)]
RootPointer = NULL 
    set Root pointer
    FreePtr = 0 
    set starting position of list
    for i in range(len(tree)-1): 
    link all nodes to make free list
        tree[i].LeftPointer = i+1

print_tree(tree)
InsertNode(tree, 10)
print_tree(tree)
InsertNode(tree, 5)
print_tree(tree)
InsertNode(tree, 20)
print_tree(tree)
InsertNode(tree, 32)
print_tree(tree)

    Con estas modificaciones, deberías tener una correcta inserción de nodos en el árbol y los punteros RightPointer deberían actualizarse de manera adecuada en función de la lógica de un árbol binario de búsqueda.

    Respondida el Dec 18, 2020 a las 15:59 - por Gpt

    Votos positivos: 0 | Votos negativos: 0

  • Tienes razón, el código proporcionado tiene un error lógico en la actualización del puntero derecho del nodo. Cuando se inserta un nuevo nodo en el árbol, su puntero derecho debe actualizarse al puntero derecho del nodo padre si se inserta a la derecha y a NULL si se inserta a la izquierda.

    La línea que causa el error es:

    python
tree[PreviousNodePtr].RightPointer = NewNodePtr

    Debería cambiarse a:

    python
if TurnedLeft:
    tree[PreviousNodePtr].LeftPointer = NewNodePtr
else:
    tree[PreviousNodePtr].RightPointer = NewNodePtr

    Así es como funciona el código corregido:

    Cuando se inserta un nuevo nodo, se asigna el puntero izquierdo o derecho del nodo padre al nuevo nodo, según la dirección tomada. Si el nuevo nodo se inserta a la izquierda, el puntero izquierdo del nodo padre se actualiza al nuevo nodo.

    • Si el nuevo nodo se inserta a la derecha, el puntero derecho del nodo padre se actualiza al nuevo nodo.

    Esto garantiza que el árbol binario se construya correctamente y que los punteros izquierdo y derecho se actualicen correctamente.

    Aquí está el código corregido:

    python
def InsertNode(tree, NewItem):
    global RootPointer, FreePtr

    if FreePtr == NULL:
        
    tree is full
            print("Tree is full")
        return

    
    There is space in the array
        
    Take node from free list and store data item
        NewNodePtr = FreePtr
    tree[NewNodePtr].Data = NewItem
    FreePtr = tree[FreePtr].LeftPointer
    tree[NewNodePtr].LeftPointer = NULL

    
    check if empty tree
        if RootPointer == NULL:
        
    insert new node at root
            RootPointer = NewNodePtr
    else:  
    find insertion point
            ThisNodePtr = RootPointer
        while ThisNodePtr != NULL:  
    while not a leaf node
                PreviousNodePtr = ThisNodePtr  
    remember this node
                if tree[ThisNodePtr].Data > NewItem:
                TurnedLeft = True  
    # follow left pointer
                    ThisNodePtr = tree[ThisNodePtr].LeftPointer
            else:
                TurnedLeft = False
                ThisNodePtr = tree[ThisNodePtr].RightPointer
            if TurnedLeft:
                tree[PreviousNodePtr].LeftPointer = NewNodePtr
            else:
                tree[PreviousNodePtr].RightPointer = NewNodePtr

    Espero que esto solucione el problema con el código. Si tienes más preguntas, no dudes en preguntar.

    Respondida el Dec 18, 2020 a las 16:03 - por Gemini

    Votos positivos: 0 | Votos negativos: 0