Construct tree from given string parenthesis expression
Here given code implementation process.
/*
C Program
Construct tree from given string parenthesis expression
*/
#include <stdio.h>
#include <stdlib.h>
//Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
struct MyStack
{
struct Node *element;
int indicator;
struct MyStack *next;
};
//Create a MyStack element and return this reference
struct MyStack *push(struct Node *tree_node, struct MyStack **top, int indicator)
{
struct MyStack *node = (struct MyStack *) malloc(sizeof(struct MyStack));
if (node != NULL)
{
//set pointer values
node->element = tree_node;
node->next = *top;
node->indicator = indicator;*top = node;
}
else
{
printf("Memory Overflow\n");
}
return node;
}
//Remove a top node of stack
void pop(struct MyStack **top)
{
if ( *top != NULL)
{
struct MyStack *remove = *top;
*top = remove->next;
remove->element = NULL;
remove->next = NULL;
//free the allocated memory of node
free(remove);
remove = NULL;
}
}
//This is creating a binary tree node and return new node
struct Node *get_node(int data)
{
// Create dynamic node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return new_node;
}
//Display inorder elements
void print_inorder(struct Node *node)
{
if (node != NULL)
{
print_inorder(node->left);
//Print node value
printf(" %d", node->data);
print_inorder(node->right);
}
}
//Display pre order elements
void print_preorder(struct Node *node)
{
if (node != NULL)
{
//Print node value
printf(" %d", node->data);
print_preorder(node->left);
print_preorder(node->right);
}
}
//Display postorder elements
void print_postorder(struct Node *node)
{
if (node != NULL)
{
print_postorder(node->left);
print_postorder(node->right);
//Print node value
printf(" %d", node->data);
}
}
//Constructing a binary tree from string
// 1) expression can be contains positive number example (1,44,2324,55 etc)
// 2) Expression contains parentheses which is indicates is left and right child
// Example 1 : () null child, other (4) child with node 4
struct Node *construct_tree(char str[], int n)
{
// Define loop controlling variables
int j = 0;
int i = 0;
// Define stack variable
struct MyStack *top = NULL;
// Define some useful Tree node variables
struct Node *auxiliary = NULL;
struct Node *temp = NULL;
struct Node *child = NULL, *parent = NULL;
// Define some auxiliary variables
int num = 0;
int position = 0;
//Display given expression
printf("\n Expression : %s\n", str);
//Construct tree
while (i < n)
{
if (str[i] == '(')
{
// Add null node
temp = NULL;
push(temp, &top, 0);
i++;
}
else if (str[i] == ')')
{
position = 0;
// Reset the value of parent and child node
child = NULL;
parent = NULL;
if (top != NULL)
{
//Get child node
child = top->element;
pop( &top);
}
if (top != NULL)
{
//Get parent node
parent = top->element;
position = top->indicator;
pop(&top);
}
if (parent != NULL)
{
//connect parent to child node
if (position == 0)
{
// Add node in left side
parent->left = child;
position = 1;
}
else if (position == 1)
{
// Add node in right side
parent->right = child;
position = 2;
}
else
{
// Tree exist More than 2 child nodes
// example x(1)(2)(3) x is parent
printf("\n More than 2 child of node %d\n", parent->data);
return NULL;
}
push(parent, &top, position);
}
i++;
}
else if (str[i] >= '1' && str[i] <= '9')
{
num = 0;
// Collect node value
while (i < n && str[i] != '(' && str[i] != ')')
{
num = (num *10) + (str[i] - '0');
i++;
}
// Get new tree node
temp = get_node(num);
if (top != NULL)
{
auxiliary = top->element;
if (auxiliary == NULL)
{
// When stack top node element is empty then add new node to this location
top->element = temp;
}
else
{
// Add new node in tree
push(temp, &top, 0);
}
}
else
{
// When stack is empty, then add first node
push(temp, &top, 0);
}
}
else
{
// When not a valid expression
printf("\n Invalid Expression \n");
return NULL;
}
}
if (top != NULL)
{
auxiliary = top->element;
pop(&top);
return auxiliary;
}
else
{
return NULL;
}
}
//handles the request of construct binary tree
struct Node *make_tree(char str[], int n)
{
if (n <= 0)
{
//Invalid sequence
return NULL;
}
else
{
return construct_tree(str, n);
}
}
//Handles the request of display the element of tree
void print_tree(struct Node *root)
{
if (root == NULL)
{
return;
}
// Display tree elements in three formats
printf("\n Preorder : ");
print_preorder(root);
printf("\n Inorder : ");
print_inorder(root);
printf("\n Postorder : ");
print_postorder(root);
printf("\n");
}
int main()
{
// string expression
char str[] = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
// Get the size
int size = sizeof(str) / sizeof(str[0]) - 1;
struct Node *root = make_tree(str, size);
/*
16
/ \
/ \
/ \
7 8
/ \ / \
4 2 9 3
\ \ /
6 1 15
----------------
Resultant binary tree
*/
print_tree(root);
return 0;
}
Output
Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))
Preorder : 16 7 4 6 2 8 9 1 3 15
Inorder : 4 6 7 2 16 9 1 8 15 3
Postorder : 6 4 2 7 1 9 15 3 8 16
/*
Java Program
Construct tree from given string parenthesis expression
*/
// Binary Tree node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
//Stack Node
class StackNode
{
public Node element;
public StackNode next;
public int indicator;
public StackNode(Node element, int indicator)
{
this.element = element;
this.next = null;
this.indicator = indicator;
}
}
//Define custom stack and its operation
class MyStack
{
public StackNode top;
public int length;
public MyStack()
{
this.top = null;
this.length = 0;
}
//Add a new element in stack
public void push(Node element, int indicator)
{
//Make a new stack node
StackNode new_node = new StackNode(element,indicator);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
this.length++;
}
else
{
System.out.print("Memory overflow\n");
}
}
//remove a top element in stack
public void pop()
{
if (this.top != null)
{
this.top = this.top.next;
this.length--;
}
}
//check that whether stack is empty or not
public boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
public int is_size()
{
return this.length;
}
//Used to get top element of stack
public Node peek()
{
if (this.top != null)
{
return this.top.element;
}
else
{
return null;
}
}
}
//Define Binary Tree
public class BinaryTree
{
public Node root;
public int location;
public BinaryTree()
{
//Set root of tree
this.root = null;
this.location = 0;
}
//Display inorder elements
public void print_inorder(Node node)
{
if (node != null)
{
print_inorder(node.left);
//Print node value
System.out.print(" " + node.data);
print_inorder(node.right);
}
}
//Display pre order elements
public void print_preorder(Node node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data);
print_preorder(node.left);
print_preorder(node.right);
}
}
//Display postorder elements
public void print_postorder(Node node)
{
if (node != null)
{
print_postorder(node.left);
print_postorder(node.right);
//Print node value
System.out.print(" " + node.data);
}
}
//Constructing a binary tree from string
// 1) expression can be contains positive number example (1,44,2324,55 etc)
// 2) Expression contains parentheses which is indicates is left and right child
// Example 1 : () null child, other (4) child with node 4
public Node construct_tree(String str, int n)
{
// Define loop controlling variables
int j = 0;
int i = 0;
// Define stack variable
MyStack stack = new MyStack();
// Define some useful Tree node variables
Node auxiliary = null;
Node temp = null;
Node child = null;
Node parent = null;
// Define some auxiliary variables
int num = 0;
int position = 0;
//Display given expression
System.out.print("\n Expression : " + str + "\n");
//Construct tree
while (i < n)
{
if (str.charAt(i) == '(')
{
// Add null node
temp = null;
stack.push(temp, 0);
i++;
}
else if (str.charAt(i) == ')')
{
if (stack.is_size() < 2)
{
//not a valid parent child relation
return null;
}
position = 0;
// Reset the value of parent and child node
child = null;
parent = null;
if (stack.is_empty() == false)
{
//Get child node
child = stack.peek();
stack.pop();
}
if (stack.is_empty() == false)
{
//Get parent node
parent = stack.peek();
position = stack.top.indicator;
stack.pop();
}
if (parent != null)
{
//connect parent to child node
if (position == 0)
{
// Add node in left side
parent.left = child;
position = 1;
}
else if (position == 1)
{
// Add node in right side
parent.right = child;
position = 2;
}
else
{
// Tree exist More than 2 child nodes
// example x(1)(2)(3) x is parent
System.out.print("\n More than 2 child of node " + parent.data + "\n");
return null;
}
stack.push(parent, position);
}
i++;
}
else if (str.charAt(i) >= '1' && str.charAt(i) <= '9')
{
num = 0;
// Collect node value
while (i < n && str.charAt(i) != '(' && str.charAt(i) != ')')
{
num = (num * 10) + (str.charAt(i) - '0');
i++;
}
// Get new tree node
temp = new Node(num);
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
if (auxiliary == null)
{
// When stack top node element is empty then add new node to this location
stack.top.element = temp;
}
else
{
// Add new node in tree
stack.push(temp, 0);
}
}
else
{
// When stack is empty, then add first node
stack.push(temp, 0);
}
}
else
{
// When not a valid expression
System.out.print("\n Invalid Expression \n");
return null;
}
}
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
stack.pop();
return auxiliary;
}
else
{
return null;
}
}
//handles the request of construct binary tree
public void make_tree(String str, int n)
{
if (n <= 0)
{
//Invalid sequence
this.root = null;
}
else
{
this.root = construct_tree(str, n);
}
}
//Handles the request of display the element of tree
public void print_tree()
{
if (this.root == null)
{
System.out.print("\n Empty Tree\n");
return;
}
System.out.print("\n Preorder : ");
print_preorder(root);
System.out.print("\n Inorder : ");
print_inorder(root);
System.out.print("\n Postorder : ");
print_postorder(root);
System.out.print("\n");
}
public static void main(String[] args)
{
//Create tree object
BinaryTree tree = new BinaryTree();
// string expression
String str = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
// Get the size
int size = str.length();
tree.make_tree(str, size);
/*
16
/ \
/ \
/ \
7 8
/ \ / \
4 2 9 3
\ \ /
6 1 15
----------------
Resultant binary tree
*/
tree.print_tree();
}
}
Output
Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))
Preorder : 16 7 4 6 2 8 9 1 3 15
Inorder : 4 6 7 2 16 9 1 8 15 3
Postorder : 6 4 2 7 1 9 15 3 8 16
// Include header file
#include <iostream>
using namespace std;
//
// C++ Program
// Construct tree from given string parenthesis expression
// Binary Tree node
class Node
{
public: int data;
Node *left;
Node *right;
Node(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Stack Node
class StackNode
{
public: Node *element;
StackNode *next;
int indicator;
StackNode(Node *element, int indicator)
{
this->element = element;
this->next = NULL;
this->indicator = indicator;
}
};
// Define custom stack and its operation
class MyStack
{
public: StackNode *top;
int length;
MyStack()
{
this->top = NULL;
this->length = 0;
}
// Add a new element in stack
void push(Node *element, int indicator)
{
// Make a new stack node
StackNode *new_node = new StackNode(element, indicator);
if (new_node != NULL)
{
new_node->next = this->top;
this->top = new_node;
this->length++;
}
else
{
cout << "Memory overflow\n";
}
}
// remove a top element in stack
void pop()
{
if (this->top != NULL)
{
this->top = this->top->next;
this->length--;
}
}
// check that whether stack is empty or not
bool is_empty()
{
if (this->top != NULL)
{
return false;
}
else
{
return true;
}
}
int is_size()
{
return this->length;
}
// Used to get top element of stack
Node *peek()
{
if (this->top != NULL)
{
return this->top->element;
}
else
{
return NULL;
}
}
};
// Define Binary Tree
class BinaryTree
{
public: Node *root;
int location;
BinaryTree()
{
// Set root of tree
this->root = NULL;
this->location = 0;
}
// Display inorder elements
void print_inorder(Node *node)
{
if (node != NULL)
{
this->print_inorder(node->left);
// Print node value
cout << " " << node->data;
this->print_inorder(node->right);
}
}
// Display pre order elements
void print_preorder(Node *node)
{
if (node != NULL)
{
// Print node value
cout << " " << node->data;
this->print_preorder(node->left);
this->print_preorder(node->right);
}
}
// Display postorder elements
void print_postorder(Node *node)
{
if (node != NULL)
{
this->print_postorder(node->left);
this->print_postorder(node->right);
// Print node value
cout << " " << node->data;
}
}
// Constructing a binary tree from string
// 1) expression can be contains positive number example (1,44,2324,55 etc)
// 2) Expression contains parentheses which is indicates is left and right child
// Example 1 : () null child, other (4) child with node 4
Node *construct_tree(string str, int n)
{
// Define loop controlling variables
int j = 0;
int i = 0;
// Define stack variable
MyStack stack = MyStack();
// Define some useful Tree node variables
Node *auxiliary = NULL;
Node *temp = NULL;
Node *child = NULL;
Node *parent = NULL;
// Define some auxiliary variables
int num = 0;
int position = 0;
// Display given expression
cout << "\n Expression : " << str << "\n";
// Construct tree
while (i < n)
{
if (str[i] == '(')
{
// Add null node
temp = NULL;
stack.push(temp, 0);
i++;
}
else if (str[i] == ')')
{
if (stack.is_size() < 2)
{
// not a valid parent child relation
return NULL;
}
position = 0;
// Reset the value of parent and child node
child = NULL;
parent = NULL;
if (stack.is_empty() == false)
{
// Get child node
child = stack.peek();
stack.pop();
}
if (stack.is_empty() == false)
{
// Get parent node
parent = stack.peek();
position = stack.top->indicator;
stack.pop();
}
if (parent != NULL)
{
// connect parent to child node
if (position == 0)
{
// Add node in left side
parent->left = child;
position = 1;
}
else if (position == 1)
{
// Add node in right side
parent->right = child;
position = 2;
}
else
{
// Tree exist More than 2 child nodes
// example x(1)(2)(3) x is parent
cout << "\n More than 2 child of node " << parent->data << "\n";
return NULL;
}
stack.push(parent, position);
}
i++;
}
else if (str[i] >= '1' && str[i] <= '9')
{
num = 0;
// Collect node value
while (i < n && str[i] != '(' && str[i] != ')')
{
num = (num *10) + (str[i] - '0');
i++;
}
// Get new tree node
temp = new Node(num);
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
if (auxiliary == NULL)
{
// When stack top node element is empty then add new node to this location
stack.top->element = temp;
}
else
{
// Add new node in tree
stack.push(temp, 0);
}
}
else
{
// When stack is empty, then add first node
stack.push(temp, 0);
}
}
else
{
// When not a valid expression
cout << "\n Invalid Expression \n";
return NULL;
}
}
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
stack.pop();
return auxiliary;
}
else
{
return NULL;
}
}
// handles the request of construct binary tree
void make_tree(string str, int n)
{
if (n <= 0)
{
// Invalid sequence
this->root = NULL;
}
else
{
this->root = this->construct_tree(str, n);
}
}
// Handles the request of display the element of tree
void print_tree()
{
if (this->root == NULL)
{
cout << "\n Empty Tree\n";
return;
}
cout << "\n Preorder : ";
this->print_preorder(this->root);
cout << "\n Inorder : ";
this->print_inorder(this->root);
cout << "\n Postorder : ";
this->print_postorder(this->root);
cout << "\n";
}
};
int main()
{
// Create tree object
BinaryTree tree = BinaryTree();
// string expression
string str = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
// Get the size
int size = str.length();
tree.make_tree(str, size);
//
// 16
// / \
// / \
// / \
// 7 8
// / \ / \
// 4 2 9 3
// \ \ /
// 6 1 15
// ----------------
// Resultant binary tree
//
tree.print_tree();
return 0;
}
Output
Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))
Preorder : 16 7 4 6 2 8 9 1 3 15
Inorder : 4 6 7 2 16 9 1 8 15 3
Postorder : 6 4 2 7 1 9 15 3 8 16
// Include namespace system
using System;
// C# Program
// Construct tree from given string parenthesis expression
// Binary Tree node
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Stack Node
public class StackNode
{
public Node element;
public StackNode next;
public int indicator;
public StackNode(Node element, int indicator)
{
this.element = element;
this.next = null;
this.indicator = indicator;
}
}
// Define custom stack and its operation
public class MyStack
{
public StackNode top;
public int length;
public MyStack()
{
this.top = null;
this.length = 0;
}
// Add a new element in stack
public void push(Node element, int indicator)
{
// Make a new stack node
StackNode new_node = new StackNode(element, indicator);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
this.length++;
}
else
{
Console.Write("Memory overflow\n");
}
}
// remove a top element in stack
public void pop()
{
if (this.top != null)
{
this.top = this.top.next;
this.length--;
}
}
// check that whether stack is empty or not
public Boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
public int is_size()
{
return this.length;
}
// Used to get top element of stack
public Node peek()
{
if (this.top != null)
{
return this.top.element;
}
else
{
return null;
}
}
}
// Define Binary Tree
public class BinaryTree
{
public Node root;
public int location;
public BinaryTree()
{
// Set root of tree
this.root = null;
this.location = 0;
}
// Display inorder elements
public void print_inorder(Node node)
{
if (node != null)
{
print_inorder(node.left);
// Print node value
Console.Write(" " + node.data);
print_inorder(node.right);
}
}
// Display pre order elements
public void print_preorder(Node node)
{
if (node != null)
{
// Print node value
Console.Write(" " + node.data);
print_preorder(node.left);
print_preorder(node.right);
}
}
// Display postorder elements
public void print_postorder(Node node)
{
if (node != null)
{
print_postorder(node.left);
print_postorder(node.right);
// Print node value
Console.Write(" " + node.data);
}
}
// Constructing a binary tree from string
// 1) expression can be contains positive number example (1,44,2324,55 etc)
// 2) Expression contains parentheses which is indicates is left and right child
// Example 1 : () null child, other (4) child with node 4
public Node construct_tree(String str, int n)
{
// Define loop controlling variables
int i = 0;
// Define stack variable
MyStack stack = new MyStack();
// Define some useful Tree node variables
Node auxiliary = null;
Node temp = null;
Node child = null;
Node parent = null;
// Define some auxiliary variables
int num = 0;
int position = 0;
// Display given expression
Console.Write("\n Expression : " + str + "\n");
// Construct tree
while (i < n)
{
if (str[i] == '(')
{
// Add null node
temp = null;
stack.push(temp, 0);
i++;
}
else if (str[i] == ')')
{
if (stack.is_size() < 2)
{
// not a valid parent child relation
return null;
}
position = 0;
// Reset the value of parent and child node
child = null;
parent = null;
if (stack.is_empty() == false)
{
// Get child node
child = stack.peek();
stack.pop();
}
if (stack.is_empty() == false)
{
// Get parent node
parent = stack.peek();
position = stack.top.indicator;
stack.pop();
}
if (parent != null)
{
// connect parent to child node
if (position == 0)
{
// Add node in left side
parent.left = child;
position = 1;
}
else if (position == 1)
{
// Add node in right side
parent.right = child;
position = 2;
}
else
{
// Tree exist More than 2 child nodes
// example x(1)(2)(3) x is parent
Console.Write("\n More than 2 child of node " + parent.data + "\n");
return null;
}
stack.push(parent, position);
}
i++;
}
else if (str[i] >= '1' && str[i] <= '9')
{
num = 0;
// Collect node value
while (i < n && str[i] != '(' && str[i] != ')')
{
num = (num * 10) + (str[i] - '0');
i++;
}
// Get new tree node
temp = new Node(num);
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
if (auxiliary == null)
{
// When stack top node element is empty then add new node to this location
stack.top.element = temp;
}
else
{
// Add new node in tree
stack.push(temp, 0);
}
}
else
{
// When stack is empty, then add first node
stack.push(temp, 0);
}
}
else
{
// When not a valid expression
Console.Write("\n Invalid Expression \n");
return null;
}
}
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
stack.pop();
return auxiliary;
}
else
{
return null;
}
}
// handles the request of construct binary tree
public void make_tree(String str, int n)
{
if (n <= 0)
{
// Invalid sequence
this.root = null;
}
else
{
this.root = construct_tree(str, n);
}
}
// Handles the request of display the element of tree
public void print_tree()
{
if (this.root == null)
{
Console.Write("\n Empty Tree\n");
return;
}
Console.Write("\n Preorder : ");
print_preorder(root);
Console.Write("\n Inorder : ");
print_inorder(root);
Console.Write("\n Postorder : ");
print_postorder(root);
Console.Write("\n");
}
public static void Main(String[] args)
{
// Create tree object
BinaryTree tree = new BinaryTree();
// string expression
String str = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
// Get the size
int size = str.Length;
tree.make_tree(str, size);
//
// 16
// / \
// / \
// / \
// 7 8
// / \ / \
// 4 2 9 3
// \ \ /
// 6 1 15
// ----------------
// Resultant binary tree
//
tree.print_tree();
}
}
Output
Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))
Preorder : 16 7 4 6 2 8 9 1 3 15
Inorder : 4 6 7 2 16 9 1 8 15 3
Postorder : 6 4 2 7 1 9 15 3 8 16
<?php
// Php Program
// Construct tree from given string parenthesis expression
// Binary Tree node
class Node
{
public $data;
public $left;
public $right;
function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
// Stack Node
class StackNode
{
public $element;
public $next;
public $indicator;
function __construct($element, $indicator)
{
$this->element = $element;
$this->next = null;
$this->indicator = $indicator;
}
}
// Define custom stack and its operation
class MyStack
{
public $top;
public $length;
function __construct()
{
$this->top = null;
$this->length = 0;
}
// Add a new element in stack
public function push($element, $indicator)
{
// Make a new stack node
$new_node = new StackNode($element, $indicator);
if ($new_node != null)
{
$new_node->next = $this->top;
$this->top = $new_node;
$this->length++;
}
else
{
echo "Memory overflow\n";
}
}
// remove a top element in stack
public function pop()
{
if ($this->top != null)
{
$this->top = $this->top->next;
$this->length--;
}
}
// check that whether stack is empty or not
public function is_empty()
{
if ($this->top != null)
{
return false;
}
else
{
return true;
}
}
public function is_size()
{
return $this->length;
}
// Used to get top element of stack
public function peek()
{
if ($this->top != null)
{
return $this->top->element;
}
else
{
return null;
}
}
}
// Define Binary Tree
class BinaryTree
{
public $root;
public $location;
function __construct()
{
// Set root of tree
$this->root = null;
$this->location = 0;
}
// Display inorder elements
public function print_inorder($node)
{
if ($node != null)
{
$this->print_inorder($node->left);
// Print node value
echo " ". $node->data;
$this->print_inorder($node->right);
}
}
// Display pre order elements
public function print_preorder($node)
{
if ($node != null)
{
// Print node value
echo " ". $node->data;
$this->print_preorder($node->left);
$this->print_preorder($node->right);
}
}
// Display postorder elements
public function print_postorder($node)
{
if ($node != null)
{
$this->print_postorder($node->left);
$this->print_postorder($node->right);
// Print node value
echo " ". $node->data;
}
}
// Constructing a binary tree from string
// 1) expression can be contains positive number example (1,44,2324,55 etc)
// 2) Expression contains parentheses which is indicates is left and right child
// Example 1 : () null child, other (4) child with node 4
public function construct_tree($str, $n)
{
// Define loop controlling variable
$i = 0;
// Define stack variable
$stack = new MyStack();
// Define some useful Tree node variables
$auxiliary = null;
$temp = null;
$child = null;
$parent = null;
// Define some auxiliary variables
$num = 0;
$position = 0;
// Display given expression
echo "\n Expression : ". $str ."\n";
// Construct tree
while ($i < $n)
{
if ($str[$i] == '(')
{
// Add null node
$temp = null;
$stack->push($temp, 0);
$i++;
}
else if ($str[$i] == ')')
{
if ($stack->is_size() < 2)
{
// not a valid parent child relation
return null;
}
$position = 0;
// Reset the value of parent and child node
$child = null;
$parent = null;
if ($stack->is_empty() == false)
{
// Get child node
$child = $stack->peek();
$stack->pop();
}
if ($stack->is_empty() == false)
{
// Get parent node
$parent = $stack->peek();
$position = $stack->top->indicator;
$stack->pop();
}
if ($parent != null)
{
// connect parent to child node
if ($position == 0)
{
// Add node in left side
$parent->left = $child;
$position = 1;
}
else if ($position == 1)
{
// Add node in right side
$parent->right = $child;
$position = 2;
}
else
{
// Tree exist More than 2 child nodes
// example x(1)(2)(3) x is parent
echo "\n More than 2 child of node ". $parent->data ."\n";
return null;
}
$stack->push($parent, $position);
}
$i++;
}
else if (ord($str[$i]) >= ord('1') && ord($str[$i]) <= ord('9'))
{
$num = 0;
// Collect node value
while ($i < $n && $str[$i] != '(' && $str[$i] != ')')
{
$num = ($num * 10) + (ord($str[$i]) - ord('0'));
$i++;
}
// Get new tree node
$temp = new Node($num);
if ($stack->is_empty() == false)
{
$auxiliary = $stack->peek();
if ($auxiliary == null)
{
// When stack top node element is empty then add new node to this location
$stack->top->element = $temp;
}
else
{
// Add new node in tree
$stack->push($temp, 0);
}
}
else
{
// When stack is empty, then add first node
$stack->push($temp, 0);
}
}
else
{
// When not a valid expression
echo "\n Invalid Expression \n";
return null;
}
}
if ($stack->is_empty() == false)
{
$auxiliary = $stack->peek();
$stack->pop();
return $auxiliary;
}
else
{
return null;
}
}
// handles the request of construct binary tree
public function make_tree($str, $n)
{
if ($n <= 0)
{
// Invalid sequence
$this->root = null;
}
else
{
$this->root = $this->construct_tree($str, $n);
}
}
// Handles the request of display the element of tree
public function print_tree()
{
if ($this->root == null)
{
echo "\n Empty Tree\n";
return;
}
echo "\n Preorder : ";
$this->print_preorder($this->root);
echo "\n Inorder : ";
$this->print_inorder($this->root);
echo "\n Postorder : ";
$this->print_postorder($this->root);
echo "\n";
}
}
function main()
{
// Create tree object
$tree = new BinaryTree();
// string expression
$str = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
// Get the size
$size = strlen($str);
$tree->make_tree($str, $size);
//
// 16
// / \
// / \
// / \
// 7 8
// / \ / \
// 4 2 9 3
// \ \ /
// 6 1 15
// ----------------
// Resultant binary tree
//
$tree->print_tree();
}
main();
Output
Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))
Preorder : 16 7 4 6 2 8 9 1 3 15
Inorder : 4 6 7 2 16 9 1 8 15 3
Postorder : 6 4 2 7 1 9 15 3 8 16
// Node Js Program
// Construct tree from given string parenthesis expression
// Binary Tree node
class Node
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Stack Node
class StackNode
{
constructor(element, indicator)
{
this.element = element;
this.next = null;
this.indicator = indicator;
}
}
// Define custom stack and its operation
class MyStack
{
constructor()
{
this.top = null;
this.length = 0;
}
// Add a new element in stack
push(element, indicator)
{
// Make a new stack node
var new_node = new StackNode(element, indicator);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
this.length++;
}
else
{
process.stdout.write("Memory overflow\n");
}
}
// remove a top element in stack
pop()
{
if (this.top != null)
{
this.top = this.top.next;
this.length--;
}
}
// check that whether stack is empty or not
is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
is_size()
{
return this.length;
}
// Used to get top element of stack
peek()
{
if (this.top != null)
{
return this.top.element;
}
else
{
return null;
}
}
}
// Define Binary Tree
class BinaryTree
{
constructor()
{
// Set root of tree
this.root = null;
this.location = 0;
}
// Display inorder elements
print_inorder(node)
{
if (node != null)
{
this.print_inorder(node.left);
// Print node value
process.stdout.write(" " + node.data);
this.print_inorder(node.right);
}
}
// Display pre order elements
print_preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write(" " + node.data);
this.print_preorder(node.left);
this.print_preorder(node.right);
}
}
// Display postorder elements
print_postorder(node)
{
if (node != null)
{
this.print_postorder(node.left);
this.print_postorder(node.right);
// Print node value
process.stdout.write(" " + node.data);
}
}
// Constructing a binary tree from string
// 1) expression can be contains positive number example (1,44,2324,55 etc)
// 2) Expression contains parentheses which is indicates is left and right child
// Example 1 : () null child, other (4) child with node 4
construct_tree(str, n)
{
// Define loop controlling variable
var i = 0;
// Define stack variable
var stack = new MyStack();
// Define some useful Tree node variables
var auxiliary = null;
var temp = null;
var child = null;
var parent = null;
// Define some auxiliary variables
var num = 0;
var position = 0;
// Display given expression
process.stdout.write("\n Expression : " + str + "\n");
// Construct tree
while (i < n)
{
if (str[i] == '(')
{
// Add null node
temp = null;
stack.push(temp, 0);
i++;
}
else if (str[i] == ')')
{
if (stack.is_size() < 2)
{
// not a valid parent child relation
return null;
}
position = 0;
// Reset the value of parent and child node
child = null;
parent = null;
if (stack.is_empty() == false)
{
// Get child node
child = stack.peek();
stack.pop();
}
if (stack.is_empty() == false)
{
// Get parent node
parent = stack.peek();
position = stack.top.indicator;
stack.pop();
}
if (parent != null)
{
// connect parent to child node
if (position == 0)
{
// Add node in left side
parent.left = child;
position = 1;
}
else if (position == 1)
{
// Add node in right side
parent.right = child;
position = 2;
}
else
{
// Tree exist More than 2 child nodes
// example x(1)(2)(3) x is parent
process.stdout.write("\n More than 2 child of node " + parent.data + "\n");
return null;
}
stack.push(parent, position);
}
i++;
}
else if ((str[i]).charCodeAt(0) >= ('1').charCodeAt(0) && (str[i]).charCodeAt(0) <= ('9').charCodeAt(0))
{
num = 0;
// Collect node value
while (i < n && str[i] != '(' && str[i] != ')')
{
num = (num * 10) + ((str[i]).charCodeAt(0) - ('0').charCodeAt(0));
i++;
}
// Get new tree node
temp = new Node(num);
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
if (auxiliary == null)
{
// When stack top node element is empty then add new node to this location
stack.top.element = temp;
}
else
{
// Add new node in tree
stack.push(temp, 0);
}
}
else
{
// When stack is empty, then add first node
stack.push(temp, 0);
}
}
else
{
// When not a valid expression
process.stdout.write("\n Invalid Expression \n");
return null;
}
}
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
stack.pop();
return auxiliary;
}
else
{
return null;
}
}
// handles the request of construct binary tree
make_tree(str, n)
{
if (n <= 0)
{
// Invalid sequence
this.root = null;
}
else
{
this.root = this.construct_tree(str, n);
}
}
// Handles the request of display the element of tree
print_tree()
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree\n");
return;
}
process.stdout.write("\n Preorder : ");
this.print_preorder(this.root);
process.stdout.write("\n Inorder : ");
this.print_inorder(this.root);
process.stdout.write("\n Postorder : ");
this.print_postorder(this.root);
process.stdout.write("\n");
}
}
function main()
{
// Create tree object
var tree = new BinaryTree();
// string expression
var str = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
// Get the size
var size = str.length;
tree.make_tree(str, size);
//
// 16
// / \
// / \
// / \
// 7 8
// / \ / \
// 4 2 9 3
// \ \ /
// 6 1 15
// ----------------
// Resultant binary tree
//
tree.print_tree();
}
main();
Output
Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))
Preorder : 16 7 4 6 2 8 9 1 3 15
Inorder : 4 6 7 2 16 9 1 8 15 3
Postorder : 6 4 2 7 1 9 15 3 8 16
# Python 3 Program
# Construct tree from given string parenthesis expression
# Binary Tree node
class Node :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
# Stack Node
class StackNode :
def __init__(self, element, indicator) :
self.element = element
self.next = None
self.indicator = indicator
# Define custom stack and its operation
class MyStack :
def __init__(self) :
self.top = None
self.length = 0
# Add a new element in stack
def push(self, element, indicator) :
# Make a new stack node
new_node = StackNode(element, indicator)
if (new_node != None) :
new_node.next = self.top
self.top = new_node
self.length += 1
else :
print("Memory overflow\n", end = "")
# remove a top element in stack
def pop(self) :
if (self.top != None) :
self.top = self.top.next
self.length -= 1
# check that whether stack is empty or not
def is_empty(self) :
if (self.top != None) :
return False
else :
return True
def is_size(self) :
return self.length
# Used to get top element of stack
def peek(self) :
if (self.top != None) :
return self.top.element
else :
return None
# Define Binary Tree
class BinaryTree :
def __init__(self) :
# Set root of tree
self.root = None
self.location = 0
# Display inorder elements
def print_inorder(self, node) :
if (node != None) :
self.print_inorder(node.left)
# Print node value
print(" ", node.data, end = "")
self.print_inorder(node.right)
# Display pre order elements
def print_preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.print_preorder(node.left)
self.print_preorder(node.right)
# Display postorder elements
def print_postorder(self, node) :
if (node != None) :
self.print_postorder(node.left)
self.print_postorder(node.right)
# Print node value
print(" ", node.data, end = "")
# Constructing a binary tree from string
# 1) expression can be contains positive number example (1,44,2324,55 etc)
# 2) Expression contains parentheses which is indicates is left and right child
# Example 1 : () null child, other (4) child with node 4
def construct_tree(self, str, n) :
# Define loop controlling variable
i = 0
# Define stack variable
stack = MyStack()
# Define some useful Tree node variables
auxiliary = None
temp = None
child = None
parent = None
# Define some auxiliary variables
num = 0
position = 0
# Display given expression
print("\n Expression : ", str )
# Construct tree
while (i < n) :
if (str[i] == '(') :
# Add null node
temp = None
stack.push(temp, 0)
i += 1
elif(str[i] == ')') :
if (stack.is_size() < 2) :
# not a valid parent child relation
return None
position = 0
# Reset the value of parent and child node
child = None
parent = None
if (stack.is_empty() == False) :
# Get child node
child = stack.peek()
stack.pop()
if (stack.is_empty() == False) :
# Get parent node
parent = stack.peek()
position = stack.top.indicator
stack.pop()
if (parent != None) :
# connect parent to child node
if (position == 0) :
# Add node in left side
parent.left = child
position = 1
elif(position == 1) :
# Add node in right side
parent.right = child
position = 2
else :
# Tree exist More than 2 child nodes
# example x(1)(2)(3) x is parent
print("\n More than 2 child of node ", parent.data )
return None
stack.push(parent, position)
i += 1
elif(ord(str[i]) >= ord('1') and ord(str[i]) <= ord('9')) :
num = 0
# Collect node value
while (i < n and str[i] != '('
and str[i] != ')') :
num = (num * 10) + (ord(str[i]) - ord('0'))
i += 1
# Get new tree node
temp = Node(num)
if (stack.is_empty() == False) :
auxiliary = stack.peek()
if (auxiliary == None) :
# When stack top node element is empty then add new node to this location
stack.top.element = temp
else :
# Add new node in tree
stack.push(temp, 0)
else :
# When stack is empty, then add first node
stack.push(temp, 0)
else :
# When not a valid expression
print("\n Invalid Expression \n", end = "")
return None
if (stack.is_empty() == False) :
auxiliary = stack.peek()
stack.pop()
return auxiliary
else :
return None
# handles the request of construct binary tree
def make_tree(self, str, n) :
if (n <= 0) :
# Invalid sequence
self.root = None
else :
self.root = self.construct_tree(str, n)
# Handles the request of display the element of tree
def print_tree(self) :
if (self.root == None) :
print("\n Empty Tree\n", end = "")
return
print("\n Preorder : ", end = "")
self.print_preorder(self.root)
print("\n Inorder : ", end = "")
self.print_inorder(self.root)
print("\n Postorder : ", end = "")
self.print_postorder(self.root)
print("\n", end = "")
def main() :
# Create tree object
tree = BinaryTree()
# string expression
str = "16(7(4()(6))(2))(8(9()(1))(3(15)))"
# Get the size
size = len(str)
tree.make_tree(str, size)
#
# 16
# / \
# / \
# / \
# 7 8
# / \ / \
# 4 2 9 3
# \ \ /
# 6 1 15
# ----------------
# Resultant binary tree
#
tree.print_tree()
if __name__ == "__main__": main()
Output
Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))
Preorder : 16 7 4 6 2 8 9 1 3 15
Inorder : 4 6 7 2 16 9 1 8 15 3
Postorder : 6 4 2 7 1 9 15 3 8 16
# Ruby Program
# Construct tree from given string parenthesis expression
# Binary Tree node
class Node
# Define the accessor and reader of class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
# Stack Node
class StackNode
# Define the accessor and reader of class StackNode
attr_reader :element, :next, :indicator
attr_accessor :element, :next, :indicator
def initialize(element, indicator)
self.element = element
self.next = nil
self.indicator = indicator
end
end
# Define custom stack and its operation
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top, :length
attr_accessor :top, :length
def initialize()
self.top = nil
self.length = 0
end
# Add a new element in stack
def push(element, indicator)
# Make a new stack node
new_node = StackNode.new(element, indicator)
if (new_node != nil)
new_node.next = self.top
self.top = new_node
self.length += 1
else
print("Memory overflow\n")
end
end
# remove a top element in stack
def pop()
if (self.top != nil)
self.top = self.top.next
self.length -= 1
end
end
# check that whether stack is empty or not
def is_empty()
if (self.top != nil)
return false
else
return true
end
end
def is_size()
return self.length
end
# Used to get top element of stack
def peek()
if (self.top != nil)
return self.top.element
else
return nil
end
end
end
# Define Binary Tree
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root, :location
attr_accessor :root, :location
def initialize()
# Set root of tree
self.root = nil
self.location = 0
end
# Display inorder elements
def print_inorder(node)
if (node != nil)
self.print_inorder(node.left)
# Print node value
print(" ", node.data)
self.print_inorder(node.right)
end
end
# Display pre order elements
def print_preorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.print_preorder(node.left)
self.print_preorder(node.right)
end
end
# Display postorder elements
def print_postorder(node)
if (node != nil)
self.print_postorder(node.left)
self.print_postorder(node.right)
# Print node value
print(" ", node.data)
end
end
# Constructing a binary tree from string
# 1) expression can be contains positive number example (1,44,2324,55 etc)
# 2) Expression contains parentheses which is indicates is left and right child
# Example 1 : () null child, other (4) child with node 4
def construct_tree(str, n)
# Define loop controlling variable
i = 0
# Define stack variable
stack = MyStack.new()
# Define some useful Tree node variables
auxiliary = nil
temp = nil
child = nil
parent = nil
# Define some auxiliary variables
num = 0
position = 0
# Display given expression
print("\n Expression : ", str ,"\n")
# Construct tree
while (i < n)
if (str[i] == '(')
# Add null node
temp = nil
stack.push(temp, 0)
i += 1
elsif(str[i] == ')')
if (stack.is_size() < 2)
# not a valid parent child relation
return nil
end
position = 0
# Reset the value of parent and child node
child = nil
parent = nil
if (stack.is_empty() == false)
# Get child node
child = stack.peek()
stack.pop()
end
if (stack.is_empty() == false)
# Get parent node
parent = stack.peek()
position = stack.top.indicator
stack.pop()
end
if (parent != nil)
# connect parent to child node
if (position == 0)
# Add node in left side
parent.left = child
position = 1
elsif(position == 1)
# Add node in right side
parent.right = child
position = 2
else
# Tree exist More than 2 child nodes
# example x(1)(2)(3) x is parent
print("\n More than 2 child of node ", parent.data ,"\n")
return nil
end
stack.push(parent, position)
end
i += 1
elsif((str[i]).ord >= ('1').ord && (str[i]).ord <= ('9').ord)
num = 0
# Collect node value
while (i < n && str[i] != '(' && str[i] != ')')
num = (num * 10) + ((str[i]).ord - ('0').ord)
i += 1
end
# Get new tree node
temp = Node.new(num)
if (stack.is_empty() == false)
auxiliary = stack.peek()
if (auxiliary == nil)
# When stack top node element is empty then add new node to this location
stack.top.element = temp
else
# Add new node in tree
stack.push(temp, 0)
end
else
# When stack is empty, then add first node
stack.push(temp, 0)
end
else
# When not a valid expression
print("\n Invalid Expression \n")
return nil
end
end
if (stack.is_empty() == false)
auxiliary = stack.peek()
stack.pop()
return auxiliary
else
return nil
end
end
# handles the request of construct binary tree
def make_tree(str, n)
if (n <= 0)
# Invalid sequence
self.root = nil
else
self.root = self.construct_tree(str, n)
end
end
# Handles the request of display the element of tree
def print_tree()
if (self.root == nil)
print("\n Empty Tree\n")
return
end
print("\n Preorder : ")
self.print_preorder(root)
print("\n Inorder : ")
self.print_inorder(root)
print("\n Postorder : ")
self.print_postorder(root)
print("\n")
end
end
def main()
# Create tree object
tree = BinaryTree.new()
# string expression
str = "16(7(4()(6))(2))(8(9()(1))(3(15)))"
# Get the size
size = str.length()
tree.make_tree(str, size)
#
# 16
# / \
# / \
# / \
# 7 8
# / \ / \
# 4 2 9 3
# \ \ /
# 6 1 15
# ----------------
# Resultant binary tree
#
tree.print_tree()
end
main()
Output
Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))
Preorder : 16 7 4 6 2 8 9 1 3 15
Inorder : 4 6 7 2 16 9 1 8 15 3
Postorder : 6 4 2 7 1 9 15 3 8 16
// Scala Program
// Construct tree from given string parenthesis expression
// Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Stack Node
class StackNode(var element: Node , var next: StackNode , var indicator: Int)
{
def this(element: Node, indicator: Int)
{
this(element, null, indicator);
}
}
// Define custom stack and its operation
class MyStack(var top: StackNode , var length: Int)
{
def this()
{
this(null, 0);
}
// Add a new element in stack
def push(element: Node, indicator: Int): Unit = {
// Make a new stack node
var new_node: StackNode = new StackNode(element, indicator);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
this.length += 1;
}
else
{
print("Memory overflow\n");
}
}
// remove a top element in stack
def pop(): Unit = {
if (this.top != null)
{
this.top = this.top.next;
this.length -= 1;
}
}
// check that whether stack is empty or not
def is_empty(): Boolean = {
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
def is_size(): Int = {
return this.length;
}
// Used to get top element of stack
def peek(): Node = {
if (this.top != null)
{
return this.top.element;
}
else
{
return null;
}
}
}
// Define Binary Tree
class BinaryTree(var root: Node , var location: Int)
{
def this()
{
this(null, 0);
}
// Display inorder elements
def print_inorder(node: Node): Unit = {
if (node != null)
{
print_inorder(node.left);
// Print node value
print(" " + node.data);
print_inorder(node.right);
}
}
// Display pre order elements
def print_preorder(node: Node): Unit = {
if (node != null)
{
// Print node value
print(" " + node.data);
print_preorder(node.left);
print_preorder(node.right);
}
}
// Display postorder elements
def print_postorder(node: Node): Unit = {
if (node != null)
{
print_postorder(node.left);
print_postorder(node.right);
// Print node value
print(" " + node.data);
}
}
// Constructing a binary tree from string
// 1) expression can be contains positive number example (1,44,2324,55 etc)
// 2) Expression contains parentheses which is indicates is left and right child
// Example 1 : () null child, other (4) child with node 4
def construct_tree(str: String, n: Int): Node = {
// Define loop controlling variable
var i: Int = 0;
// Define stack variable
var stack: MyStack = new MyStack();
// Define some useful Tree node variables
var auxiliary: Node = null;
var temp: Node = null;
var child: Node = null;
var parent: Node = null;
// Define some auxiliary variables
var num: Int = 0;
var position: Int = 0;
// Display given expression
print("\n Expression : " + str + "\n");
// Construct tree
while (i < n)
{
if (str(i) == '(')
{
// Add null node
temp = null;
stack.push(temp, 0);
i += 1;
}
else if (str(i) == ')')
{
if (stack.is_size() < 2)
{
// not a valid parent child relation
return null;
}
position = 0;
// Reset the value of parent and child node
child = null;
parent = null;
if (stack.is_empty() == false)
{
// Get child node
child = stack.peek();
stack.pop();
}
if (stack.is_empty() == false)
{
// Get parent node
parent = stack.peek();
position = stack.top.indicator;
stack.pop();
}
if (parent != null)
{
// connect parent to child node
if (position == 0)
{
// Add node in left side
parent.left = child;
position = 1;
}
else if (position == 1)
{
// Add node in right side
parent.right = child;
position = 2;
}
else
{
// Tree exist More than 2 child nodes
// example x(1)(2)(3) x is parent
print("\n More than 2 child of node " + parent.data + "\n");
return null;
}
stack.push(parent, position);
}
i += 1;
}
else if (str(i) >= '1' && str(i) <= '9')
{
num = 0;
// Collect node value
while (i < n && str(i) != '(' && str(i) != ')')
{
num = (num * 10) + (str(i) - '0');
i += 1;
}
// Get new tree node
temp = new Node(num);
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
if (auxiliary == null)
{
// When stack top node element is empty then add new node to this location
stack.top.element = temp;
}
else
{
// Add new node in tree
stack.push(temp, 0);
}
}
else
{
// When stack is empty, then add first node
stack.push(temp, 0);
}
}
else
{
// When not a valid expression
print("\n Invalid Expression \n");
return null;
}
}
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
stack.pop();
return auxiliary;
}
else
{
return null;
}
}
// handles the request of construct binary tree
def make_tree(str: String, n: Int): Unit = {
if (n <= 0)
{
// Invalid sequence
this.root = null;
}
else
{
this.root = construct_tree(str, n);
}
}
// Handles the request of display the element of tree
def print_tree(): Unit = {
if (this.root == null)
{
print("\n Empty Tree\n");
return;
}
print("\n Preorder : ");
print_preorder(root);
print("\n Inorder : ");
print_inorder(root);
print("\n Postorder : ");
print_postorder(root);
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create tree object
var tree: BinaryTree = new BinaryTree();
// string expression
var str: String = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
// Get the size
var size: Int = str.length();
tree.make_tree(str, size);
//
// 16
// / \
// / \
// / \
// 7 8
// / \ / \
// 4 2 9 3
// \ \ /
// 6 1 15
// ----------------
// Resultant binary tree
//
tree.print_tree();
}
}
Output
Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))
Preorder : 16 7 4 6 2 8 9 1 3 15
Inorder : 4 6 7 2 16 9 1 8 15 3
Postorder : 6 4 2 7 1 9 15 3 8 16
// Swift 4 Program
// Construct tree from given string parenthesis expression
// Binary Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Stack Node
class StackNode
{
var element: Node? ;
var next: StackNode? ;
var indicator: Int;
init(_ element: Node? , _ indicator : Int)
{
self.element = element;
self.next = nil;
self.indicator = indicator;
}
}
// Define custom stack and its operation
class MyStack
{
var top: StackNode? ;
var length: Int;
init()
{
self.top = nil;
self.length = 0;
}
// Add a new element in stack
func push(_ element: Node? , _ indicator : Int)
{
// Make a new stack node
let new_node: StackNode? = StackNode(element, indicator);
if (new_node != nil)
{
new_node!.next = self.top;
self.top = new_node;
self.length += 1;
}
else
{
print("Memory overflow\n", terminator: "");
}
}
// remove a top element in stack
func pop()
{
if (self.top != nil)
{
self.top = self.top!.next;
self.length -= 1;
}
}
// check that whether stack is empty or not
func is_empty()->Bool
{
if (self.top != nil)
{
return false;
}
else
{
return true;
}
}
func is_size()->Int
{
return self.length;
}
// Used to get top element of stack
func peek()->Node?
{
if (self.top != nil)
{
return self.top!.element;
}
else
{
return nil;
}
}
}
// Define Binary Tree
class BinaryTree
{
var root: Node? ;
var location: Int;
init()
{
// Set root of tree
self.root = nil;
self.location = 0;
}
// Display inorder elements
func print_inorder(_ node: Node? )
{
if (node != nil)
{
self.print_inorder(node!.left);
// Print node value
print(" ", node!.data, terminator: "");
self.print_inorder(node!.right);
}
}
// Display pre order elements
func print_preorder(_ node: Node? )
{
if (node != nil)
{
// Print node value
print(" ", node!.data, terminator: "");
self.print_preorder(node!.left);
self.print_preorder(node!.right);
}
}
// Display postorder elements
func print_postorder(_ node: Node? )
{
if (node != nil)
{
self.print_postorder(node!.left);
self.print_postorder(node!.right);
// Print node value
print(" ", node!.data, terminator: "");
}
}
// Constructing a binary tree from string
// 1) expression can be contains positive number example (1,44,2324,55 etc)
// 2) Expression contains parentheses which is indicates is left and right child
// Example 1 : () null child, other (4) child with node 4
func construct_tree(_ str: [Character], _ n: Int)->Node?
{
// Define loop controlling variable
var i: Int = 0;
// Define stack variable
let stack: MyStack = MyStack();
// Define some useful Tree node variables
var auxiliary: Node? = nil;
var temp: Node? = nil;
var child: Node? = nil;
var parent: Node? = nil;
// Define some auxiliary variables
var num: Int = 0;
var position: Int = 0;
// Construct tree
while (i < n)
{
if (str[i] == "(")
{
// Add null node
temp = nil;
stack.push(temp, 0);
i += 1;
}
else if (str[i] == ")")
{
if (stack.is_size() < 2)
{
// not a valid parent child relation
return nil;
}
position = 0;
// Reset the value of parent and child node
child = nil;
parent = nil;
if (stack.is_empty() == false)
{
// Get child node
child = stack.peek();
stack.pop();
}
if (stack.is_empty() == false)
{
// Get parent node
parent = stack.peek();
position = stack.top!.indicator;
stack.pop();
}
if (parent != nil)
{
// connect parent to child node
if (position == 0)
{
// Add node in left side
parent!.left = child;
position = 1;
}
else if (position == 1)
{
// Add node in right side
parent!.right = child;
position = 2;
}
else
{
// Tree exist More than 2 child nodes
// example x(1)(2)(3) x is parent
print("\n More than 2 child of node ", parent!.data ,"\n", terminator: "");
return nil;
}
stack.push(parent, position);
}
i += 1;
}
else if (str[i] >= "1" && str[i] <= "9")
{
num = 0;
var ch : String = " " ;
// Collect node value
while (i < n && str[i] != "(" && str[i] != ")")
{
ch = String(str[i]);
num = (num * 10) + Int(UnicodeScalar(ch)!.value - UnicodeScalar("0")!.value);
i += 1;
}
// Get new tree node
temp = Node(num);
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
if (auxiliary == nil)
{
// When stack top node element is empty then add new node to this location
stack.top!.element = temp;
}
else
{
// Add new node in tree
stack.push(temp, 0);
}
}
else
{
// When stack is empty, then add first node
stack.push(temp, 0);
}
}
else
{
// When not a valid expression
print("\n Invalid Expression \n", terminator: "");
return nil;
}
}
if (stack.is_empty() == false)
{
auxiliary = stack.peek();
stack.pop();
return auxiliary;
}
else
{
return nil;
}
}
// handles the request of construct binary tree
func make_tree(_ str: String, _ n: Int)
{
if (n <= 0)
{
// Invalid sequence
self.root = nil;
}
else
{
// Display given expression
print("\n Expression : ", str );
self.root = self.construct_tree(Array(str), n);
}
}
// Handles the request of display the element of tree
func print_tree()
{
if (self.root == nil)
{
print("\n Empty Tree\n", terminator: "");
return;
}
print("\n Preorder : ", terminator: "");
self.print_preorder(self.root);
print("\n Inorder : ", terminator: "");
self.print_inorder(self.root);
print("\n Postorder : ", terminator: "");
self.print_postorder(self.root);
print("\n", terminator: "");
}
}
func main()
{
// Create tree object
let tree: BinaryTree = BinaryTree();
// string expression
let str: String = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
// Get the size
let size: Int = str.count;
tree.make_tree(str, size);
//
// 16
// / \
// / \
// / \
// 7 8
// / \ / \
// 4 2 9 3
// \ \ /
// 6 1 15
// ----------------
// Resultant binary tree
//
tree.print_tree();
}
main();
Output
Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))
Preorder : 16 7 4 6 2 8 9 1 3 15
Inorder : 4 6 7 2 16 9 1 8 15 3
Postorder : 6 4 2 7 1 9 15 3 8 16
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment