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