c++ - fuente - guardar un arbol binario en un archivo en java

Guardar un árbol binario en un archivo

Question

Tengo un árbol binario no balanceado (no de búsqueda binaria) Necesito incoordenarlo (y luego decodificarlo) en un archivo txt. ¿Cómo puedo hacerlo de manera eficiente?

Encontré este enlace que habla de un problema similar (el mismo), pero es obvio para mí

Answer 1

Por favor mira esto en LeetCode .

Me gusta esta solución porque es relativamente eficiente y produce archivos de salida ligera.

Suponiendo que tienes un árbol como este:

    _30_ 
   /    /    
  10    20
 /     /  / 
50    45  35

Esta solución le permite serializarlo en un archivo de texto de salida:

30 10 50 # # # 20 45 # # 35 # #

Para hacer esto es suficiente realizar un recorrido de pre-pedido simple a través del árbol:

void writeBinaryTree(BinaryTree *p, ostream &out) {
  if (!p) {
    out << "# ";
  } else {
    out << p->data << " ";
    writeBinaryTree(p->left, out);
    writeBinaryTree(p->right, out);
  }
}

Como puede ver, un símbolo # se usa para representar el nodo nulo.

Para deserializar esta cadena en un árbol puede usar:

void readBinaryTree(BinaryTree *&p, ifstream &fin) {
  int token;
  bool isNumber;
  if (!readNextToken(token, fin, isNumber)) 
    return;
  if (isNumber) {
    p = new BinaryTree(token);
    readBinaryTree(p->left, fin);
    readBinaryTree(p->right, fin);
  }
}

Como dije antes, este método produce una representación ligera del árbol binario.

Por supuesto, tiene un serio inconveniente: requiere un símbolo para representar el nodo nulo.

Puede causar problemas potenciales si los nodos del árbol son cadenas que pueden contener este símbolo.