algorithm - operaciones - Para imprimir el límite del árbol binario

clasificacion de arboles estructura de datos

Question

En una entrevista me pidieron que imprimiera el límite del Árbol Binario. Por ejemplo.

 1
/ /
2 3
/ / / /
4 5 6 7
/ / /
8 9 10

La respuesta será: 1, 2, 4, 8, 9, 10, 7, 3

He dado la siguiente respuesta.

Primer método:

He usado una variable Bool para resolver el problema anterior.

void printLeftEdges(BinaryTree *p, bool print) {
if (!p) return;
if (print || (!p->left && !p->right))
cout << p->data << " ";
printLeftEdges(p->left, print);
printLeftEdges(p->right, false);
}
void printRightEdges(BinaryTree *p, bool print) {
if (!p) return;
printRightEdges(p->left, false);
printRightEdges(p->right, print);
if (print || (!p->left && !p->right))
cout << p->data << " ";
}
void printOuterEdges(BinaryTree *root) {
if (!root) return;
cout << root->data << " ";
printLeftEdges(root->left, true);
printRightEdges(root->right, true);
}

Su respuesta: has usado la variable Bool tantas veces. ¿Puedes resolver esto sin usar eso?

Segundo método:

Simplemente usé el cruce de árboles para resolver este problema.

1. Print the left boundary in top-down manner.
2. Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts:
2.1 Print all leaf nodes of left sub-tree from left to right.
2.2 Print all leaf nodes of right subtree from left to right.
3. Print the right boundary in bottom-up manner.

Su respuesta: Él no estaba contento con este método también. Él dijo que estás atravesando el árbol 3 veces . Eso es demasiado. Dale otra solución si tienes alguna.

Tercer método: esta vez he ido para el cruce de orden de nivel (BFS) .

 1: Print starting and ending node of each level
2: For each other node check if its both the children are <b>NULL</b> then print that node too.

Su respuesta: Él no parecía feliz con este método también porque este método toma memoria extra de la orden O (n).

Mi pregunta es que dígame un método que recorra el árbol una sola vez, no use ninguna variable Bool y no use ninguna memoria extra. ¿Es posible?

Answer 1

Método O(n) No extra space and single traversal of tree.

Dividí los nodos de árbol en cuatro tipos de nodos

Escriba 1 -> Nodos que forman el límite izquierdo (p. Ej. 8)

Escriba 0 -> Nodos que no forman el límite (por ejemplo, 12)

Tipo 3 -> Nodos que forman el límite derecho (por ejemplo, 22)

Nodos de la hoja (p. Ej. 4,10,14)

En mi método, estoy haciendo un método de recurrencia de cruce de árbol (solo modificado) donde mi función es de esta forma

 void recFunc(btNode *temp,int type)
{
//Leaf Nodes
if((temp->left == NULL)&&(temp->right == NULL))
cout << temp->data << " ";
// type -1 Nodes must be printed before their children
else if(type == 1)cout << temp->data << " ";
else {;}
if(type == 3)
{
if(temp->left)recFunc(temp->left,0);
if(temp->right)recFunc(temp->right,3);
//type 3 nodes must be printed after their children
cout << temp->data << " ";
}
else if(type == 1)
{
if(temp->left)recFunc(temp->left,1);
if(temp->right)recFunc(temp->right,0);
}
else if(type == 0)
{
if(temp->left)recFunc(temp->left,0);
if(temp->right)recFunc(temp->right,0);
}
else {;}
}

donde he modificado el

1. En mi función recurrente, los nodos de tipo 1 deben hacer que sus nodos izquierdos sean del tipo 1 y deben imprimirse antes de llamar a sus hijos (si existen)
2. Los nodos de tipo 3 se deben imprimir en orden inverso. Por lo tanto, se deben imprimir después de llamar a sus hijos. También deben asignar a sus hijos correctos como nodos de tipo 3.
3. Los nodos de tipo 0 no se deben imprimir y asignan sus hijos como tipo 0 Nodos
4. Los nodos de hoja se deben imprimir directamente solo y devolver

Enlace al código

Answer 2

Creo que esto debería hacer el truco:

traverse(BinaryTree *root)
{
if (!root) return;
cout << p->data << " ";
if (root->left ) traverseL(root->left ); //special function for outer left
if (root->right) traverseR(root->right); //special function for outer right
}
traverseL(BinaryTree *p)
{
cout << p->data << " ";
if (root->left ) traverseL(root->left ); //still in outer left
if (root->right) traverseC(root->right);
}
traverseR(BinaryTree *p)
{
if (root->left ) traverseC(root->left );
if (root->right) traverseR(root->right); //still in outer right
cout << p->data << " ";
}
traverseC(BinaryTree *p)
{
if (!root->left && !root->right) //bottom reached
cout << p->data << " ";
else
{
if (root->left ) traverseC(root->left );
if (root->right) traverseC(root->right);
}
}

Comience con la función traverse . Se deshizo de las consultas nulas al comienzo de cada método (evita una llamada de función en cada extremo). No necesita variables de bool, simplemente usa tres métodos de cruce diferentes:

• uno para el borde izquierdo, dando salida al nodo antes del recorrido
• uno para el borde derecho, dando salida al nodo después del recorrido
• uno para todos los otros nodos, sacando el nodo si no hay hermanos.

Answer 3

A continuación hay una solución recursiva en Python3 con complejidad de tiempo O (n). Aquí el algoritmo es imprimir los nodos de la izquierda de arriba a abajo, los nodos de las hojas de izquierda a derecha y los nodos de la derecha de abajo hacia arriba. La adición de indicadores booleanos (isLeft,isRight) para el (isLeft,isRight) de árbol izquierdo y derecho simplifica el código e impulsa la complejidad de tiempo de O (n).

#Print tree boundary nodes
def TreeBoundry(node,isLeft,isRight):
#Left most node and leaf nodes
if(isLeft or isLeaf(node)): print(node.data,end='' '')
#Process next left node
if(node.getLeft() is not None): TreeBoundry(node.getLeft(), True,False)
#Process next right node
if(node.getRight() is not None):TreeBoundry(node.getRight(), False,True)
#Right most node
if(isRight and not isLeft and not isLeaf(node)):print(node.data,end='' '')
#Check is a node is leaf
def isLeaf(node):
if (node.getLeft() is None and node.getRight() is None):
return True
else:
return False
#Get started
#https://github.com/harishvc/challenges/blob/master/binary-tree-edge-nodes.py
TreeBoundry(root,True,True)