Dado un árbol binario, necesitamos escribir un programa para intercambiar Nodes de hoja en el árbol binario dado por pares, comenzando de izquierda a derecha, como se muestra a continuación.
Árbol antes de intercambiar:
Árbol después del intercambio:
La secuencia de Nodes hoja en el árbol binario original de izquierda a derecha es (4, 6, 7, 9, 10). Ahora, si tratamos de formar pares a partir de esta secuencia, tendremos dos pares como (4, 6), (7, 9). El último Node (10) no puede formar pareja con ningún Node y, por lo tanto, no se intercambia.
La idea para resolver este problema es primero atravesar los Nodes hoja del árbol binario de izquierda a derecha. Mientras recorremos los Nodes de hoja, mantenemos dos punteros para realizar un seguimiento del primer y segundo Node de hoja en un par y un conteo variable para realizar un seguimiento del conteo de Nodes de hoja atravesados. Ahora, si observamos detenidamente, vemos que al atravesar si el recuento de Nodes de hoja atravesados es par, significa que podemos formar un par de Nodes de hoja. Para realizar un seguimiento de este par, tomamos dos punteros firstPtr y secondPtr como se mencionó anteriormente. Cada vez que encontramos un Node hoja, inicializamos secondPtr con este Node hoja. Ahora, si el conteo es impar, inicializamos firstPtrcon secondPtr de lo contrario, simplemente intercambiamos estos dos Nodes.
A continuación se muestra la implementación en C++ de la idea anterior:
CPP
/* C++ program to pairwise swap
leaf nodes from left to right */
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
};
// function to swap two Node
void Swap(Node **a, Node **b)
{
Node * temp = *a;
*a = *b;
*b = temp;
}
// two pointers to keep track of
// first and second nodes in a pair
Node **firstPtr;
Node **secondPtr;
// function to pairwise swap leaf
// nodes from left to right
void pairwiseSwap(Node **root, int &count)
{
// if node is null, return
if (!(*root))
return;
// if node is leaf node, increment count
if(!(*root)->left&&!(*root)->right)
{
// initialize second pointer
// by current node
secondPtr = root;
// increment count
count++;
// if count is even, swap first
// and second pointers
if (count%2 == 0)
Swap(firstPtr, secondPtr);
else
// if count is odd, initialize
// first pointer by second pointer
firstPtr = secondPtr;
}
// if left child exists, check for leaf
// recursively
if ((*root)->left)
pairwiseSwap(&(*root)->left, count);
// if right child exists, check for leaf
// recursively
if ((*root)->right)
pairwiseSwap(&(*root)->right, count);
}
// Utility function to create a new tree node
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// function to print inorder traversal
// of binary tree
void printInorder(Node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%d ", node->data);
/* now recur on right child */
printInorder(node->right);
}
// Driver program to test above functions
int main()
{
// Let us create binary tree shown in
// above diagram
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(5);
root->right->right = newNode(8);
root->right->left->left = newNode(6);
root->right->left->right = newNode(7);
root->right->right->left = newNode(9);
root->right->right->right = newNode(10);
// print inorder traversal before swapping
cout << "Inorder traversal before swap:\n";
printInorder(root);
cout << "\n";
// variable to keep track
// of leafs traversed
int c = 0;
// Pairwise swap of leaf nodes
pairwiseSwap(&root, c);
// print inorder traversal after swapping
cout << "Inorder traversal after swap:\n";
printInorder(root);
cout << "\n";
return 0;
}
Inorder traversal before swap: 4 2 1 6 5 7 3 9 8 10 Inorder traversal after swap: 6 2 1 4 5 9 3 7 8 10
Complejidad de tiempo: O( n ) , donde n es el número de Nodes en el árbol binario.
Espacio Auxiliar: O( 1 )
Este artículo es una contribución de Harsh Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA