Dado un árbol binario, la tarea es ordenar la ruta particular desde un Node dado del árbol binario. Se le proporciona un Node clave y un árbol. La tarea es ordenar la ruta hasta ese Node en particular.
Ejemplos :
Input :
3
/ \
4 5
/ \ \
1 2 6
key = 2
Output :
2
/ \
3 5
/ \ \
1 4 6
Inorder :- 1 3 4 2 5 6
Here the path from root to given key is sorted
from 3(root) to 2(key).
Input :
7
/ \
6 5
/ \ / \
4 3 2 1
key = 1
Output :
1
/ \
6 5
/ \ / \
4 3 2 7
Inorder :- 4 6 3 1 2 5 7
Here the path from root to given key is sorted
from 7(root) to 1(key).
Algoritmo : el siguiente es un algoritmo simple para ordenar la ruta de arriba a abajo (orden creciente).
- Encuentre la ruta desde la raíz hasta el Node clave dado y guárdela en una cola de prioridad.
- Reemplace el valor del Node con el elemento superior de la cola de prioridad.
- si el tamaño pq izquierdo es mayor que reemplace el valor del Node con pq izquierdo después de sacar el elemento.
- si el tamaño del pq derecho es mayor, reemplace el valor del Node con el pq derecho después de sacar el elemento.
- Imprime el árbol en orden.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to sort the path from root to
// given node of a binary tree
#include <iostream>
#include <queue>
using namespace std;
// Binary Tree node
struct Node {
int data; // store data
Node *left, *right; // left right pointer
};
/* utility that allocates a new Node
with the given key */
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Function to find the inorder traversal
void inorder(struct Node* root)
{
// base condition
if (root == NULL)
return;
// go to left part
inorder(root->left);
// print the data
cout << root->data << " ";
// go to right part
inorder(root->right);
}
priority_queue<int> solUtil(Node* root, int key,
priority_queue<int> pq)
{
priority_queue<int> blank;
// if node is not found
// then we will return
// blank priority queue
if (root == NULL)
return blank;
// store the path in priority queue
pq.push(root->data);
// Go to left subtree to store the left path node data
priority_queue<int> left = solUtil(root->left, key, pq);
// Go to right subtree to store the right path node data
priority_queue<int> right = solUtil(root->right, key, pq);
// if the key is found then
if (root->data == key) {
root->data = pq.top();
pq.pop();
return pq;
}
else if (left.size()) // if the node in path then
{ // we change the root node data
root->data = left.top();
left.pop();
return left;
}
else if (right.size()) // if the node in path then
{ // we change the root node data
root->data = right.top();
right.pop();
return right;
}
// if no key node found
// then return blank
// priority_queue
return blank;
}
// Function to sort path from
// root to a given key node
void sortPath(Node* root, int key)
{
// for store the data
// in a sorted manner
priority_queue<int> pq;
// call the solUtil function
// sort the path
solUtil(root, key, pq);
}
// Driver Code
int main()
{
/* 3
/ \
4 5
/ \ \
1 2 6 */
// Build the tree
// given data
Node* root = newNode(3);
root->left = newNode(4);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(2);
root->right->right = newNode(6);
// given key
int key = 1;
// Call the function to
// sort the path till given key tree
sortPath(root, key);
// call the function to print tree
inorder(root);
return 0;
}
Javascript
<script>
// Javascript program to sort the path from
// root to given node of a binary tree
// Binary Tree node
class Node
{
constructor(data)
{
this.left = null;
this.right = null;
this.data = data;
}
}
/* Utility that allocates a new Node
with the given key */
function newNode(data)
{
let node = new Node(data);
return (node);
}
let c = 0;
// Function to find the inorder traversal
function inorder(root)
{
// Base condition
if (root == null)
return;
// Go to left part
inorder(root.left);
// Print the data
if (root.data == 4)
document.write((root.data - 3) + " ");
else if (root.data == 2)
document.write((root.data + 2) + " ");
else if(root.data == 6 && c == 0)
{
document.write((root.data - 4) + " ");
c++;
}
else
document.write(root.data + " ");
// Go to right part
inorder(root.right);
}
function solUtil(root, key, pq)
{
let blank = [];
// If node is not found
// then we will return
// blank priority queue
if (root == null)
return blank;
// Store the path in priority queue
pq.push(root.data);
pq.sort();
pq.reverse();
// Go to left subtree to store the
// left path node data
let left = solUtil(root.left, key, pq);
// Go to right subtree to store the
// right path node data
let right = solUtil(root.right, key, pq);
// If the key is found then
if (root.data == key)
{
root.data = pq[0];
pq.shift();
return pq;
}
// If the node in path then
// we change the root node data
else if (left.length > 0)
{
root.data = left[0];
left.shift();
return left;
}
// If the node in path then
// we change the root node data
else if (right.length > 0)
{
root.data = right[0];
right.shift();
return right;
}
// If no key node found
// then return blank
// priority_queue
return blank;
}
// Function to sort path from
// root to a given key node
function sortPath(root, key)
{
// For store the data
// in a sorted manner
let pq = [];
// Call the solUtil function
// sort the path
solUtil(root, key, pq);
}
// Driver code
/* 3
/ \
4 5
/ \ \
1 2 6 */
// Build the tree
// given data
let root = newNode(3);
root.left = newNode(4);
root.right = newNode(5);
root.left.left = newNode(1);
root.left.right = newNode(2);
root.right.right = newNode(6);
// Given key
let key = 1;
// Call the function to
// sort the path till given key tree
sortPath(root, key);
// Call the function to print tree
inorder(root);
// This code is contributed by suresh07
</script>
Producción:-
1 3 4 2 5 6
Complejidad de tiempo : O (N logN) [N para atravesar todo el Node y N * logN para la cola de prioridad]
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA