Dada una string str que contiene una expresión ternaria que se puede anidar. La tarea es convertir la expresión ternaria dada en un árbol binario y devolver la raíz.
Ejemplos:
Input: str = "a?b:c"
Output: a b c
a
/ \
b c
The preorder traversal of the above tree is a b c.
Input: str = "a?b?c:d:e"
Output: a b c d e
a
/ \
b e
/ \
c d
Enfoque: Este es un enfoque basado en la pila para el problema dado. Dado que el operador ternario tiene asociatividad de derecha a izquierda, la string se puede recorrer de derecha a izquierda. Tome las letras una por una saltándose las letras ‘?’ y ‘:’ ya que estas letras se usan para decidir si la letra actual (alfabeto [a a z]) irá a la pila o se usará para sacar los 2 elementos superiores de la parte superior de la pila para convertirlos en los hijos de la letra actual que luego se empuja a la pila. Esto forma el árbol de abajo hacia arriba y el último elemento que queda en la pila después de procesar toda la string es la raíz del árbol.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Node structure
struct Node {
char data;
Node *left, *right;
};
// Function to create a new node
Node* createNewNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = NULL, node->right = NULL;
return node;
}
// Function to print the preorder
// traversal of the tree
void preorder(Node* root)
{
if (root == NULL)
return;
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
// Function to convert the expression to a binary tree
Node* convertExpression(string str)
{
stack<Node*> s;
// If the letter is the last letter of
// the string or is of the type :letter: or ?letter:
// we push the node pointer containing
// the letter to the stack
for (int i = str.length() - 1; i >= 0;) {
if ((i == str.length() - 1)
|| (i != 0 && ((str[i - 1] == ':'
&& str[i + 1] == ':')
|| (str[i - 1] == '?'
&& str[i + 1] == ':')))) {
s.push(createNewNode(str[i]));
}
// If we do not push the current letter node to stack,
// it means the top 2 nodes in the stack currently are the
// left and the right children of the current node
// So pop these elements and assign them as the
// children of the current letter node and then
// push this node into the stack
else {
Node* lnode = s.top();
s.pop();
Node* rnode = s.top();
s.pop();
Node* node = createNewNode(str[i]);
node->left = lnode;
node->right = rnode;
s.push(node);
}
i -= 2;
}
// Finally, there will be only 1 element
// in the stack which will be the
// root of the binary tree
return s.top();
}
// Driver code
int main()
{
string str = "a?b?c:d:e";
// Convert expression
Node* root = convertExpression(str);
// Print the preorder traversal
preorder(root);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
public class Main
{
// Class containing left and
// right child of current
// node and key value
static class Node {
public char data;
public Node left, right;
public Node(char data)
{
this.data = data;
left = right = null;
}
}
// Function to create a new node
static Node createNewNode(char data)
{
Node node = new Node(data);
return node;
}
// Function to print the preorder
// traversal of the tree
static void preorder(Node root)
{
if (root == null)
return;
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
// Function to convert the expression to a binary tree
static Node convertExpression(String str)
{
Stack<Node> s = new Stack<Node>();
// If the letter is the last letter of
// the string or is of the type :letter: or ?letter:
// we push the node pointer containing
// the letter to the stack
for (int i = str.length() - 1; i >= 0😉 {
if ((i == str.length() - 1)
|| (i != 0 && ((str.charAt(i - 1) == ':'
&& str.charAt(i + 1) == ':')
|| (str.charAt(i - 1) == '?'
&& str.charAt(i + 1) == ':')))) {
s.push(createNewNode(str.charAt(i)));
}
// If we do not push the current
// letter node to stack,
// it means the top 2 nodes in
// the stack currently are the
// left and the right children of the current node
// So pop these elements and assign them as the
// children of the current letter node and then
// push this node into the stack
else {
Node lnode = (Node)s.peek();
s.pop();
Node rnode = (Node)s.peek();
s.pop();
Node node = createNewNode(str.charAt(i));
node.left = lnode;
node.right = rnode;
s.push(node);
}
i -= 2;
}
// Finally, there will be only 1 element
// in the stack which will be the
// root of the binary tree
return (Node)s.peek();
}
// Driver code
public static void main(String[] args)
{
String str = "a?b?c:d:e";
// Convert expression
Node root = convertExpression(str);
// Print the preorder traversal
preorder(root);
}
}
// This code is contributed by divyesh072019.
Python3
# Python3 implementation of the approach # Tree Structure class Node: # Constructor to set the data of # the newly created tree node def __init__(self, data): self.data = data self.left = None self.right = None # Function to create a new node def createNewNode(data): node = Node(data) return node # Function to print the preorder # traversal of the tree def preorder(root): if (root == None): return print(root.data, end = " ") preorder(root.left) preorder(root.right) # Function to convert the expression to a binary tree def convertExpression(Str): s = [] # If the letter is the last letter of # the string or is of the type :letter: or ?letter: # we push the node pointer containing # the letter to the stack i = len(Str) - 1 while i >= 0: if ((i == len(Str) - 1) or (i != 0 and ((Str[i - 1] == ':' and Str[i + 1] == ':') or (Str[i - 1] == '?' and Str[i + 1] == ':')))): s.append(createNewNode(Str[i])) # If we do not push the current # letter node to stack, # it means the top 2 nodes in # the stack currently are the # left and the right children of the current node # So pop these elements and assign them as the # children of the current letter node and then # push this node into the stack else: lnode = s[-1] s.pop() rnode = s[-1] s.pop() node = createNewNode(Str[i]) node.left = lnode node.right = rnode s.append(node) i -= 2 # Finally, there will be only 1 element # in the stack which will be the # root of the binary tree return s[-1] Str = "a?b?c:d:e" # Convert expression root = convertExpression(Str) # Print the preorder traversal preorder(root) # This code is contributed by divyeshrabadiya07.
C#
// C# implementation of the approach
using System;
using System.Collections;
class GFG {
// Class containing left and
// right child of current
// node and key value
class Node {
public char data;
public Node left, right;
public Node(char data)
{
this.data = data;
left = right = null;
}
}
// Function to create a new node
static Node createNewNode(char data)
{
Node node = new Node(data);
return node;
}
// Function to print the preorder
// traversal of the tree
static void preorder(Node root)
{
if (root == null)
return;
Console.Write(root.data + " ");
preorder(root.left);
preorder(root.right);
}
// Function to convert the expression to a binary tree
static Node convertExpression(string str)
{
Stack s = new Stack();
// If the letter is the last letter of
// the string or is of the type :letter: or ?letter:
// we push the node pointer containing
// the letter to the stack
for (int i = str.Length - 1; i >= 0;) {
if ((i == str.Length - 1)
|| (i != 0 && ((str[i - 1] == ':'
&& str[i + 1] == ':')
|| (str[i - 1] == '?'
&& str[i + 1] == ':')))) {
s.Push(createNewNode(str[i]));
}
// If we do not push the current
// letter node to stack,
// it means the top 2 nodes in
// the stack currently are the
// left and the right children of the current node
// So pop these elements and assign them as the
// children of the current letter node and then
// push this node into the stack
else {
Node lnode = (Node)s.Peek();
s.Pop();
Node rnode = (Node)s.Peek();
s.Pop();
Node node = createNewNode(str[i]);
node.left = lnode;
node.right = rnode;
s.Push(node);
}
i -= 2;
}
// Finally, there will be only 1 element
// in the stack which will be the
// root of the binary tree
return (Node)s.Peek();
}
static void Main() {
string str = "a?b?c:d:e";
// Convert expression
Node root = convertExpression(str);
// Print the preorder traversal
preorder(root);
}
}
// This code is contributed by decode2207.
Javascript
<script>
// JavaScript implementation of the approach
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Function to create a new node
function createNewNode(data)
{
let node = new Node(data);
return node;
}
// Function to print the preorder
// traversal of the tree
function preorder(root)
{
if (root == null)
return;
document.write(root.data + " ");
preorder(root.left);
preorder(root.right);
}
// Function to convert the expression to a binary tree
function convertExpression(str)
{
let s = [];
// If the letter is the last letter of
// the string or is of the type :letter: or ?letter:
// we push the node pointer containing
// the letter to the stack
for (let i = str.length - 1; i >= 0;) {
if ((i == str.length - 1)
|| (i != 0 && ((str[i - 1] == ':'
&& str[i + 1] == ':')
|| (str[i - 1] == '?'
&& str[i + 1] == ':')))) {
s.push(createNewNode(str[i]));
}
// If we do not push the current
// letter node to stack,
// it means the top 2 nodes in
// the stack currently are the
// left and the right children of the current node
// So pop these elements and assign them as the
// children of the current letter node and then
// push this node into the stack
else {
let lnode = s[s.length - 1];
s.pop();
let rnode = s[s.length - 1];
s.pop();
let node = createNewNode(str[i]);
node.left = lnode;
node.right = rnode;
s.push(node);
}
i -= 2;
}
// Finally, there will be only 1 element
// in the stack which will be the
// root of the binary tree
return s[s.length - 1];
}
let str = "a?b?c:d:e";
// Convert expression
let root = convertExpression(str);
// Print the preorder traversal
preorder(root);
</script>
Producción:
a b c d e
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por sh16011993 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA