Cómo crear un árbol binario

Question

No me refería al árbol de búsqueda binaria.

por ejemplo, si inserto los valores 1,2,3,4,5 en un árbol de búsqueda binaria, el recorrido del inorder dará 1,2,3,4,5 como salida.

pero si inserto los mismos valores en un árbol binario, el recorrido del inorder debe dar 4,2,5,1,3 como salida.

El árbol binario se puede crear usando matrices dinámicas en las que para cada elemento en el índice n, 2n + 1 y 2n + 2 representan sus hijos izquierdo y derecho respectivamente.

por lo que la representación y el recorrido de la orden de nivel es muy fácil aquí.

pero creo que, en orden, después de la orden, preordenar es difícil.

mi pregunta es cómo podemos crear un árbol binario como un árbol de búsqueda binario. es decir. tienen una clase de árbol que contiene datos, punteros izquierdo y derecho en lugar de matrices. para que podamos hacer un recorrido recursivo.

Answer 1

La parte de declaración de clase de árbol es, sin duda, la dificultad aquí. Es, básicamente, declaró exactamente cómo declarar que, en la pregunta:

class BinaryTree 
{ 
private: 
    int data; 
    BinaryTree *left, *right; 
}; 

Esto apoya diversas formas de recorrido, así:

void Inorder(const BinaryTree *root) 
{ 
    if(root == 0) 
    return; 
    Inorder(root->left); 
    printf("now at %d\n", root->data); 
    Inorder(root->right); 
} 

Usted debe ser capaz de deducir recorridos de orden pre y post a partir de ese. En una implementación real, el árbol probablemente tendría la función de almacenar datos aleatorios, las rutinas transversales serían más generales (con una entrada de datos de usuario, o quizás una devolución de llamada por nodo proporcionada por el usuario, o lo que sea), por supuesto.

Answer 2

Como no he recibido ninguna respuesta a la pregunta que hice, publicaré mi propia implementación del árbol binario usando matrices. ahora sé que la implementación de la matriz es más fácil de lo que pensaba, pero aún así no sé cómo implementar la misma utilizando listas vinculadas.

el código está en C#

class BinaryTree 
    { 
     private static int MAX_ELEM = 100;  //initial size of the array 
     int lastElementIndex; 
     int?[] dataArray; 

     public BinaryTree() 
     { 
      dataArray = new int?[MAX_ELEM]; 
      lastElementIndex = -1; 
     } 

     //function to insert data in to the tree 
     //insert as a complete binary tree 
     public void insertData(int data) 
     { 
      int?[] temp; 
      if (lastElementIndex + 1 < MAX_ELEM) 
      { 
       dataArray[++lastElementIndex] = data; 
      } 
      else 
      { //double the size of the array on reaching the limit 
       temp = new int?[MAX_ELEM * 2]; 
       for (int i = 0; i < MAX_ELEM; i++) 
       { 
        temp[i] = dataArray[i]; 
       } 
       MAX_ELEM *= 2; 
       dataArray = temp; 
       dataArray[++lastElementIndex] = data; 
      } 
     } 

     //internal function used to get the left child of an element in the array 
     int getLeftChild(int index) { 
      if(lastElementIndex >= (2*index+1)) 
       return (2*index + 1); 
      return -1; 
     } 

     //internal function used to get the right child of an element in the array 
     int getRightChild(int index) { 
      if(lastElementIndex >= (2*index+2)) 
       return (2*index + 2); 
      return -1; 
     } 
     //function to check if the tree is empty 
     public bool isTreeEmpty() { 
      if (lastElementIndex == -1) 
       return true; 
      return false; 
     } 

     //recursive function for inorder traversal 
     public void traverseInOrder(int index) { 
      if (index == -1) 
       return; 
      traverseInOrder(getLeftChild(index)); 
      Console.Write("{0} ", dataArray[index]); 
      traverseInOrder(getRightChild(index)); 
     } 

     //recursive function for preorder traversal 
     public void traversePreOrder(int index) { 
      if (index == -1) 
       return; 
      Console.Write("{0} ", dataArray[index]); 
      traversePreOrder(getLeftChild(index)); 
      traversePreOrder(getRightChild(index)); 
     } 

     //recursive function for postorder traversal 
     public void traversePostOrder(int index) { 
      if (index == -1) 
       return; 
      traversePostOrder(getLeftChild(index)); 
      traversePostOrder(getRightChild(index)); 
      Console.Write("{0} ", dataArray[index]); 
     } 

     //function to traverse the tree in level order 
     public void traverseLevelOrder() 
     { 
      Console.WriteLine("\nPrinting Elements Of The Tree In Ascending Level Order\n"); 
      if (lastElementIndex == -1) 
      { 
       Console.WriteLine("Empty Tree!...press any key to return"); 
       Console.ReadKey(); 
       return; 
      } 
      for (int i = 0; i <= lastElementIndex; i++) 
      { 
       Console.Write("{0} ", dataArray[i]); 
      } 
      Console.WriteLine("\n"); 
     } 


    } 

Answer 3

Si he entendido bien, que desea crear un árbol binario de una matriz

int[] values = new int[] {1, 2, 3, 4, 5}; 
BinaryTree tree = new BinaryTree(values); 

esto debe rellenar previamente el árbol binario con los valores 1 - 5 como sigue:

1 
/\ 
    2 3 
/\ 
4 5 

esto se puede hacer utilizando la siguiente clase:

class BinaryTree 
{ 
    int value; 
    BinaryTree left; 
    BinaryTree right; 

    public BinaryTree(int[] values) : this(values, 0) {} 

    BinaryTree(int[] values, int index) 
    { 
     Load(this, values, index); 
    } 

    void Load(BinaryTree tree, int[] values, int index) 
    { 
     this.value = values[index]; 
     if (index * 2 + 1 < values.Length) 
     { 
      this.left = new BinaryTree(values, index * 2 + 1); 
     } 
     if (index * 2 + 2 < values.Length) 
     { 
      this.right = new BinaryTree(values, index * 2 + 2); 
     } 
    } 
} 

Answer 4

Si buscas la fuente para una implementación completa de BinaryTree, puedes aprender de echar un vistazo a The C5 Generic Collection Library.