Dado un árbol de búsqueda binario , la tarea es crear una array de ondas a partir del árbol de búsqueda binario dado. Una array arr[0..n-1] se denomina array de ondas si arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …
Ejemplos:
Aporte:
Salida: 4 2 8 6 12 10 14
Explicación: La array mencionada anteriormente {4, 2, 8, 6, 12, 10, 14} es una de las muchas arrays de ondas válidas.Aporte:
Salida: 4 2 8 6 12
Enfoque: el problema dado se puede resolver mediante la observación de que el recorrido en orden del árbol de búsqueda binaria da Nodes en orden no decreciente. Por lo tanto, almacene el recorrido en orden del árbol dado en un vector . Dado que el vector contiene elementos ordenados, se puede convertir en una array de ondas intercambiando los elementos adyacentes por todos los elementos en el rango [0, N) utilizando el enfoque que se describe en este artículo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Node of the Binary Search tree
struct Node {
int data;
Node* right;
Node* left;
// Constructor
Node(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Function to convert Binary Search
// Tree into a wave Array
void toWaveArray(Node* root)
{
// Stores the final wave array
vector<int> waveArr;
stack<Node*> s;
Node* curr = root;
// Perform the Inorder traversal
// of the given BST
while (curr != NULL || s.empty() == false) {
// Reach the left most Node of
// the curr Node
while (curr != NULL) {
// Place pointer to a tree node
// in stack before traversing
// the node's left subtree
s.push(curr);
curr = curr->left;
}
curr = s.top();
s.pop();
// Insert into wave array
waveArr.push_back(curr->data);
// Visit the right subtree
curr = curr->right;
}
// Convert sorted array into wave array
for (int i = 0;
i + 1 < waveArr.size(); i += 2) {
swap(waveArr[i], waveArr[i + 1]);
}
// Print the answer
for (int i = 0; i < waveArr.size(); i++) {
cout << waveArr[i] << " ";
}
}
// Driver Code
int main()
{
Node* root = new Node(8);
root->left = new Node(4);
root->right = new Node(12);
root->right->left = new Node(10);
root->right->right = new Node(14);
root->left->left = new Node(2);
root->left->right = new Node(6);
toWaveArray(root);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Node of the Binary Search tree
static class Node {
int data;
Node right;
Node left;
// Constructor
Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
// Function to convert Binary Search
// Tree into a wave Array
static void toWaveArray(Node root)
{
// Stores the final wave array
Vector<Integer> waveArr = new Vector<>();
Stack<Node> s = new Stack<>();
Node curr = root;
// Perform the Inorder traversal
// of the given BST
while (curr != null || s.isEmpty() == false) {
// Reach the left most Node of
// the curr Node
while (curr != null) {
// Place pointer to a tree node
// in stack before traversing
// the node's left subtree
s.add(curr);
curr = curr.left;
}
curr = s.peek();
s.pop();
// Insert into wave array
waveArr.add(curr.data);
// Visit the right subtree
curr = curr.right;
}
// Convert sorted array into wave array
for (int i = 0; i + 1 < waveArr.size(); i += 2) {
int t = waveArr.get(i);
waveArr.set(i, waveArr.get(i+1));
waveArr.set(i+1, t);
}
// Print the answer
for (int i = 0; i < waveArr.size(); i++) {
System.out.print(waveArr.get(i)+ " ");
}
}
// Driver Code
public static void main(String[] args)
{
Node root = new Node(8);
root.left = new Node(4);
root.right = new Node(12);
root.right.left = new Node(10);
root.right.right = new Node(14);
root.left.left = new Node(2);
root.left.right = new Node(6);
toWaveArray(root);
}
}
// This code is contributed by umadevi9616
Python3
# Python program for the above approach # Node of the Binary Search tree class Node: def __init__(self, data): self.data = data; self.right = None; self.left = None; # Function to convert Binary Search # Tree into a wave Array def toWaveArray(root): # Stores the final wave array waveArr = []; s = []; curr = root; # Perform the Inorder traversal # of the given BST while (curr != None or len(s) != 0): # Reach the left most Node of # the curr Node while (curr != None): # Place pointer to a tree Node # in stack before traversing # the Node's left subtree s.append(curr); curr = curr.left; curr = s.pop(); # Insert into wave array waveArr.append(curr.data); # Visit the right subtree curr = curr.right; # Convert sorted array into wave array for i in range(0,len(waveArr)-1, 2): t = waveArr[i]; waveArr[i] = waveArr[i + 1]; waveArr[i + 1]= t; # Print the answer for i in range(len(waveArr)): print(waveArr[i], end=" "); # Driver Code if __name__ == '__main__': root = Node(8); root.left = Node(4); root.right = Node(12); root.right.left = Node(10); root.right.right = Node(14); root.left.left = Node(2); root.left.right = Node(6); toWaveArray(root); # This code is contributed by Rajput-Ji
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Node of the Binary Search tree
public class Node {
public int data;
public Node right;
public Node left;
// Constructor
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
// Function to convert Binary Search
// Tree into a wave Array
static void toWaveArray(Node root)
{
// Stores the readonly wave array
List<int> waveArr = new List<int>();
Stack<Node> s = new Stack<Node>();
Node curr = root;
// Perform the Inorder traversal
// of the given BST
while (curr != null || s.Count!=0 ) {
// Reach the left most Node of
// the curr Node
while (curr != null) {
// Place pointer to a tree node
// in stack before traversing
// the node's left subtree
s.Push(curr);
curr = curr.left;
}
curr = s.Peek();
s.Pop();
// Insert into wave array
waveArr.Add(curr.data);
// Visit the right subtree
curr = curr.right;
}
// Convert sorted array into wave array
for (int i = 0; i + 1 < waveArr.Count; i += 2) {
int t = waveArr[i];
waveArr[i]= waveArr[i+1];
waveArr[i+1]= t;
}
// Print the answer
for (int i = 0; i < waveArr.Count; i++) {
Console.Write(waveArr[i]+ " ");
}
}
// Driver Code
public static void Main(String[] args)
{
Node root = new Node(8);
root.left = new Node(4);
root.right = new Node(12);
root.right.left = new Node(10);
root.right.right = new Node(14);
root.left.left = new Node(2);
root.left.right = new Node(6);
toWaveArray(root);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// JavaScript Program to implement
// the above approach
class Node {
constructor(data) {
this.data = data;
this.left = this.right = null;
}
}
// Function to convert Binary Search
// Tree into a wave Array
function toWaveArray(root) {
// Stores the final wave array
let waveArr = [];
let s = [];
let curr = root;
// Perform the Inorder traversal
// of the given BST
while (curr != null || s.length != 0) {
// Reach the left most Node of
// the curr Node
while (curr != null) {
// Place pointer to a tree node
// in stack before traversing
// the node's left subtree
s.push(curr);
curr = curr.left;
}
curr = s[s.length - 1];
s.pop();
// Insert into wave array
waveArr.push(curr.data);
// Visit the right subtree
curr = curr.right;
}
// Convert sorted array into wave array
for (let i = 0;
i + 1 < waveArr.length; i += 2) {
let temp = waveArr[i]
waveArr[i] = waveArr[i + 1]
waveArr[i + 1] = temp
}
// Print the answer
for (let i = 0; i < waveArr.length; i++) {
document.write(waveArr[i] + " ");
}
}
// Driver Code
let root = new Node(8);
root.left = new Node(4);
root.right = new Node(12);
root.right.left = new Node(10);
root.right.right = new Node(14);
root.left.left = new Node(2);
root.left.right = new Node(6);
toWaveArray(root);
// This code is contributed by Potta Lokesh
</script>
Producción:
4 2 8 6 12 10 14
Complejidad temporal: O(N)
Espacio auxiliar: O(N)