Construct N Level Calkin-Wilf Tree

Here given code implementation process.
/*
C program for
Construct N Level Calkin-Wilf Tree
*/
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
int a;
int b;
struct TreeNode *left;
struct TreeNode *right;
};
struct CalkinWilfTree
{
struct TreeNode *root;
};
// Create new tree
struct CalkinWilfTree *newTree()
{
// Create dynamic node
struct CalkinWilfTree *tree =
(struct CalkinWilfTree *) malloc(sizeof(struct CalkinWilfTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
// return new tree
return tree;
}
// This is creating and return new node of tree
struct TreeNode *newNode(int a, int b)
{
// Create dynamic node
struct TreeNode *node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
node->a = a;
node->b = b;
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;
}
// This function are constructing a Calkin Wilf Tree
struct TreeNode *constructTree(int a, int b, int level)
{
if (level == 0)
{
return NULL;
}
struct TreeNode *node = newNode(a, b);
// build left and right subtree by using recursively
node->left = constructTree(a, a + b, level - 1);
node->right = constructTree(a + b, b, level - 1);
return node;
}
struct TreeNode *makeTree(int level)
{
return constructTree(1, 1, level);
}
void preorder(struct TreeNode *node)
{
if (node != NULL)
{
printf(" (%d/%d)", node->a, node->b);
preorder(node->left);
preorder(node->right);
}
}
int main(int argc, char
const *argv[])
{
int level = 3;
struct CalkinWilfTree *tree = newTree();
/*
Level : 3
-----------------------
(1/1)
/ \
/ \
(1/2) (2/1)
/ \ / \
(1/3) (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree->root = makeTree(level);
// Print tree node value
preorder(tree->root);
return 0;
}
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
// Java program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
public int a;
public int b;
public TreeNode left;
public TreeNode right;
public TreeNode(int a, int b)
{
// Set data value
this.a = a;
this.b = b;
// Set node value
this.left = null;
this.right = null;
}
}
public class CalkinWilfTree
{
// Tree Root
public TreeNode root;
public CalkinWilfTree()
{
this.root = null;
}
// This function are constructing a Calkin Wilf Tree
public TreeNode constructTree(int a, int b, int level)
{
if (level == 0)
{
return null;
}
TreeNode node = new TreeNode(a, b);
// build left and right subtree by using recursively
node.left = constructTree(a, a + b, level - 1);
node.right = constructTree(a + b, b, level - 1);
return node;
}
public void preorder(TreeNode node)
{
if (node != null)
{
System.out.print(" (" + node.a + "/" + node.b + ")");
preorder(node.left);
preorder(node.right);
}
}
public void makeTree(int level)
{
if (level > 0)
{
this.root = constructTree(1, 1, level);
}
}
public static void main(String[] args)
{
CalkinWilfTree tree = new CalkinWilfTree();
int level = 3;
/*
Level : 3
-----------------------
(1/1)
/ \
/ \
(1/2) (2/1)
/ \ / \
(1/3) (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}
}
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
public:
int a;
int b;
TreeNode *left;
TreeNode *right;
TreeNode(int a, int b)
{
// Set data value
this->a = a;
this->b = b;
// Set node value
this->left = NULL;
this->right = NULL;
}
};
class CalkinWilfTree
{
public:
// Tree Root
TreeNode *root;
CalkinWilfTree()
{
this->root = NULL;
}
// This function are constructing a Calkin Wilf Tree
TreeNode *constructTree(int a, int b, int level)
{
if (level == 0)
{
return NULL;
}
TreeNode *node = new TreeNode(a, b);
// build left and right subtree by using recursively
node->left = this->constructTree(a, a + b, level - 1);
node->right = this->constructTree(a + b, b, level - 1);
return node;
}
void preorder(TreeNode *node)
{
if (node != NULL)
{
cout << " (" << node->a << "/" << node->b << ")";
this->preorder(node->left);
this->preorder(node->right);
}
}
void makeTree(int level)
{
if (level > 0)
{
this->root = this->constructTree(1, 1, level);
}
}
};
int main()
{
CalkinWilfTree *tree = new CalkinWilfTree();
int level = 3;
/*
Level : 3
-----------------------
(1/1)
/ \
/ \
(1/2) (2/1)
/ \ / \
(1/3) (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree->makeTree(level);
// Print tree node value
tree->preorder(tree->root);
return 0;
}
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
// Include namespace system
using System;
// Csharp program for
// Construct N Level Calkin-Wilf Tree
public class TreeNode
{
public int a;
public int b;
public TreeNode left;
public TreeNode right;
public TreeNode(int a, int b)
{
// Set data value
this.a = a;
this.b = b;
// Set node value
this.left = null;
this.right = null;
}
}
public class CalkinWilfTree
{
// Tree Root
public TreeNode root;
public CalkinWilfTree()
{
this.root = null;
}
// This function are constructing a Calkin Wilf Tree
public TreeNode constructTree(int a, int b, int level)
{
if (level == 0)
{
return null;
}
TreeNode node = new TreeNode(a, b);
// build left and right subtree by using recursively
node.left = this.constructTree(a, a + b, level - 1);
node.right = this.constructTree(a + b, b, level - 1);
return node;
}
public void preorder(TreeNode node)
{
if (node != null)
{
Console.Write(" (" + node.a + "/" + node.b + ")");
this.preorder(node.left);
this.preorder(node.right);
}
}
public void makeTree(int level)
{
if (level > 0)
{
this.root = this.constructTree(1, 1, level);
}
}
public static void Main(String[] args)
{
CalkinWilfTree tree = new CalkinWilfTree();
int level = 3;
/*
Level : 3
-----------------------
(1/1)
/ \
/ \
(1/2) (2/1)
/ \ / \
(1/3) (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}
}
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
package main
import "fmt"
// Go program for
// Construct N Level Calkin-Wilf Tree
type TreeNode struct {
a int
b int
left * TreeNode
right * TreeNode
}
func getTreeNode(a int, b int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set data value
me.a = a
me.b = b
// Set node value
me.left = nil
me.right = nil
return me
}
type CalkinWilfTree struct {
// Tree Root
root * TreeNode
}
func getCalkinWilfTree() * CalkinWilfTree {
var me *CalkinWilfTree = &CalkinWilfTree {}
me.root = nil
return me
}
// This function are constructing a Calkin Wilf Tree
func(this *CalkinWilfTree) constructTree(a,
b, level int) * TreeNode {
if level == 0 {
return nil
}
var node * TreeNode = getTreeNode(a, b)
// build left and right subtree by using recursively
node.left = this.constructTree(a, a + b, level - 1)
node.right = this.constructTree(a + b, b, level - 1)
return node
}
func(this CalkinWilfTree) preorder(node * TreeNode) {
if node != nil {
fmt.Print(" (", node.a, "/", node.b, ")")
this.preorder(node.left)
this.preorder(node.right)
}
}
func(this *CalkinWilfTree) makeTree(level int) {
if level > 0 {
this.root = this.constructTree(1, 1, level)
}
}
func main() {
var tree * CalkinWilfTree = getCalkinWilfTree()
var level int = 3
/*
Level : 3
-----------------------
(1/1)
/ \
/ \
(1/2) (2/1)
/ \ / \
(1/3) (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level)
// Print tree node value
tree.preorder(tree.root)
}
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
<?php
// Php program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
public $a;
public $b;
public $left;
public $right;
public function __construct($a, $b)
{
// Set data value
$this->a = $a;
$this->b = $b;
// Set node value
$this->left = NULL;
$this->right = NULL;
}
}
class CalkinWilfTree
{
// Tree Root
public $root;
public function __construct()
{
$this->root = NULL;
}
// This function are constructing a Calkin Wilf Tree
public function constructTree($a, $b, $level)
{
if ($level == 0)
{
return NULL;
}
$node = new TreeNode($a, $b);
// build left and right subtree by using recursively
$node->left = $this->constructTree($a, $a + $b, $level - 1);
$node->right = $this->constructTree($a + $b, $b, $level - 1);
return $node;
}
public function preorder($node)
{
if ($node != NULL)
{
echo(" (".$node->a."/".$node->b.")");
$this->preorder($node->left);
$this->preorder($node->right);
}
}
public function makeTree($level)
{
if ($level > 0)
{
$this->root = $this->constructTree(1, 1, $level);
}
}
}
function main()
{
$tree = new CalkinWilfTree();
$level = 3;
/*
Level : 3
-----------------------
(1/1)
/ \
/ \
(1/2) (2/1)
/ \ / \
(1/3) (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
$tree->makeTree($level);
// Print tree node value
$tree->preorder($tree->root);
}
main();
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
// Node JS program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
constructor(a, b)
{
// Set data value
this.a = a;
this.b = b;
// Set node value
this.left = null;
this.right = null;
}
}
class CalkinWilfTree
{
constructor()
{
this.root = null;
}
// This function are constructing a Calkin Wilf Tree
constructTree(a, b, level)
{
if (level == 0)
{
return null;
}
var node = new TreeNode(a, b);
// build left and right subtree by using recursively
node.left = this.constructTree(a, a + b, level - 1);
node.right = this.constructTree(a + b, b, level - 1);
return node;
}
preorder(node)
{
if (node != null)
{
process.stdout.write(" (" + node.a + "/" + node.b + ")");
this.preorder(node.left);
this.preorder(node.right);
}
}
makeTree(level)
{
if (level > 0)
{
this.root = this.constructTree(1, 1, level);
}
}
}
function main()
{
var tree = new CalkinWilfTree();
var level = 3;
/*
Level : 3
-----------------------
(1/1)
/ \
/ \
(1/2) (2/1)
/ \ / \
(1/3) (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}
main();
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
# Python 3 program for
# Construct N Level Calkin-Wilf Tree
class TreeNode :
def __init__(self, a, b) :
# Set data value
self.a = a
self.b = b
# Set node value
self.left = None
self.right = None
class CalkinWilfTree :
# Tree Root
def __init__(self) :
self.root = None
# This function are constructing a Calkin Wilf Tree
def constructTree(self, a, b, level) :
if (level == 0) :
return None
node = TreeNode(a, b)
# build left and right subtree by using recursively
node.left = self.constructTree(a, a + b, level - 1)
node.right = self.constructTree(a + b, b, level - 1)
return node
def preorder(self, node) :
if (node != None) :
print(" (", node.a ,"/", node.b ,")", end = "",sep = "")
self.preorder(node.left)
self.preorder(node.right)
def makeTree(self, level) :
if (level > 0) :
self.root = self.constructTree(1, 1, level)
def main() :
tree = CalkinWilfTree()
level = 3
# Level : 3
# -----------------------
# (1/1)
# / \
# / \
# (1/2) (2/1)
# / \ / \
# (1/3) (3/2) (2/3) (3/1)
# -----------------------
# Calkin Wilf Tree
tree.makeTree(level)
# Print tree node value
tree.preorder(tree.root)
if __name__ == "__main__": main()
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
# Ruby program for
# Construct N Level Calkin-Wilf Tree
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :a, :b, :left, :right
attr_accessor :a, :b, :left, :right
def initialize(a, b)
# Set data value
self.a = a
self.b = b
# Set node value
self.left = nil
self.right = nil
end
end
class CalkinWilfTree
# Define the accessor and reader of class CalkinWilfTree
attr_reader :root
attr_accessor :root
# Tree Root
def initialize()
self.root = nil
end
# This function are constructing a Calkin Wilf Tree
def constructTree(a, b, level)
if (level == 0)
return nil
end
node = TreeNode.new(a, b)
# build left and right subtree by using recursively
node.left = self.constructTree(a, a + b, level - 1)
node.right = self.constructTree(a + b, b, level - 1)
return node
end
def preorder(node)
if (node != nil)
print(" (", node.a ,"/", node.b ,")")
self.preorder(node.left)
self.preorder(node.right)
end
end
def makeTree(level)
if (level > 0)
self.root = self.constructTree(1, 1, level)
end
end
end
def main()
tree = CalkinWilfTree.new()
level = 3
# Level : 3
# -----------------------
# (1/1)
# / \
# / \
# (1/2) (2/1)
# / \ / \
# (1/3) (3/2) (2/3) (3/1)
# -----------------------
# Calkin Wilf Tree
tree.makeTree(level)
# Print tree node value
tree.preorder(tree.root)
end
main()
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
// Scala program for
// Construct N Level Calkin-Wilf Tree
class TreeNode(var a: Int,
var b: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(a: Int, b: Int)
{
// Set data value
// Set node value
this(a, b, null, null)
}
}
class CalkinWilfTree(
// Tree Root
var root: TreeNode)
{
def this()
{
this(null)
}
// This function are constructing a Calkin Wilf Tree
def constructTree(a: Int, b: Int, level: Int): TreeNode = {
if (level == 0)
{
return null;
}
var node: TreeNode = new TreeNode(a, b);
// build left and right subtree by using recursively
node.left = constructTree(a, a + b, level - 1);
node.right = constructTree(a + b, b, level - 1);
return node;
}
def preorder(node: TreeNode): Unit = {
if (node != null)
{
print(" (" + node.a + "/" + node.b + ")");
preorder(node.left);
preorder(node.right);
}
}
def makeTree(level: Int): Unit = {
if (level > 0)
{
this.root = constructTree(1, 1, level);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: CalkinWilfTree = new CalkinWilfTree();
var level: Int = 3;
/*
Level : 3
-----------------------
(1/1)
/ \
/ \
(1/2) (2/1)
/ \ / \
(1/3) (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}
}
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
// Swift 4 program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
var a: Int;
var b: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ a: Int, _ b: Int)
{
// Set data value
self.a = a;
self.b = b;
// Set node value
self.left = nil;
self.right = nil;
}
}
class CalkinWilfTree
{
// Tree Root
var root: TreeNode? ;
init()
{
self.root = nil;
}
// This function are constructing a Calkin Wilf Tree
func constructTree(_ a: Int, _ b: Int, _ level: Int) -> TreeNode?
{
if (level == 0)
{
return nil;
}
let node: TreeNode = TreeNode(a, b);
// build left and right subtree by using recursively
node.left = self.constructTree(a, a + b, level - 1);
node.right = self.constructTree(a + b, b, level - 1);
return node;
}
func preorder(_ node: TreeNode? )
{
if (node != nil)
{
print(" (", node!.a ,"/", node!.b ,")", separator:"",
terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
func makeTree(_ level: Int)
{
if (level > 0)
{
self.root = self.constructTree(1, 1, level);
}
}
}
func main()
{
let tree: CalkinWilfTree = CalkinWilfTree();
let level: Int = 3;
/*
Level : 3
-----------------------
(1/1)
/ \
/ \
(1/2) (2/1)
/ \ / \
(1/3) (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}
main();
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
// Kotlin program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
var a: Int;
var b: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(a: Int, b: Int)
{
// Set data value
this.a = a;
this.b = b;
// Set node value
this.left = null;
this.right = null;
}
}
class CalkinWilfTree
{
// Tree Root
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// This function are constructing a Calkin Wilf Tree
fun constructTree(a: Int, b: Int, level: Int): TreeNode ?
{
if (level == 0)
{
return null;
}
val node: TreeNode = TreeNode(a, b);
// build left and right subtree by using recursively
node.left = this.constructTree(a, a + b, level - 1);
node.right = this.constructTree(a + b, b, level - 1);
return node;
}
fun preorder(node: TreeNode ? ): Unit
{
if (node != null)
{
print(" (" + node.a + "/" + node.b + ")");
this.preorder(node.left);
this.preorder(node.right);
}
}
fun makeTree(level: Int): Unit
{
if (level > 0)
{
this.root = this.constructTree(1, 1, level);
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: CalkinWilfTree = CalkinWilfTree();
val level: Int = 3;
/*
Level : 3
-----------------------
(1/1)
/ \
/ \
(1/2) (2/1)
/ \ / \
(1/3) (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}
Output
(1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)
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