Encuentre la array mediana para el árbol binario

Requisito previo: Tree Traversals (Inorder, Preorder and Postorder) , Median
Dado un árbol binario que tiene Nodes integrales, la tarea es encontrar la mediana para cada posición en el recorrido del árbol en preorder, postorder y inorder.
 

La array mediana se da como la array formada con la ayuda de PreOrder, PostOrder e Inorder transversal de un árbol, tal que 
med[i] = mediana(preorder[i], inorder[i], postorder[i])

Ejemplos: 
 

Input: Tree =
               1
             /   \
            2     3
          /  \
         4    5 
Output: {4, 2, 4, 3, 3}
Explanation:
Preorder traversal = {1 2 4 5 3}
Inorder traversal =  {4 2 5 1 3}
Postorder traversal = {4 5 2 3 1}
median[0] = median(1, 4, 4) = 4
median[1] = median(2, 2, 5) = 2
median[2] = median(4, 5, 2) = 4
median[3] = median(5, 1, 3) = 3
median[4] = median(3, 3, 1) = 3
Hence, Median array = {4 2 4 3 3}

Input: Tree = 
               25
             /    \
           20      30
         /    \   /   \
       18     22 24   32 
Output: 18 20 20 24 30 30 32

Acercarse: 
 

  • Primero, encuentre el recorrido previo, posterior y en orden del árbol binario dado y almacénelos cada uno en un vector .
  • Ahora, para cada posición de 0 a N, inserte los valores en esa posición en cada una de las arrays transversales en un vector. El vector tendrá un tamaño de 3N.
  • Finalmente, ordene este vector y la mediana para esta posición viene dada por el segundo elemento . En este vector tiene 3N elementos. Por lo tanto, después de ordenar, la mediana estará dada por el elemento medio, el segundo elemento, en cada 3 elementos.

A continuación se muestra la implementación del enfoque anterior:
 

CPP

// C++ program to Obtain the median
// array for the preorder, postorder
// and inorder traversal of a binary tree
   
#include <bits/stdc++.h>
using namespace std;
   
// A binary tree node has data,
// a pointer to the left child
// and a pointer to the right child
struct Node {
    int data;
    struct Node *left, *right;
    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};
   
// Postorder traversal
void Postorder(
    struct Node* node,
    vector<int>& postorder)
{
    if (node == NULL)
        return;
   
    // First recur on left subtree
    Postorder(node->left, postorder);
   
    // then recur on right subtree
    Postorder(node->right, postorder);
   
    // now deal with the node
    postorder.push_back(node->data);
}
   
// Inorder traversal
void Inorder(
    struct Node* node,
    vector<int>& inorder)
{
    if (node == NULL)
        return;
   
    // First recur on left child
    Inorder(node->left, inorder);
   
    // then print the data of node
    inorder.push_back(node->data);
   
    // now recur on right child
    Inorder(node->right, inorder);
}
   
// Preorder traversal
void Preorder(
    struct Node* node,
    vector<int>& preorder)
{
    if (node == NULL)
        return;
   
    // First print data of node
    preorder.push_back(node->data);
   
    // then recur on left subtree
    Preorder(node->left, preorder);
   
    // now recur on right subtree
    Preorder(node->right, preorder);
}
   
// Function to print the any array
void PrintArray(vector<int> median)
{
    for (int i = 0;
         i < median.size(); i++)
        cout << median[i] << " ";
   
    return;
}
   
// Function to create and print
// the Median array
void MedianArray(struct Node* node)
{
    // Vector to store
    // the median values
    vector<int> median;
   
    if (node == NULL)
        return;
   
    vector<int> preorder,
        postorder,
        inorder;
   
    // Traverse the tree
    Postorder(node, postorder);
    Inorder(node, inorder);
    Preorder(node, preorder);
   
    int n = preorder.size();
    for (int i = 0; i < n; i++) {
   
        // Temporary vector to sort
        // the three values
        vector<int> temp;
   
        // Insert the values at ith index
        // for each traversal into temp
        temp.push_back(postorder[i]);
        temp.push_back(inorder[i]);
        temp.push_back(preorder[i]);
   
        // Sort the temp vector to
        // find the median
        sort(temp.begin(), temp.end());
   
        // Insert the middle value in
        // temp into the median vector
        median.push_back(temp[1]);
    }
   
    PrintArray(median);
    return;
}
   
// Driver Code
int main()
{
    struct Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
   
    MedianArray(root);
   
    return 0;
}

Java

// Java program to Obtain the median
// array for the preorder, postorder
// and inorder traversal of a binary tree
import java.io.*;
import java.util.*;
 
// A binary tree node has data,
// a pointer to the left child
// and a pointer to the right child
class Node
{
  int data;
  Node left,right;
  Node(int item)
  {
    data = item;
    left = right = null;
  }
}
class Tree {
  public static Vector<Integer> postorder = new Vector<Integer>();
  public static Vector<Integer> inorder = new Vector<Integer>();
  public static Vector<Integer> preorder = new Vector<Integer>();
  public static Node root;
 
  // Postorder traversal
  public static void Postorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First recur on left subtree
    Postorder(node.left);
 
    // then recur on right subtree
    Postorder(node.right);
 
    // now deal with the node
    postorder.add(node.data);
  }
  // Inorder traversal
  public static void Inorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First recur on left child
    Inorder(node.left);
 
    // then print the data of node
    inorder.add(node.data);
 
    // now recur on right child
    Inorder(node.right);      
  }
 
  // Preorder traversal
  public static void Preorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First print data of node
    preorder.add(node.data);
 
    // then recur on left subtree
    Preorder(node.left);
 
    // now recur on right subtree
    Preorder(node.right);
  }
 
  // Function to print the any array    
  public static void PrintArray(Vector<Integer> median)
  {
    for(int i = 0; i < median.size(); i++)
    {
      System.out.print(median.get(i) + " ");
    }
  }
 
  // Function to create and print
  // the Median array
  public static void MedianArray(Node node)
  {
 
    // Vector to store
    // the median values
    Vector<Integer> median = new Vector<Integer>();
    if(node == null)
    {
      return;
    }
 
    // Traverse the tree
    Postorder(node);
    Inorder(node);
    Preorder(node);
    int n = preorder.size();
    for(int i = 0; i < n; i++)
    {
 
      // Temporary vector to sort
      // the three values
      Vector<Integer> temp = new Vector<Integer>();
 
      // Insert the values at ith index
      // for each traversal into temp
      temp.add(postorder.get(i));
      temp.add(inorder.get(i));
      temp.add(preorder.get(i));
 
      // Sort the temp vector to
      // find the median
      Collections.sort(temp);
 
      // Insert the middle value in
      // temp into the median vector
      median.add(temp.get(1));
    }
    PrintArray(median);
  }
 
  // Driver Code
  public static void main (String[] args)
  {
    Tree.root = new Node(1);
    Tree.root.left = new Node(2);
    Tree.root.right = new Node(3);
    Tree.root.left.left = new Node(4);
    Tree.root.left.right = new Node(5);
    MedianArray(root);
  }
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 program to Obtain the median
# array for the preorder, postorder
# and inorder traversal of a binary tree
 
 
# A binary tree node has data,
# a pointer to the left child
# and a pointer to the right child
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
 
# Postorder traversal
def Postorder(node):
    global preorder
    if (node == None):
        return
    # First recur on left subtree
    Postorder(node.left)
 
    # then recur on right subtree
    Postorder(node.right)
 
    # now deal with the node
    postorder.append(node.data)
 
# Inorder traversal
def Inorder(node):
    global inorder
    if (node == None):
        return
 
    # First recur on left child
    Inorder(node.left)
 
    # then print the data of node
    inorder.append(node.data)
 
    # now recur on right child
    Inorder(node.right)
 
# Preorder traversal
def Preorder(node):
    global preorder
 
    if (node == None):
        return
 
    # First print data of node
    preorder.append(node.data)
 
    # then recur on left subtree
    Preorder(node.left)
 
    # now recur on right subtree
    Preorder(node.right)
 
# Function to print the any array
def PrintArray(median):
    for i in range(len(median)):
        print(median[i], end = " ")
 
    return
 
# Function to create and print
# the Median array
def MedianArray(node):
    global inorder, postorder, preorder
 
    # Vector to store
    # the median values
    median = []
 
    if (node == None):
        return
 
    # Traverse the tree
    Postorder(node)
    Inorder(node)
    Preorder(node)
 
    n = len(preorder)
 
    for i in range(n):
 
        # Temporary vector to sort
        # the three values
        temp = []
 
        # Insert the values at ith index
        # for each traversal into temp
        temp.append(postorder[i])
        temp.append(inorder[i])
        temp.append(preorder[i])
 
        # Sort the temp vector to
        # find the median
        temp = sorted(temp)
 
        # Insert the middle value in
        # temp into the median vector
        median.append(temp[1])
 
    PrintArray(median)
 
# Driver Code
if __name__ == '__main__':
    preorder, inorder, postorder = [], [], []
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
 
    MedianArray(root)
 
# This code is contributed by mohit kumar 29

C#

// C# program to Obtain the median
// array for the preorder, postorder
// and inorder traversal of a binary tree
using System;
using System.Collections.Generic;
using System.Numerics;
 
// A binary tree node has data,
// a pointer to the left child
// and a pointer to the right child
public class Node
{
  public int data;
  public Node left,right;
  public Node(int item)
  {
    data = item;
    left = right = null;
  }
}
public class Tree{
  static List<int> postorder = new List<int>();
  static List<int> inorder = new List<int>();
  static List<int> preorder = new List<int>();
 
  static Node root;
  // Postorder traversal
  public static void Postorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First recur on left subtree
    Postorder(node.left);
 
    // then recur on right subtree
    Postorder(node.right);
 
    // now deal with the node
    postorder.Add(node.data);
  }
  // Inorder traversal
  public static void Inorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First recur on left child
    Inorder(node.left);
 
    // then print the data of node
    inorder.Add(node.data);
 
    // now recur on right child
    Inorder(node.right);      
  }
  // Preorder traversal
  public static void Preorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First print data of node
    preorder.Add(node.data);
 
    // then recur on left subtree
    Preorder(node.left);
 
    // now recur on right subtree
    Preorder(node.right);
  }
 
  // Function to print the any array    
  public static void PrintArray(List<int> median)
  {
    for(int i = 0; i < median.Count; i++)
    {
      Console.Write(median[i] + " ");
    }
  }
 
  // Function to create and print
  // the Median array
  public static void MedianArray(Node node)
  {
 
    // Vector to store
    // the median values
    List<int> median = new List<int>();
    if(node == null)
    {
      return;
    }
 
    // Traverse the tree
    Postorder(node);
    Inorder(node);
    Preorder(node);
    int n = preorder.Count;
    for(int i = 0; i < n; i++)
    {
 
      // Temporary vector to sort
      // the three values
      List<int> temp = new List<int>();
 
      // Insert the values at ith index
      // for each traversal into temp
      temp.Add(postorder[i]);
      temp.Add(inorder[i]);
      temp.Add(preorder[i]);
 
      // Sort the temp vector to
      // find the median
      temp.Sort();
 
      // Insert the middle value in
      // temp into the median vector
      median.Add(temp[1]);
    }
    PrintArray(median);
  }
 
  // Driver code
  static public void Main ()
  {
    Tree.root = new Node(1);
    Tree.root.left = new Node(2);
    Tree.root.right = new Node(3);
    Tree.root.left.left = new Node(4);
    Tree.root.left.right = new Node(5);
    MedianArray(root);
  }
}
 
// This code is contributed by rag2127

Javascript

<script>
 
// JavaScript program to Obtain the median
// array for the preorder, postorder
// and inorder traversal of a binary tree
 
// A binary tree node has data,
// a pointer to the left child
// and a pointer to the right child
class Node
{
    constructor(item)
    {
        this.data = item;
        this.left = this.right = null;
    }
}
 
let postorder = [];
let inorder = [];
let preorder = [];
 
// Postorder traversal
function Postorder(node)
{
    if(node == null)
    {
      return;
    }
  
    // First recur on left subtree
    Postorder(node.left);
  
    // then recur on right subtree
    Postorder(node.right);
  
    // now deal with the node
    postorder.push(node.data);
}
 
// Inorder traversal
function Inorder(node)
{
    if(node == null)
    {
      return;
    }
  
    // First recur on left child
    Inorder(node.left);
  
    // then print the data of node
    inorder.push(node.data);
  
    // now recur on right child
    Inorder(node.right);  
}
 
// Preorder traversal
function Preorder(node)
{
    if(node == null)
    {
      return;
    }
  
    // First print data of node
    preorder.push(node.data);
  
    // then recur on left subtree
    Preorder(node.left);
  
    // now recur on right subtree
    Preorder(node.right);
}
// Function to print the any array
function PrintArray(median)
{
    for(let i = 0; i < median.length; i++)
    {
      document.write(median[i] + " ");
    }
}
 
// Function to create and print
  // the Median array
function MedianArray(node)
{
    // Vector to store
    // the median values
    let median = [];
    if(node == null)
    {
      return;
    }
  
    // Traverse the tree
    Postorder(node);
    Inorder(node);
    Preorder(node);
    let n = preorder.length;
    for(let i = 0; i < n; i++)
    {
  
      // Temporary vector to sort
      // the three values
      let temp = [];
  
      // Insert the values at ith index
      // for each traversal into temp
      temp.push(postorder[i]);
      temp.push(inorder[i]);
      temp.push(preorder[i]);
  
      // Sort the temp vector to
      // find the median
      temp.sort(function(a,b){return a-b;});
  
      // Insert the middle value in
      // temp into the median vector
      median.push(temp[1]);
    }
    PrintArray(median);
}
 
 // Driver Code
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
MedianArray(root);
         
// This code is contributed by patel2127
 
</script>
Producción: 

4 2 4 3 3

 

Complejidad de tiempo: O(N)
 

Publicación traducida automáticamente

Artículo escrito por muskan_garg 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 *