求二叉树的中值数组

原文:https://www . geesforgeks . org/find-中值数组换二叉树/

先决条件: 树遍历(有序、前序和后序)、中值
给定一棵具有整数节点的二叉树，任务是为树的前序、后序和有序遍历中的每个位置找到中值。

中值数组是借助于树的前序、后序和有序遍历形成的数组，这样
med[i] =中值(前序[i]、有序[i]、有序[i])

例:

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


进场:

• 首先，找到给定二叉树的前序、后序和有序遍历，并将它们分别存储在向量中。


• 现在，对于从 0 到 N 的每个位置，将每个遍历数组中该位置的值插入一个向量。矢量大小为 3N。


• 最后，对这个向量进行排序，这个位置的中位数由第二元素给出。在这个向量中，它有 3N 个元素。因此在排序之后，中间的元素，第二个元素，每 3 个元素给出一个中间值。

以下是上述方法的实现:

卡片打印处理机（Card Print Processor 的缩写）

// C++ program to Obtain the median
// array for the preorder, postorder
// and inorder traversal of a binary tree
#include
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& 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& 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& 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 median)
{
    for (int i = 0;
         i         cout <    return;
}
// Function to create and print
// the Median array
void MedianArray(struct Node* node)
{
    // Vector to store
    // the median values
    vector median;
    if (node == NULL)
        return;
    vector preorder,
        postorder,
        inorder;
    // Traverse the tree
    Postorder(node, postorder);
    Inorder(node, inorder);
    Preorder(node, preorder);
    int n = preorder.size();
    for (int i = 0; i         // Temporary vector to sort
        // the three values
        vector 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 postorder = new Vector();
  public static Vector inorder = new Vector();
  public static Vector preorder = new Vector();
  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 median)
  {
    for(int i = 0; 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 median = new Vector();
    if(node == null)
    {
      return;
    }
    // Traverse the tree
    Postorder(node);
    Inorder(node);
    Preorder(node);
    int n = preorder.size();
    for(int i = 0; i     {
      // Temporary vector to sort
      // the three values
      Vector temp = new Vector();
      // 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


Python 3

# 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 postorder = new List();
  static List inorder = new List();
  static List preorder = new List();
  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 median)
  {
    for(int i = 0; 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 median = new List();
    if(node == null)
    {
      return;
    }
    // Traverse the tree
    Postorder(node);
    Inorder(node);
    Preorder(node);
    int n = preorder.Count;
    for(int i = 0; i     {
      // Temporary vector to sort
      // the three values
      List temp = new List();
      // 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


java 描述语言

Output: 

4 2 4 3 3


时间复杂度:O(N)T4】