Dada una string s que consta de paréntesis { ‘(‘ y ‘)’ } y números enteros, la tarea es construir un árbol binario a partir de ella e imprimir su recorrido Preorder .
Ejemplos:
Entrada: S = “1(2)(3)”
Salida: 1 2 3
Explicación: El árbol binario correspondiente es el siguiente:
1
/ \
2 3Entrada: “4(2(3)(1))(6(5))”
Salida: 4 2 3 1 6 5
Explicación:
El árbol binario correspondiente es el siguiente:4
/ \
2 6
/ \ /
3 1 5
Enfoque recursivo : consulte el artículo anterior para resolver el problema de forma recursiva.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque: este problema se puede resolver utilizando la estructura de datos de pila . Siga los pasos a continuación para resolver el problema:
- Actualice el carácter en la posición 0 como raíz del árbol binario e inicialice una pila stk .
- Iterar en el rango [1, N-1] usando la variable i :
- Al final de los pasos anteriores, devuelva el Node raíz del árbol binario.
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; // Build a tree node having left and // right pointers set to null initially struct Node { Node* left; Node* right; int data; // Constructor to set the data of // the newly created tree node Node(int element) { data = element; this->left = nullptr; this->right = nullptr; } }; // Utility function to print // preorder traversal of the tree void preorder(Node* root) { if (!root) return; cout << root->data << " "; preorder(root->left); preorder(root->right); } // Function to construct a // tree using bracket notation Node* constructTree(string s) { // First character is the root of the tree Node* root = new Node(s[0] - '0'); // Stack used to store the // previous root elements stack<Node*> stk; // Iterate over remaining characters for (int i = 1; i < s.length(); i++) { // If current character is '(' if (s[i] == '(') { // Push root into stack stk.push(root); } // If current character is ')' else if (s[i] == ')') { // Make root the top most // element in the stack root = stk.top(); // Remove the top node stk.pop(); } // If current character is a number else { // If left is null, then put the new // node to the left and move to the // left of the root if (root->left == nullptr) { Node* left = new Node(s[i] - '0'); root->left = left; root = root->left; } // Otherwise, if right is null, then // put the new node to the right and // move to the right of the root else if (root->right == nullptr) { Node* right = new Node(s[i] - '0'); root->right = right; root = root->right; } } } // Return the root return root; } // Driver code int main() { // Input string s = "4(2(3)(1))(6(5))"; // Function calls Node* root = constructTree(s); preorder(root); return 0; }
Java
// Java program for the above approach import java.util.*; public class Main { // Class containing left and // right child of current // node and key value static class Node { public int data; public Node left, right; public Node(int element) { data = element; left = right = null; } } // Utility function to print // 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 construct a // tree using bracket notation static Node constructTree(String s) { // First character is the root of the tree Node root = new Node(s.charAt(0) - '0'); // Stack used to store the // previous root elements Stack<Node> stk = new Stack<Node>(); // Iterate over remaining characters for (int i = 1; i < s.length(); i++) { // If current character is '(' if (s.charAt(i) == '(') { // Push root into stack stk.push(root); } // If current character is ')' else if (s.charAt(i) == ')') { // Make root the top most // element in the stack root = stk.peek(); // Remove the top node stk.pop(); } // If current character is a number else { // If left is null, then put the new // node to the left and move to the // left of the root if (root.left == null) { Node left = new Node(s.charAt(i) - '0'); root.left = left; root = root.left; } // Otherwise, if right is null, then // put the new node to the right and // move to the right of the root else if (root.right == null) { Node right = new Node(s.charAt(i) - '0'); root.right = right; root = root.right; } } } // Return the root return root; } public static void main(String[] args) { // Input String s = "4(2(3)(1))(6(5))"; // Function calls Node root = constructTree(s); preorder(root); } } // This code is contributed by divyesh072019.
Python3
# Python program for the above approach # Build a tree node having left and # right pointers set to null initially class Node: # Constructor to set the data of # the newly created tree node def __init__(self, element): self.data = element self.left = None self.right = None # Utility function to print # preorder traversal of the tree def preorder(root): if (not root): return print(root.data, end = " ") preorder(root.left) preorder(root.right) # Function to construct a # tree using bracket notation def constructTree(s): # First character is the root of the tree root = Node(ord(s[0]) - ord('0')) # Stack used to store the # previous root elements stk = [] # Iterate over remaining characters for i in range(1,len(s)): # If current character is '(' if (s[i] == '('): # Push root into stack stk.append(root) # If current character is ')' elif (s[i] == ')'): # Make root the top most # element in the stack root = stk[-1] # Remove the top node del stk[-1] # If current character is a number else: # If left is null, then put the new # node to the left and move to the # left of the root if (root.left == None): left = Node(ord(s[i]) - ord('0')) root.left = left root = root.left # Otherwise, if right is null, then # put the new node to the right and # move to the right of the root elif (root.right == None): right = Node(ord(s[i]) - ord('0')) root.right = right root = root.right # Return the root return root # Driver code if __name__ == '__main__': # Input s = "4(2(3)(1))(6(5))" # Function calls root = constructTree(s) preorder(root) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach using System; using System.Collections; class GFG { // Class containing left and // right child of current // node and key value class Node { public int data; public Node left, right; public Node(int element) { data = element; left = right = null; } } // Utility function to print // 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 construct a // tree using bracket notation static Node constructTree(string s) { // First character is the root of the tree Node root = new Node(s[0] - '0'); // Stack used to store the // previous root elements Stack stk = new Stack(); // Iterate over remaining characters for (int i = 1; i < s.Length; i++) { // If current character is '(' if (s[i] == '(') { // Push root into stack stk.Push(root); } // If current character is ')' else if (s[i] == ')') { // Make root the top most // element in the stack root = (Node)(stk.Peek()); // Remove the top node stk.Pop(); } // If current character is a number else { // If left is null, then put the new // node to the left and move to the // left of the root if (root.left == null) { Node left = new Node(s[i] - '0'); root.left = left; root = root.left; } // Otherwise, if right is null, then // put the new node to the right and // move to the right of the root else if (root.right == null) { Node right = new Node(s[i] - '0'); root.right = right; root = root.right; } } } // Return the root return root; } // Driver code static void Main() { // Input string s = "4(2(3)(1))(6(5))"; // Function calls Node root = constructTree(s); preorder(root); } } // This code is contributed by decode2207.
Javascript
<script> // Javascript program for the above approach class Node { constructor(element) { this.left = null; this.right = null; this.data = element; } } // Utility function to print // preorder traversal of the tree function preorder(root) { if (root == null) return; document.write(root.data + " "); preorder(root.left); preorder(root.right); } // Function to construct a // tree using bracket notation function constructTree(s) { // First character is the root of the tree let root = new Node(s[0].charCodeAt() - '0'.charCodeAt()); // Stack used to store the // previous root elements let stk = []; // Iterate over remaining characters for (let i = 1; i < s.length; i++) { // If current character is '(' if (s[i] == '(') { // Push root into stack stk.push(root); } // If current character is ')' else if (s[i] == ')') { // Make root the top most // element in the stack root = stk[stk.length - 1]; // Remove the top node stk.pop(); } // If current character is a number else { // If left is null, then put the new // node to the left and move to the // left of the root if (root.left == null) { let left = new Node(s[i].charCodeAt() - '0'.charCodeAt()); root.left = left; root = root.left; } // Otherwise, if right is null, then // put the new node to the right and // move to the right of the root else if (root.right == null) { let right = new Node(s[i].charCodeAt() - '0'.charCodeAt()); root.right = right; root = root.right; } } } // Return the root return root; } // Input let s = "4(2(3)(1))(6(5))"; // Function calls let root = constructTree(s); preorder(root); // This code is contributed by divyeshrabadiya07. </script>
4 2 3 1 6 5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ManjuKrishna y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA