Cree una array de ondas a partir del árbol de búsqueda binaria dado

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)

Publicación traducida automáticamente

Artículo escrito por vibhor11 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *