Implement Leftist Tree
Here given code implementation process.
/*
C Program
Implement Leftist Tree
*/
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
int data;
int rank;
struct TreeNode *left;
struct TreeNode *right;
};
// Define structure of Leftist Tree
struct LeftistTree
{
struct TreeNode *root;
};
// Create new tree
struct LeftistTree *new_tree()
{
// Create dynamic node
struct LeftistTree *tree = (struct LeftistTree *) malloc(sizeof(struct LeftistTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
//return new tree
return tree;
}
// returns a new node of tree
struct TreeNode *new_node(int data)
{
// Create dynamic node
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
//Set data and pointer values
node->data = data;
node->rank = 0;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return node;
}
//Swap the child of given node
void swap_child(struct TreeNode *parent)
{
if (parent != NULL)
{
struct TreeNode *temp = parent->left;
parent->left = parent->right;
parent->right = temp;
}
}
//Merge nodes of given two leftist tree
struct TreeNode *merge_node(struct TreeNode *n1, struct TreeNode *n2)
{
if (n1 == NULL)
{
return n2;
}
if (n2 == NULL)
{
return n1;
}
if (n1->data < n2->data)
{
// When need to Modification in first leftist tree
if (n1->left == NULL)
{
//When left subtree null
n1->left = n2;
}
else
{
n1->right = merge_node(n1->right, n2);
if (n1->left->rank < n1->right->rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n1);
}
}
if (n1->right != NULL)
{
// Update the current path node rank
n1->rank = n1->right->rank + 1;
}
return n1;
}
else
{
// When need to Modification in second leftist tree
if (n2->left == NULL)
{
//When left subtree null
n2->left = n1;
}
else
{
n2->right = merge_node(n2->right, n1);
if (n2->left->rank < n2->right->rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n2);
}
}
if (n2->right != NULL)
{
// Update the current path node rank
n2->rank = n2->right->rank + 1;
}
return n2;
}
}
// Handles the request of adding a new node in leftist tree
void add_node(struct LeftistTree *tree, int data)
{
struct TreeNode *node = new_node(data);
tree->root = merge_node(node, tree->root);
}
void inorder(struct TreeNode *node)
{
if (node != NULL)
{
inorder(node->left);
//Print node value
printf(" %d", node->data);
inorder(node->right);
}
}
void preorder(struct TreeNode *node)
{
if (node != NULL)
{
//Print node value
printf(" %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
void postorder(struct TreeNode *node)
{
if (node != NULL)
{
postorder(node->left);
postorder(node->right);
//Print node value
printf(" %d", node->data);
}
}
// Handles the request of view tree elements
void print_tree(struct LeftistTree *tree)
{
if (tree->root != NULL)
{
// Display tree elements
printf("\n Preorder : ");
preorder(tree->root);
printf("\n Inorder : ");
inorder(tree->root);
printf("\n Postorder : ");
postorder(tree->root);
printf("\n");
}
else
{
printf("\n Empty Tree");
}
}
//Handles the request to merge two trees
void merge_tree(struct LeftistTree *tree1, struct LeftistTree *tree2)
{
tree1->root = merge_node(tree1->root, tree2->root);
tree2->root = NULL;
}
void delete_min(struct LeftistTree *tree)
{
if (tree->root == NULL)
{
printf("\nEmpty Tree\n");
}
else
{
tree->root = merge_node(tree->root->left, tree->root->right);
}
}
//Print Min element of tree
void min_element(struct LeftistTree *tree)
{
if (tree->root == NULL)
{
printf("\nEmpty Tree\n");
}
else
{
printf("\n Min Element : %d \n", tree->root->data);
}
}
int main()
{
struct LeftistTree *tree1 = new_tree();
// Added nodes
add_node(tree1, 6);
add_node(tree1, 9);
add_node(tree1, 11);
add_node(tree1, 3);
add_node(tree1, 2);
add_node(tree1, 45);
add_node(tree1, 70);
add_node(tree1, 4);
add_node(tree1, 13);
/*
2
/ \
/ \
4 3
/ \ /
45 13 6
/ / \
70 9 11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
print_tree(tree1);
struct LeftistTree *tree2 = new_tree();
// Put tree nodes
add_node(tree2, 5);
add_node(tree2, 9);
add_node(tree2, 41);
add_node(tree2, 8);
add_node(tree2, 12);
add_node(tree2, 50);
add_node(tree2, 100);
add_node(tree2, 120);
add_node(tree2, 150);
/*
5
/ \
/ \
8 9
/ \ / \
41 12 100 50
/ \
120 150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------
*/
print_tree(tree2);
printf("\n Merge Two Tree \n");
merge_tree(tree1, tree2);
//After merge two tree
printf("\n Tree 1");
print_tree(tree1);
printf("\n Tree 2");
print_tree(tree2);
printf("\n\n Delete Min ");
min_element(tree1);
delete_min(tree1);
print_tree(tree1);
return 0;
}Output
Preorder : 2 4 45 70 13 3 6 9 11
Inorder : 70 45 4 13 2 9 6 11 3
Postorder : 70 45 13 4 9 11 6 3 2
Preorder : 5 8 41 12 9 100 120 150 50
Inorder : 41 8 12 5 120 100 150 9 50
Postorder : 41 12 8 120 150 100 50 9 5
Merge Two Tree
Tree 1
Preorder : 2 3 5 8 41 12 9 100 120 150 50 6 9 11 4 45 70 13
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 11 2 70 45 4 13
Postorder : 41 12 8 120 150 100 50 9 5 9 11 6 3 70 45 13 4 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 5 8 41 12 9 100 120 150 50 4 6 9 11 13 45 70
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 13 11 4 70 45
Postorder : 41 12 8 120 150 100 50 9 5 9 13 11 6 70 45 4 3/*
Java Program
Implement Leftist Tree
*/
// Tree Node
class TreeNode
{
public int data;
public int rank;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.rank = 0;
this.left = null;
this.right = null;
}
}
// Leftist Tree
public class LeftistTree
{
public TreeNode root;
public LeftistTree()
{
this.root = null;
}
//Swap the child of given node
public void swap_child(TreeNode parent)
{
if (parent != null)
{
TreeNode temp = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
//Merge nodes of given two leftist tree
public TreeNode merge_node(TreeNode n1, TreeNode n2)
{
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
// When need to Modification in first leftist tree
if (n1.left == null)
{
//When left subtree null
n1.left = n2;
}
else
{
n1.right = merge_node(n1.right, n2);
if (n1.left.rank < n1.right.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n1);
}
}
if (n1.right != null)
{
// Update the current path node rank
n1.rank = n1.right.rank + 1;
}
return n1;
}
else
{
// When need to Modification in second leftist tree
if (n2.left == null)
{
//When left subtree null
n2.left = n1;
}
else
{
n2.right = merge_node(n2.right, n1);
if (n2.left.rank < n2.right.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n2);
}
}
if (n2.right != null)
{
// Update the current path node rank
n2.rank = n2.right.rank + 1;
}
return n2;
}
}
// Handles the request of adding a new node in leftist tree
public void add_node(int data)
{
TreeNode node = new TreeNode(data);
this.root = merge_node(node, this.root);
}
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
//Print node value
System.out.print(" " + node.data );
inorder(node.right);
}
}
public void preorder(TreeNode node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data );
preorder(node.left);
preorder(node.right);
}
}
public void postorder(TreeNode node)
{
if (node != null)
{
postorder(node.left);
postorder(node.right);
//Print node value
System.out.print(" " + node.data );
}
}
// Handles the request of view tree elements
public void print_tree()
{
if (this.root != null)
{
// Display tree elements
System.out.print("\n Preorder : ");
preorder(this.root);
System.out.print("\n Inorder : ");
inorder(this.root);
System.out.print("\n Postorder : ");
postorder(this.root);
System.out.print("\n");
}
else
{
System.out.print("\n Empty Tree");
}
}
//Handles the request to merge two trees
public void merge_tree(LeftistTree tree2)
{
this.root = merge_node(this.root, tree2.root);
tree2.root = null;
}
public void delete_min()
{
if (this.root == null)
{
System.out.print("\nEmpty Tree\n");
}
else
{
this.root = merge_node(this.root.left, this.root.right);
}
}
//Print Min element of tree
public void min_element()
{
if (this.root == null)
{
System.out.print("\nEmpty Tree\n");
}
else
{
System.out.print("\n Min Element : " + this.root.data + " \n");
}
}
public static void main(String[] args)
{
LeftistTree tree1 = new LeftistTree();
LeftistTree tree2 = new LeftistTree();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
4 3
/ \ /
45 13 6
/ / \
70 9 11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
8 9
/ \ / \
41 12 100 50
/ \
120 150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------
*/
tree2.print_tree();
System.out.print("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
//After merge two tree
System.out.print("\n Tree 1");
tree1.print_tree();
System.out.print("\n Tree 2");
tree2.print_tree();
System.out.print("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
}
}Output
Preorder : 2 4 45 70 13 3 6 9 11
Inorder : 70 45 4 13 2 9 6 11 3
Postorder : 70 45 13 4 9 11 6 3 2
Preorder : 5 8 41 12 9 100 120 150 50
Inorder : 41 8 12 5 120 100 150 9 50
Postorder : 41 12 8 120 150 100 50 9 5
Merge Two Tree
Tree 1
Preorder : 2 3 5 8 41 12 9 100 120 150 50 6 9 11 4 45 70 13
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 11 2 70 45 4 13
Postorder : 41 12 8 120 150 100 50 9 5 9 11 6 3 70 45 13 4 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 5 8 41 12 9 100 120 150 50 4 6 9 11 13 45 70
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 13 11 4 70 45
Postorder : 41 12 8 120 150 100 50 9 5 9 13 11 6 70 45 4 3// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Implement Leftist Tree
*/
// Tree Node
class TreeNode
{
public:
int data;
int rank;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->rank = 0;
this->left = NULL;
this->right = NULL;
}
};
// Leftist Tree
class LeftistTree
{
public:
TreeNode *root;
LeftistTree()
{
this->root = NULL;
}
// Swap the child of given node
void swap_child(TreeNode *parent)
{
if (parent != NULL)
{
TreeNode *temp = parent->left;
parent->left = parent->right;
parent->right = temp;
}
}
// Merge nodes of given two leftist tree
TreeNode *merge_node(TreeNode *n1, TreeNode *n2)
{
if (n1 == NULL)
{
return n2;
}
if (n2 == NULL)
{
return n1;
}
if (n1->data < n2->data)
{
// When need to Modification in first leftist tree
if (n1->left == NULL)
{
// When left subtree null
n1->left = n2;
}
else
{
n1->right = this->merge_node(n1->right, n2);
if (n1->left->rank < n1->right->rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
this->swap_child(n1);
}
}
if (n1->right != NULL)
{
// Update the current path node rank
n1->rank = n1->right->rank + 1;
}
return n1;
}
else
{
// When need to Modification in second leftist tree
if (n2->left == NULL)
{
// When left subtree null
n2->left = n1;
}
else
{
n2->right = this->merge_node(n2->right, n1);
if (n2->left->rank < n2->right->rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
this->swap_child(n2);
}
}
if (n2->right != NULL)
{
// Update the current path node rank
n2->rank = n2->right->rank + 1;
}
return n2;
}
}
// Handles the request of adding a new node in leftist tree
void add_node(int data)
{
TreeNode *node = new TreeNode(data);
this->root = this->merge_node(node, this->root);
}
void inorder(TreeNode *node)
{
if (node != NULL)
{
this->inorder(node->left);
// Print node value
cout << " " << node->data;
this->inorder(node->right);
}
}
void preorder(TreeNode *node)
{
if (node != NULL)
{
// Print node value
cout << " " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
void postorder(TreeNode *node)
{
if (node != NULL)
{
this->postorder(node->left);
this->postorder(node->right);
// Print node value
cout << " " << node->data;
}
}
// Handles the request of view tree elements
void print_tree()
{
if (this->root != NULL)
{
// Display tree elements
cout << "\n Preorder : ";
this->preorder(this->root);
cout << "\n Inorder : ";
this->inorder(this->root);
cout << "\n Postorder : ";
this->postorder(this->root);
cout << "\n";
}
else
{
cout << "\n Empty Tree";
}
}
// Handles the request to merge two trees
void merge_tree(LeftistTree tree2)
{
this->root = this->merge_node(this->root, tree2.root);
tree2.root = NULL;
}
void delete_min()
{
if (this->root == NULL)
{
cout << "\nEmpty Tree\n";
}
else
{
this->root = this->merge_node(this->root->left, this->root->right);
}
}
// Print Min element of tree
void min_element()
{
if (this->root == NULL)
{
cout << "\nEmpty Tree\n";
}
else
{
cout << "\n Min Element : " << this->root->data << " \n";
}
}
};
int main()
{
LeftistTree tree1 = LeftistTree();
LeftistTree tree2 = LeftistTree();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
4 3
/ \ /
45 13 6
/ / \
70 9 11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
8 9
/ \ / \
41 12 100 50
/ \
120 150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------
*/
tree2.print_tree();
cout << "\n Merge Two Tree \n";
tree1.merge_tree(tree2);
// After merge two tree
cout << "\n Tree 1";
tree1.print_tree();
cout << "\n Tree 2";
tree2.print_tree();
cout << "\n\n Delete Min ";
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
return 0;
}Output
Preorder : 2 4 45 70 13 3 6 9 11
Inorder : 70 45 4 13 2 9 6 11 3
Postorder : 70 45 13 4 9 11 6 3 2
Preorder : 5 8 41 12 9 100 120 150 50
Inorder : 41 8 12 5 120 100 150 9 50
Postorder : 41 12 8 120 150 100 50 9 5
Merge Two Tree
Tree 1
Preorder : 2 3 5 8 41 12 9 100 120 150 50 6 9 11 4 45 70 13
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 11 2 70 45 4 13
Postorder : 41 12 8 120 150 100 50 9 5 9 11 6 3 70 45 13 4 2
Tree 2
Preorder : 5 8 41 12 9 100 120 150 50
Inorder : 41 8 12 5 120 100 150 9 50
Postorder : 41 12 8 120 150 100 50 9 5
Delete Min
Min Element : 2
Preorder : 3 5 8 41 12 9 100 120 150 50 4 6 9 11 13 45 70
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 13 11 4 70 45
Postorder : 41 12 8 120 150 100 50 9 5 9 13 11 6 70 45 4 3// Include namespace system
using System;
/*
C# Program
Implement Leftist Tree
*/
// Tree Node
public class TreeNode
{
public int data;
public int rank;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.rank = 0;
this.left = null;
this.right = null;
}
}
// Leftist Tree
public class LeftistTree
{
public TreeNode root;
public LeftistTree()
{
this.root = null;
}
// Swap the child of given node
public void swap_child(TreeNode parent)
{
if (parent != null)
{
TreeNode temp = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
// Merge nodes of given two leftist tree
public TreeNode merge_node(TreeNode n1, TreeNode n2)
{
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
// When need to Modification in first leftist tree
if (n1.left == null)
{
// When left subtree null
n1.left = n2;
}
else
{
n1.right = merge_node(n1.right, n2);
if (n1.left.rank < n1.right.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n1);
}
}
if (n1.right != null)
{
// Update the current path node rank
n1.rank = n1.right.rank + 1;
}
return n1;
}
else
{
// When need to Modification in second leftist tree
if (n2.left == null)
{
// When left subtree null
n2.left = n1;
}
else
{
n2.right = merge_node(n2.right, n1);
if (n2.left.rank < n2.right.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n2);
}
}
if (n2.right != null)
{
// Update the current path node rank
n2.rank = n2.right.rank + 1;
}
return n2;
}
}
// Handles the request of adding a new node in leftist tree
public void add_node(int data)
{
TreeNode node = new TreeNode(data);
this.root = merge_node(node, this.root);
}
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
// Print node value
Console.Write(" " + node.data);
inorder(node.right);
}
}
public void preorder(TreeNode node)
{
if (node != null)
{
// Print node value
Console.Write(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
public void postorder(TreeNode node)
{
if (node != null)
{
postorder(node.left);
postorder(node.right);
// Print node value
Console.Write(" " + node.data);
}
}
// Handles the request of view tree elements
public void print_tree()
{
if (this.root != null)
{
// Display tree elements
Console.Write("\n Preorder : ");
preorder(this.root);
Console.Write("\n Inorder : ");
inorder(this.root);
Console.Write("\n Postorder : ");
postorder(this.root);
Console.Write("\n");
}
else
{
Console.Write("\n Empty Tree");
}
}
// Handles the request to merge two trees
public void merge_tree(LeftistTree tree2)
{
this.root = merge_node(this.root, tree2.root);
tree2.root = null;
}
public void delete_min()
{
if (this.root == null)
{
Console.Write("\nEmpty Tree\n");
}
else
{
this.root = merge_node(this.root.left, this.root.right);
}
}
// Print Min element of tree
public void min_element()
{
if (this.root == null)
{
Console.Write("\nEmpty Tree\n");
}
else
{
Console.Write("\n Min Element : " + this.root.data + " \n");
}
}
public static void Main(String[] args)
{
LeftistTree tree1 = new LeftistTree();
LeftistTree tree2 = new LeftistTree();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
4 3
/ \ /
45 13 6
/ / \
70 9 11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
8 9
/ \ / \
41 12 100 50
/ \
120 150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------
*/
tree2.print_tree();
Console.Write("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
// After merge two tree
Console.Write("\n Tree 1");
tree1.print_tree();
Console.Write("\n Tree 2");
tree2.print_tree();
Console.Write("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
}
}Output
Preorder : 2 4 45 70 13 3 6 9 11
Inorder : 70 45 4 13 2 9 6 11 3
Postorder : 70 45 13 4 9 11 6 3 2
Preorder : 5 8 41 12 9 100 120 150 50
Inorder : 41 8 12 5 120 100 150 9 50
Postorder : 41 12 8 120 150 100 50 9 5
Merge Two Tree
Tree 1
Preorder : 2 3 5 8 41 12 9 100 120 150 50 6 9 11 4 45 70 13
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 11 2 70 45 4 13
Postorder : 41 12 8 120 150 100 50 9 5 9 11 6 3 70 45 13 4 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 5 8 41 12 9 100 120 150 50 4 6 9 11 13 45 70
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 13 11 4 70 45
Postorder : 41 12 8 120 150 100 50 9 5 9 13 11 6 70 45 4 3<?php
/*
Php Program
Implement Leftist Tree
*/
// Tree Node
class TreeNode
{
public $data;
public $rank;
public $left;
public $right;
function __construct($data)
{
$this->data = $data;
$this->rank = 0;
$this->left = null;
$this->right = null;
}
}
// Leftist Tree
class LeftistTree
{
public $root;
function __construct()
{
$this->root = null;
}
// Swap the child of given node
public function swap_child($parent)
{
if ($parent != null)
{
$temp = $parent->left;
$parent->left = $parent->right;
$parent->right = $temp;
}
}
// Merge nodes of given two leftist tree
public function merge_node($n1, $n2)
{
if ($n1 == null)
{
return $n2;
}
if ($n2 == null)
{
return $n1;
}
if ($n1->data < $n2->data)
{
// When need to Modification in first leftist tree
if ($n1->left == null)
{
// When left subtree null
$n1->left = $n2;
}
else
{
$n1->right = $this->merge_node($n1->right, $n2);
if ($n1->left->rank < $n1->right->rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
$this->swap_child($n1);
}
}
if ($n1->right != null)
{
// Update the current path node rank
$n1->rank = $n1->right->rank + 1;
}
return $n1;
}
else
{
// When need to Modification in second leftist tree
if ($n2->left == null)
{
// When left subtree null
$n2->left = $n1;
}
else
{
$n2->right = $this->merge_node($n2->right, $n1);
if ($n2->left->rank < $n2->right->rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
$this->swap_child($n2);
}
}
if ($n2->right != null)
{
// Update the current path node rank
$n2->rank = $n2->right->rank + 1;
}
return $n2;
}
}
// Handles the request of adding a new node in leftist tree
public function add_node($data)
{
$node = new TreeNode($data);
$this->root = $this->merge_node($node, $this->root);
}
public function inorder($node)
{
if ($node != null)
{
$this->inorder($node->left);
// Print node value
echo " ". $node->data;
$this->inorder($node->right);
}
}
public function preorder($node)
{
if ($node != null)
{
// Print node value
echo " ". $node->data;
$this->preorder($node->left);
$this->preorder($node->right);
}
}
public function postorder($node)
{
if ($node != null)
{
$this->postorder($node->left);
$this->postorder($node->right);
// Print node value
echo " ". $node->data;
}
}
// Handles the request of view tree elements
public function print_tree()
{
if ($this->root != null)
{
// Display tree elements
echo "\n Preorder : ";
$this->preorder($this->root);
echo "\n Inorder : ";
$this->inorder($this->root);
echo "\n Postorder : ";
$this->postorder($this->root);
echo "\n";
}
else
{
echo "\n Empty Tree";
}
}
// Handles the request to merge two trees
public function merge_tree($tree2)
{
$this->root = $this->merge_node($this->root, $tree2->root);
$tree2->root = null;
}
public function delete_min()
{
if ($this->root == null)
{
echo "\nEmpty Tree\n";
}
else
{
$this->root = $this->merge_node($this->root->left, $this->root->right);
}
}
// Print Min element of tree
public function min_element()
{
if ($this->root == null)
{
echo "\nEmpty Tree\n";
}
else
{
echo "\n Min Element : ". $this->root->data ." \n";
}
}
}
function main()
{
$tree1 = new LeftistTree();
$tree2 = new LeftistTree();
// Added nodes
$tree1->add_node(6);
$tree1->add_node(9);
$tree1->add_node(11);
$tree1->add_node(3);
$tree1->add_node(2);
$tree1->add_node(45);
$tree1->add_node(70);
$tree1->add_node(4);
$tree1->add_node(13);
/*
2
/ \
/ \
4 3
/ \ /
45 13 6
/ / \
70 9 11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
$tree1->print_tree();
// Put tree nodes
$tree2->add_node(5);
$tree2->add_node(9);
$tree2->add_node(41);
$tree2->add_node(8);
$tree2->add_node(12);
$tree2->add_node(50);
$tree2->add_node(100);
$tree2->add_node(120);
$tree2->add_node(150);
/*
5
/ \
/ \
8 9
/ \ / \
41 12 100 50
/ \
120 150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------
*/
$tree2->print_tree();
echo "\n Merge Two Tree \n";
$tree1->merge_tree($tree2);
// After merge two tree
echo "\n Tree 1";
$tree1->print_tree();
echo "\n Tree 2";
$tree2->print_tree();
echo "\n\n Delete Min ";
$tree1->min_element();
$tree1->delete_min();
$tree1->print_tree();
}
main();Output
Preorder : 2 4 45 70 13 3 6 9 11
Inorder : 70 45 4 13 2 9 6 11 3
Postorder : 70 45 13 4 9 11 6 3 2
Preorder : 5 8 41 12 9 100 120 150 50
Inorder : 41 8 12 5 120 100 150 9 50
Postorder : 41 12 8 120 150 100 50 9 5
Merge Two Tree
Tree 1
Preorder : 2 3 5 8 41 12 9 100 120 150 50 6 9 11 4 45 70 13
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 11 2 70 45 4 13
Postorder : 41 12 8 120 150 100 50 9 5 9 11 6 3 70 45 13 4 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 5 8 41 12 9 100 120 150 50 4 6 9 11 13 45 70
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 13 11 4 70 45
Postorder : 41 12 8 120 150 100 50 9 5 9 13 11 6 70 45 4 3/*
Node Js Program
Implement Leftist Tree
*/
// Tree Node
class TreeNode
{
constructor(data)
{
this.data = data;
this.rank = 0;
this.left = null;
this.right = null;
}
}
// Leftist Tree
class LeftistTree
{
constructor()
{
this.root = null;
}
// Swap the child of given node
swap_child(parent)
{
if (parent != null)
{
var temp = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
// Merge nodes of given two leftist tree
merge_node(n1, n2)
{
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
// When need to Modification in first leftist tree
if (n1.left == null)
{
// When left subtree null
n1.left = n2;
}
else
{
n1.right = this.merge_node(n1.right, n2);
if (n1.left.rank < n1.right.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
this.swap_child(n1);
}
}
if (n1.right != null)
{
// Update the current path node rank
n1.rank = n1.right.rank + 1;
}
return n1;
}
else
{
// When need to Modification in second leftist tree
if (n2.left == null)
{
// When left subtree null
n2.left = n1;
}
else
{
n2.right = this.merge_node(n2.right, n1);
if (n2.left.rank < n2.right.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
this.swap_child(n2);
}
}
if (n2.right != null)
{
// Update the current path node rank
n2.rank = n2.right.rank + 1;
}
return n2;
}
}
// Handles the request of adding a new node in leftist tree
add_node(data)
{
var node = new TreeNode(data);
this.root = this.merge_node(node, this.root);
}
inorder(node)
{
if (node != null)
{
this.inorder(node.left);
// Print node value
process.stdout.write(" " + node.data);
this.inorder(node.right);
}
}
preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
postorder(node)
{
if (node != null)
{
this.postorder(node.left);
this.postorder(node.right);
// Print node value
process.stdout.write(" " + node.data);
}
}
// Handles the request of view tree elements
print_tree()
{
if (this.root != null)
{
// Display tree elements
process.stdout.write("\n Preorder : ");
this.preorder(this.root);
process.stdout.write("\n Inorder : ");
this.inorder(this.root);
process.stdout.write("\n Postorder : ");
this.postorder(this.root);
process.stdout.write("\n");
}
else
{
process.stdout.write("\n Empty Tree");
}
}
// Handles the request to merge two trees
merge_tree(tree2)
{
this.root = this.merge_node(this.root, tree2.root);
tree2.root = null;
}
delete_min()
{
if (this.root == null)
{
process.stdout.write("\nEmpty Tree\n");
}
else
{
this.root = this.merge_node(this.root.left, this.root.right);
}
}
// Print Min element of tree
min_element()
{
if (this.root == null)
{
process.stdout.write("\nEmpty Tree\n");
}
else
{
process.stdout.write("\n Min Element : " + this.root.data + " \n");
}
}
}
function main()
{
var tree1 = new LeftistTree();
var tree2 = new LeftistTree();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
4 3
/ \ /
45 13 6
/ / \
70 9 11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
8 9
/ \ / \
41 12 100 50
/ \
120 150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------
*/
tree2.print_tree();
process.stdout.write("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
// After merge two tree
process.stdout.write("\n Tree 1");
tree1.print_tree();
process.stdout.write("\n Tree 2");
tree2.print_tree();
process.stdout.write("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
}
main();Output
Preorder : 2 4 45 70 13 3 6 9 11
Inorder : 70 45 4 13 2 9 6 11 3
Postorder : 70 45 13 4 9 11 6 3 2
Preorder : 5 8 41 12 9 100 120 150 50
Inorder : 41 8 12 5 120 100 150 9 50
Postorder : 41 12 8 120 150 100 50 9 5
Merge Two Tree
Tree 1
Preorder : 2 3 5 8 41 12 9 100 120 150 50 6 9 11 4 45 70 13
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 11 2 70 45 4 13
Postorder : 41 12 8 120 150 100 50 9 5 9 11 6 3 70 45 13 4 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 5 8 41 12 9 100 120 150 50 4 6 9 11 13 45 70
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 13 11 4 70 45
Postorder : 41 12 8 120 150 100 50 9 5 9 13 11 6 70 45 4 3# Python 3 Program
# Implement Leftist Tree
# Tree Node
class TreeNode :
def __init__(self, data) :
self.data = data
self.rank = 0
self.left = None
self.right = None
# Leftist Tree
class LeftistTree :
def __init__(self) :
self.root = None
# Swap the child of given node
def swap_child(self, parent) :
if (parent != None) :
temp = parent.left
parent.left = parent.right
parent.right = temp
# Merge nodes of given two leftist tree
def merge_node(self, n1, n2) :
if (n1 == None) :
return n2
if (n2 == None) :
return n1
if (n1.data < n2.data) :
# When need to Modification in first leftist tree
if (n1.left == None) :
# When left subtree null
n1.left = n2
else :
n1.right = self.merge_node(n1.right, n2)
if (n1.left.rank < n1.right.rank) :
# When rank of left subtree is less than of right subtree.
# Then change the position of subtree
self.swap_child(n1)
if (n1.right != None) :
# Update the current path node rank
n1.rank = n1.right.rank + 1
return n1
else :
# When need to Modification in second leftist tree
if (n2.left == None) :
# When left subtree null
n2.left = n1
else :
n2.right = self.merge_node(n2.right, n1)
if (n2.left.rank < n2.right.rank) :
# When rank of left subtree is less than of right subtree.
# Then change the position of subtree
self.swap_child(n2)
if (n2.right != None) :
# Update the current path node rank
n2.rank = n2.right.rank + 1
return n2
# Handles the request of adding a new node in leftist tree
def add_node(self, data) :
node = TreeNode(data)
self.root = self.merge_node(node, self.root)
def inorder(self, node) :
if (node != None) :
self.inorder(node.left)
# Print node value
print(" ", node.data, end = "")
self.inorder(node.right)
def preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)
def postorder(self, node) :
if (node != None) :
self.postorder(node.left)
self.postorder(node.right)
# Print node value
print(" ", node.data, end = "")
# Handles the request of view tree elements
def print_tree(self) :
if (self.root != None) :
# Display tree elements
print("\n Preorder : ", end = "")
self.preorder(self.root)
print("\n Inorder : ", end = "")
self.inorder(self.root)
print("\n Postorder : ", end = "")
self.postorder(self.root)
print("\n", end = "")
else :
print("\n Empty Tree", end = "")
# Handles the request to merge two trees
def merge_tree(self, tree2) :
self.root = self.merge_node(self.root, tree2.root)
tree2.root = None
def delete_min(self) :
if (self.root == None) :
print("\nEmpty Tree\n", end = "")
else :
self.root = self.merge_node(self.root.left, self.root.right)
# Print Min element of tree
def min_element(self) :
if (self.root == None) :
print("\nEmpty Tree\n", end = "")
else :
print("\n Min Element : ", self.root.data ," \n", end = "")
def main() :
tree1 = LeftistTree()
tree2 = LeftistTree()
# Added nodes
tree1.add_node(6)
tree1.add_node(9)
tree1.add_node(11)
tree1.add_node(3)
tree1.add_node(2)
tree1.add_node(45)
tree1.add_node(70)
tree1.add_node(4)
tree1.add_node(13)
#
# 2
# / \
# / \
# 4 3
# / \ /
# 45 13 6
# / / \
# 70 9 11
# ----------------------------
# Constructing Leftist Tree
# ----------------------------
# Node [2], Rank (1)
# Node [4], Rank (1)
# Node [45], Rank (0)
# Node [70], Rank (0)
# Node [13], Rank (0)
# Node [3], Rank (0)
# Node [6], Rank (1)
# Node [9], Rank (0)
# Node [11], Rank (0)
# ----------------------------
#
tree1.print_tree()
# Put tree nodes
tree2.add_node(5)
tree2.add_node(9)
tree2.add_node(41)
tree2.add_node(8)
tree2.add_node(12)
tree2.add_node(50)
tree2.add_node(100)
tree2.add_node(120)
tree2.add_node(150)
#
# 5
# / \
# / \
# 8 9
# / \ / \
# 41 12 100 50
# / \
# 120 150
# ----------------------------
# Constructing Leftist Tree
# ----------------------------
# Node [5], Rank (2)
# Node [8], Rank (1)
# Node [41], Rank (0)
# Node [12], Rank (0)
# Node [9], Rank (1)
# Node [100], Rank (1)
# Node [120], Rank (0)
# Node [150], Rank (0)
# Node [50], Rank (0)
# ------------------
#
tree2.print_tree()
print("\n Merge Two Tree \n", end = "")
tree1.merge_tree(tree2)
# After merge two tree
print("\n Tree 1", end = "")
tree1.print_tree()
print("\n Tree 2", end = "")
tree2.print_tree()
print("\n\n Delete Min ", end = "")
tree1.min_element()
tree1.delete_min()
tree1.print_tree()
if __name__ == "__main__": main()Output
Preorder : 2 4 45 70 13 3 6 9 11
Inorder : 70 45 4 13 2 9 6 11 3
Postorder : 70 45 13 4 9 11 6 3 2
Preorder : 5 8 41 12 9 100 120 150 50
Inorder : 41 8 12 5 120 100 150 9 50
Postorder : 41 12 8 120 150 100 50 9 5
Merge Two Tree
Tree 1
Preorder : 2 3 5 8 41 12 9 100 120 150 50 6 9 11 4 45 70 13
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 11 2 70 45 4 13
Postorder : 41 12 8 120 150 100 50 9 5 9 11 6 3 70 45 13 4 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 5 8 41 12 9 100 120 150 50 4 6 9 11 13 45 70
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 13 11 4 70 45
Postorder : 41 12 8 120 150 100 50 9 5 9 13 11 6 70 45 4 3# Ruby Program
# Implement Leftist Tree
# Tree Node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :rank, :left, :right
attr_accessor :data, :rank, :left, :right
def initialize(data)
self.data = data
self.rank = 0
self.left = nil
self.right = nil
end
end
# Leftist Tree
class LeftistTree
# Define the accessor and reader of class LeftistTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
# Swap the child of given node
def swap_child(parent)
if (parent != nil)
temp = parent.left
parent.left = parent.right
parent.right = temp
end
end
# Merge nodes of given two leftist tree
def merge_node(n1, n2)
if (n1 == nil)
return n2
end
if (n2 == nil)
return n1
end
if (n1.data < n2.data)
# When need to Modification in first leftist tree
if (n1.left == nil)
# When left subtree null
n1.left = n2
else
n1.right = self.merge_node(n1.right, n2)
if (n1.left.rank < n1.right.rank)
# When rank of left subtree is less than of right subtree.
# Then change the position of subtree
self.swap_child(n1)
end
end
if (n1.right != nil)
# Update the current path node rank
n1.rank = n1.right.rank + 1
end
return n1
else
# When need to Modification in second leftist tree
if (n2.left == nil)
# When left subtree null
n2.left = n1
else
n2.right = self.merge_node(n2.right, n1)
if (n2.left.rank < n2.right.rank)
# When rank of left subtree is less than of right subtree.
# Then change the position of subtree
self.swap_child(n2)
end
end
if (n2.right != nil)
# Update the current path node rank
n2.rank = n2.right.rank + 1
end
return n2
end
end
# Handles the request of adding a new node in leftist tree
def add_node(data)
node = TreeNode.new(data)
self.root = self.merge_node(node, self.root)
end
def inorder(node)
if (node != nil)
self.inorder(node.left)
# Print node value
print(" ", node.data)
self.inorder(node.right)
end
end
def preorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end
end
def postorder(node)
if (node != nil)
self.postorder(node.left)
self.postorder(node.right)
# Print node value
print(" ", node.data)
end
end
# Handles the request of view tree elements
def print_tree()
if (self.root != nil)
# Display tree elements
print("\n Preorder : ")
self.preorder(self.root)
print("\n Inorder : ")
self.inorder(self.root)
print("\n Postorder : ")
self.postorder(self.root)
print("\n")
else
print("\n Empty Tree")
end
end
# Handles the request to merge two trees
def merge_tree(tree2)
self.root = self.merge_node(self.root, tree2.root)
tree2.root = nil
end
def delete_min()
if (self.root == nil)
print("\nEmpty Tree\n")
else
self.root = self.merge_node(self.root.left, self.root.right)
end
end
# Print Min element of tree
def min_element()
if (self.root == nil)
print("\nEmpty Tree\n")
else
print("\n Min Element : ", self.root.data ," \n")
end
end
end
def main()
tree1 = LeftistTree.new()
tree2 = LeftistTree.new()
# Added nodes
tree1.add_node(6)
tree1.add_node(9)
tree1.add_node(11)
tree1.add_node(3)
tree1.add_node(2)
tree1.add_node(45)
tree1.add_node(70)
tree1.add_node(4)
tree1.add_node(13)
#
# 2
# / \
# / \
# 4 3
# / \ /
# 45 13 6
# / / \
# 70 9 11
# ----------------------------
# Constructing Leftist Tree
# ----------------------------
# Node [2], Rank (1)
# Node [4], Rank (1)
# Node [45], Rank (0)
# Node [70], Rank (0)
# Node [13], Rank (0)
# Node [3], Rank (0)
# Node [6], Rank (1)
# Node [9], Rank (0)
# Node [11], Rank (0)
# ----------------------------
#
tree1.print_tree()
# Put tree nodes
tree2.add_node(5)
tree2.add_node(9)
tree2.add_node(41)
tree2.add_node(8)
tree2.add_node(12)
tree2.add_node(50)
tree2.add_node(100)
tree2.add_node(120)
tree2.add_node(150)
#
# 5
# / \
# / \
# 8 9
# / \ / \
# 41 12 100 50
# / \
# 120 150
# ----------------------------
# Constructing Leftist Tree
# ----------------------------
# Node [5], Rank (2)
# Node [8], Rank (1)
# Node [41], Rank (0)
# Node [12], Rank (0)
# Node [9], Rank (1)
# Node [100], Rank (1)
# Node [120], Rank (0)
# Node [150], Rank (0)
# Node [50], Rank (0)
# ------------------
#
tree2.print_tree()
print("\n Merge Two Tree \n")
tree1.merge_tree(tree2)
# After merge two tree
print("\n Tree 1")
tree1.print_tree()
print("\n Tree 2")
tree2.print_tree()
print("\n\n Delete Min ")
tree1.min_element()
tree1.delete_min()
tree1.print_tree()
end
main()Output
Preorder : 2 4 45 70 13 3 6 9 11
Inorder : 70 45 4 13 2 9 6 11 3
Postorder : 70 45 13 4 9 11 6 3 2
Preorder : 5 8 41 12 9 100 120 150 50
Inorder : 41 8 12 5 120 100 150 9 50
Postorder : 41 12 8 120 150 100 50 9 5
Merge Two Tree
Tree 1
Preorder : 2 3 5 8 41 12 9 100 120 150 50 6 9 11 4 45 70 13
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 11 2 70 45 4 13
Postorder : 41 12 8 120 150 100 50 9 5 9 11 6 3 70 45 13 4 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 5 8 41 12 9 100 120 150 50 4 6 9 11 13 45 70
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 13 11 4 70 45
Postorder : 41 12 8 120 150 100 50 9 5 9 13 11 6 70 45 4 3
/*
Scala Program
Implement Leftist Tree
*/
// Tree Node
class TreeNode(var data: Int , var rank: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, 0, null, null);
}
}
// Leftist Tree
class LeftistTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Swap the child of given node
def swap_child(parent: TreeNode): Unit = {
if (parent != null)
{
var temp: TreeNode = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
// Merge nodes of given two leftist tree
def merge_node(n1: TreeNode, n2: TreeNode): TreeNode = {
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
// When need to Modification in first leftist tree
if (n1.left == null)
{
// When left subtree null
n1.left = n2;
}
else
{
n1.right = merge_node(n1.right, n2);
if (n1.left.rank < n1.right.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n1);
}
}
if (n1.right != null)
{
// Update the current path node rank
n1.rank = n1.right.rank + 1;
}
return n1;
}
else
{
// When need to Modification in second leftist tree
if (n2.left == null)
{
// When left subtree null
n2.left = n1;
}
else
{
n2.right = merge_node(n2.right, n1);
if (n2.left.rank < n2.right.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n2);
}
}
if (n2.right != null)
{
// Update the current path node rank
n2.rank = n2.right.rank + 1;
}
return n2;
}
}
// Handles the request of adding a new node in leftist tree
def add_node(data: Int): Unit = {
var node: TreeNode = new TreeNode(data);
this.root = merge_node(node, this.root);
}
def inorder(node: TreeNode): Unit = {
if (node != null)
{
inorder(node.left);
// Print node value
print(" " + node.data);
inorder(node.right);
}
}
def preorder(node: TreeNode): Unit = {
if (node != null)
{
// Print node value
print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
def postorder(node: TreeNode): Unit = {
if (node != null)
{
postorder(node.left);
postorder(node.right);
// Print node value
print(" " + node.data);
}
}
// Handles the request of view tree elements
def print_tree(): Unit = {
if (this.root != null)
{
// Display tree elements
print("\n Preorder : ");
preorder(this.root);
print("\n Inorder : ");
inorder(this.root);
print("\n Postorder : ");
postorder(this.root);
print("\n");
}
else
{
print("\n Empty Tree");
}
}
// Handles the request to merge two trees
def merge_tree(tree2: LeftistTree): Unit = {
this.root = merge_node(this.root, tree2.root);
tree2.root = null;
}
def delete_min(): Unit = {
if (this.root == null)
{
print("\nEmpty Tree\n");
}
else
{
this.root = merge_node(this.root.left, this.root.right);
}
}
// Print Min element of tree
def min_element(): Unit = {
if (this.root == null)
{
print("\nEmpty Tree\n");
}
else
{
print("\n Min Element : " + this.root.data + " \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree1: LeftistTree = new LeftistTree();
var tree2: LeftistTree = new LeftistTree();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
4 3
/ \ /
45 13 6
/ / \
70 9 11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
8 9
/ \ / \
41 12 100 50
/ \
120 150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------
*/
tree2.print_tree();
print("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
// After merge two tree
print("\n Tree 1");
tree1.print_tree();
print("\n Tree 2");
tree2.print_tree();
print("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
}
}Output
Preorder : 2 4 45 70 13 3 6 9 11
Inorder : 70 45 4 13 2 9 6 11 3
Postorder : 70 45 13 4 9 11 6 3 2
Preorder : 5 8 41 12 9 100 120 150 50
Inorder : 41 8 12 5 120 100 150 9 50
Postorder : 41 12 8 120 150 100 50 9 5
Merge Two Tree
Tree 1
Preorder : 2 3 5 8 41 12 9 100 120 150 50 6 9 11 4 45 70 13
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 11 2 70 45 4 13
Postorder : 41 12 8 120 150 100 50 9 5 9 11 6 3 70 45 13 4 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 5 8 41 12 9 100 120 150 50 4 6 9 11 13 45 70
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 13 11 4 70 45
Postorder : 41 12 8 120 150 100 50 9 5 9 13 11 6 70 45 4 3/*
Swift 4 Program
Implement Leftist Tree
*/
// Tree Node
class TreeNode
{
var data: Int;
var rank: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
self.data = data;
self.rank = 0;
self.left = nil;
self.right = nil;
}
}
// Leftist Tree
class LeftistTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Swap the child of given node
func swap_child(_ parent: TreeNode? )
{
if (parent != nil)
{
let temp: TreeNode? = parent!.left;
parent!.left = parent!.right;
parent!.right = temp;
}
}
// Merge nodes of given two leftist tree
func merge_node(_ n1: TreeNode? , _ n2 : TreeNode? )->TreeNode?
{
if (n1 == nil)
{
return n2;
}
if (n2 == nil)
{
return n1;
}
if (n1!.data < n2!.data)
{
// When need to Modification in first leftist tree
if (n1!.left == nil)
{
// When left subtree null
n1!.left = n2;
}
else
{
n1!.right = self.merge_node(n1!.right, n2);
if (n1!.left!.rank < n1!.right!.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
self.swap_child(n1);
}
}
if (n1!.right != nil)
{
// Update the current path node rank
n1!.rank = n1!.right!.rank + 1;
}
return n1;
}
else
{
// When need to Modification in second leftist tree
if (n2!.left == nil)
{
// When left subtree null
n2!.left = n1;
}
else
{
n2!.right = self.merge_node(n2!.right, n1);
if (n2!.left!.rank < n2!.right!.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
self.swap_child(n2);
}
}
if (n2!.right != nil)
{
// Update the current path node rank
n2!.rank = n2!.right!.rank + 1;
}
return n2;
}
}
// Handles the request of adding a new node in leftist tree
func add_node(_ data: Int)
{
let node: TreeNode? = TreeNode(data);
self.root = self.merge_node(node, self.root);
}
func inorder(_ node: TreeNode? )
{
if (node != nil)
{
self.inorder(node!.left);
// Print node value
print(" ", node!.data, terminator: "");
self.inorder(node!.right);
}
}
func preorder(_ node: TreeNode? )
{
if (node != nil)
{
// Print node value
print(" ", node!.data, terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
func postorder(_ node: TreeNode? )
{
if (node != nil)
{
self.postorder(node!.left);
self.postorder(node!.right);
// Print node value
print(" ", node!.data, terminator: "");
}
}
// Handles the request of view tree elements
func print_tree()
{
if (self.root != nil)
{
// Display tree elements
print("\n Preorder : ", terminator: "");
self.preorder(self.root);
print("\n Inorder : ", terminator: "");
self.inorder(self.root);
print("\n Postorder : ", terminator: "");
self.postorder(self.root);
print("\n", terminator: "");
}
else
{
print("\n Empty Tree", terminator: "");
}
}
// Handles the request to merge two trees
func merge_tree(_ tree2: LeftistTree? )
{
self.root = self.merge_node(self.root, tree2!.root);
tree2!.root = nil;
}
func delete_min()
{
if (self.root == nil)
{
print("\nEmpty Tree\n", terminator: "");
}
else
{
self.root = self.merge_node(self.root!.left, self.root!.right);
}
}
// Print Min element of tree
func min_element()
{
if (self.root == nil)
{
print("\nEmpty Tree\n", terminator: "");
}
else
{
print("\n Min Element : ", self.root!.data ," \n", terminator: "");
}
}
}
func main()
{
let tree1: LeftistTree = LeftistTree();
let tree2: LeftistTree = LeftistTree();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
4 3
/ \ /
45 13 6
/ / \
70 9 11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
8 9
/ \ / \
41 12 100 50
/ \
120 150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------
*/
tree2.print_tree();
print("\n Merge Two Tree \n", terminator: "");
tree1.merge_tree(tree2);
// After merge two tree
print("\n Tree 1", terminator: "");
tree1.print_tree();
print("\n Tree 2", terminator: "");
tree2.print_tree();
print("\n\n Delete Min ", terminator: "");
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
}
main();Output
Preorder : 2 4 45 70 13 3 6 9 11
Inorder : 70 45 4 13 2 9 6 11 3
Postorder : 70 45 13 4 9 11 6 3 2
Preorder : 5 8 41 12 9 100 120 150 50
Inorder : 41 8 12 5 120 100 150 9 50
Postorder : 41 12 8 120 150 100 50 9 5
Merge Two Tree
Tree 1
Preorder : 2 3 5 8 41 12 9 100 120 150 50 6 9 11 4 45 70 13
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 11 2 70 45 4 13
Postorder : 41 12 8 120 150 100 50 9 5 9 11 6 3 70 45 13 4 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 5 8 41 12 9 100 120 150 50 4 6 9 11 13 45 70
Inorder : 41 8 12 5 120 100 150 9 50 3 9 6 13 11 4 70 45
Postorder : 41 12 8 120 150 100 50 9 5 9 13 11 6 70 45 4 3
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