top of page
Binary tree – C++ Program source code
 

  1. #include <iostream>

  2. #include <stdio  h>

  3. using namespace std;

  4.  

  5. class Node{

  6.  

  7. public:

  8.           int Value; // store the value of the Node

  9.           int index; // pointer to storing index of the tree

  10.           Node* leftChild; // pointer to the left Node

  11.           Node* rightChild; // pointer to the right Child

  12. };

  13. class BinaryTree{

  14. public:

  15.           Node* root; // pointer for root of the tree

  16.           int NumElements; // number of elements in the tree

  17.  

  18.           BinaryTree(){

  19.           root = NULL;

  20.                     NumElements = 0;

  21.           }

  22.           int add_left_child(Node* parent, int input);

  23.           int add_right_child(Node* parent, int input);

  24.           void traverse_inorder(Node* root);

  25.           void traverse_preorder(Node* root);

  26.           void traverse_postorder(Node* root);

  27.           Node* create_Tree(int inputArray[], int index, int arraySize);

  28.           Node* expand_Tree(Node* root, int elements[] , int ArraySize);

  29.           void get_inputOrder(Node* root, int inputs[]);

  30. };

  31.  

  32. Node* BinaryTree::create_Tree(int inputArray[],int index, int ArraySize){

  33.           this->NumElements = ArraySize; // store the number of elements in the array

  34.           Node* Root = new Node();

  35.           Root->Value = inputArray[index];

  36.           Root->index = index;

  37.           //if left child node  excised the index of array return null, thats leaf

  38.           if ((2 * index + 1) >= ArraySize){

  39.                     return Root;

  40.           }

  41.           //adding left child node  

  42.           if (add_left_child(Root, inputArray[2*index + 1])){

  43.                     Root->leftChild = create_Tree(inputArray, 2*index+1, ArraySize);

  44.           }

  45.           //if right child node excised the index of array return null, thats leaf

  46.           if ((2 * index + 2) >= ArraySize){

  47.                     return Root;

  48.           }

  49.           // adding right child node

  50.           if (add_right_child(Root, inputArray[2*index+2])){

  51.                     Root->rightChild = create_Tree(inputArray, (2 * index + 2),ArraySize);

  52.           }

  53.           return Root; // return the sub tree node pointer

  54. }

  55.  

  56. int BinaryTree::add_left_child(Node* parent, int inputValue){

  57.           Node*newLeaf;

  58.           if (parent->leftChild == NULL){

  59.                     newLeaf = new Node();

  60.                     parent->leftChild = newLeaf;

  61.                     newLeaf->Value = inputValue;

  62.                     return 1;

  63.           }

  64.           else{

  65.                     return -1;

  66.           }

  67. }

  68.  

  69. int BinaryTree::add_right_child(Node* parent, int inputValue){

  70.           Node* newLeaf;

  71.           if (parent->rightChild == NULL){

  72.                     newLeaf = new Node();

  73.                     parent->rightChild = newLeaf;

  74.                     newLeaf->Value = inputValue;

  75.                     return 1;

  76.         }

  77.           else{

  78.                     return -1;

  79.           }

  80. }

  81.  

  82. // pre- order traversal : *Node *Left Tree *Right Tree

  83. void BinaryTree::traverse_preorder(Node* root){

  84.           if (root)

  85.           {

  86.                     cout << root->Value << "  ";

  87.                     traverse_preorder(root->leftChild);

  88.                     traverse_preorder(root->rightChild);

  89.           }

  90. }

  91.  

  92. //post order Travers: Left Tree *Right sub Tree * Node

  93. void BinaryTree::traverse_postorder(Node* root){

  94.           if (root)

  95.           {

  96.                     traverse_postorder(root->leftChild);

  97.                     traverse_postorder(root->rightChild);

  98.                     cout << root->Value << " ";

  99.           }

  100. }

  101.  

  102. //  In-order Travesal : *Left Tree *Node  *Right Tree

  103. void BinaryTree::traverse_inorder(Node* root){

  104.           if (root ){

  105.                     traverse_inorder(root->leftChild);

  106.                     cout << root->Value << " ";

  107.                     traverse_inorder(root->rightChild);

  108.           }

  109. }

  110.  

  111. // to expand methord

  112. void BinaryTree::get_inputOrder(Node* root , int inputs[]){

  113.           if (root)

  114.           {

  115.                     inputs[root->index] = root->Value;

  116.                     get_inputOrder(root->leftChild, inputs);

  117.                     get_inputOrder(root->rightChild, inputs);

  118.           }

  119. }

  120.  

  121. Node* BinaryTree::expand_Tree(Node* root, int elements[] ,int ArraySize){

  122.           int allElements = this->NumElements + ArraySize;

  123.           int NewArray[12]; //  int allElement should be the array size   but in V  S   it consider as not constant value   therefore i had to set it manually

  124.           this->get_inputOrder(root, NewArray); // get all the elements in the Tree and put in to array

  125.           int j = 0;

  126.           for (int i = 8; i < allElements; i++){

  127.                      NewArray[i] = elements[j];

  128.                     j++;

  129.           }

  130.           return create_Tree(NewArray,0,allElements) ; // all elemtment put in to the one new aray and create new tree and return the root

  131. }

  132.  

  133.                       }

  134.                     return add_value(root->leftChild, newvalue);

  135.           }

  136.           else{

  137.                     if (root->rightChild == NULL){

  138.                               Node* newNode = new Node;

  139.                               newNode->leftChild = NULL;

  140.                               newNode->rightChild = NULL;

  141.                               newNode->Value = newvalue;

  142.                               root->rightChild = newNode;

  143.                               return 1;

  144.           }

  145.           return add_value(root->rightChild, newvalue);

  146.           }

  147. }

  148.  

  149. int main(){

  150.         BinaryTree *binaryTree = new BinaryTree;

  151.         cout <<"Create tree[1,45,23,33,25,53,54,11]\n"<< endl;

  152.         int array[8] = { 1, 45, 23, 33, 25, 53, 54,11 };

  153.         Node* Root = binaryTree->create_Tree(array, 0,8);

  154.         cout << "InOrderTraversal of Tree :  " << endl;

  155.         binaryTree->traverse_inorder(Root);

  156.         cout << "" << endl;

  157.         cout << "pre- order traversal : " << endl;

  158.         binaryTree->traverse_preorder(Root);

  159.         cout << "" << endl;

  160.         cout << "post order Traversal :" << endl;

  161.         binaryTree->traverse_postorder(Root);

  162.         cout << "" << endl;

  163.         cout << "\n \n" << endl;

  164.         cout << "Expand the same tree [3,22,7,64]\n" << endl;

  165.         int expand[] = { 3, 22, 7, 64 };

  166.         Root =  binaryTree->expand_Tree(Root, expand, 4);

  167.         cout << "InOrderTraversal of Tree : " << endl;

  168.         binaryTree->traverse_inorder(Root);

  169.         cout << "" << endl;

  170.         cout << "pre- order traversal :" << endl;

  171.         binaryTree->traverse_preorder(Root);

  172.         cout << "" << endl;

  173.         cout << "post order Traversal :" << endl;

  174.         binaryTree->traverse_postorder(Root);

  175.         cout << "" << endl;

  176.         cout << "\n \n" << endl;

  177.         return 0;

  178. }   

 

Anchor 5
Binary tree - java Program source code

 

 

  1. package Binary_tree;

  2.  

  3. /**

  4.  *

  5.  * @author CSE Helper

  6.  */

  7.  

  8. class Node{

  9.         public Node leftChild;

  10.         public Node rightChild;

  11.         public int value;

  12.         public int index;

  13. }

  14. public class Binary_Tree {

  15.         private Node root;

  16.         private int numElements;

  17.         private int  elements[];

  18.  

  19.         public Binary_Tree() {

  20.                 root = null;

  21.                 numElements = 0;

  22.         }

  23.         boolean add_left_child(Node parent, int input){

  24.                 Node newLeaf;

  25.                 if (parent  leftChild == null){

  26.                         newLeaf = new Node();

  27.                         parent  leftChild = newLeaf;

  28.                         newLeaf  value = input;

  29.                         return true;

  30.                 }else{

  31.                         return false;

  32.                 }

  33.         }

  34.         boolean add_right_child(Node parent , int input){

  35.                 Node newLeaf;

  36.                 if (parent  rightChild == null){

  37.                         newLeaf = new Node();

  38.                         parent  rightChild = newLeaf;

  39.                         newLeaf  value = input;

  40.                         return true;

  41.                 }else{

  42.                         return false;

  43.                 }

  44.         }

  45.         Node create_Tree(int inputArray[], int index, int arraySize){

  46.                 numElements = arraySize; // store the number of elements in the array

  47.                 elements = inputArray;

  48.                 Node Root = new Node();

  49.                 Root  value = inputArray[index];

  50.                 Root  index = index;

  51.                 //if left child node  excised the index of array return null, thats leaf

  52.                 if ((2 * index + 1) >= arraySize){

  53.                         return Root;

  54.                 }

  55.                 //adding left child node 

  56.                 if (add_left_child(Root, inputArray[2 * index + 1])){

  57.                          Root  leftChild = create_Tree(inputArray, 2 * index + 1 , arraySize);

  58.                 }

  59.                 //if right child node excised the index of array return null, thats leaf

  60.                 if ((2 * index + 2) >= arraySize){

  61.                          return Root;

  62.                 }

  63.                 // adding right child node

  64.                 if (add_right_child(Root, inputArray[2 * index + 2])){

  65.                         Root  rightChild = create_Tree(inputArray, (2 * index + 2),arraySize);

  66.                  }

  67.                 return Root; // return the sub tree node pointer

  68.         }

  69.         void traverse_inorder(Node root){

  70.                 if (root != null ){

  71.                         traverse_inorder(root  leftChild);

  72.                         System  out  print( root  value + "  ");

  73.                         traverse_inorder(root  rightChild);

  74.                 }

  75.         }

  76.         void traverse_preorder(Node root){

  77.                 if (root != null)

  78.                 {        System  out  print( root  value + "  ");

  79.                         traverse_preorder(root  leftChild);

  80.                         traverse_preorder(root  rightChild);

  81.                 }

  82.         }

  83.         void traverse_postorder(Node root){

  84.                  if (root != null)

  85.                 {        traverse_postorder(root  leftChild);

  86.                         traverse_postorder(root  rightChild);

  87.                         System  out  print( root  value + "  ");

  88.                 }

  89.         }

  90.         Node expand_Tree(Node root, int elements[] , int ArraySize){

  91.                 int allElements = numElements + ArraySize;

  92.         //  int allElement should be the array size   but in V  S   it consider as not constant value   therefore i had to set it manually

  93.                 int NewArray[] = new int[allElements];

  94.                 // get all the elements in the Tree and put in to array

  95.                 get_inputOrder(root, this  elements);

  96.                 int j = 0;

  97.                 for (int i = 8; i < allElements; i++){

  98.                         NewArray[i] = elements[j];

  99.                         j++;

  100.                 }

  101.                 //add previous tree values to new array

  102.                 for(int i = 0 ; i< numElements ; i++){

  103.                         NewArray[i] = this  elements[i];

  104.                 }

  105.                 //create new expanded tree

  106.     return create_Tree(NewArray,0,allElements) ; // all elemtment put in to the one new aray and create new tree and return the root

  107.         }

  108.         void get_inputOrder( Node root , int inputs[]){

  109.                 if (root != null)

  110.                  {  

  111.                         inputs[root  index] = root  value;

  112.                         get_inputOrder(root  leftChild, inputs);

  113.                         get_inputOrder(root  rightChild, inputs);

  114.                 }

  115.         }

  116.     

  117.         public static void main(String[] args){

  118.                 Binary_Tree binaryTree = new Binary_Tree();

  119.                 System  out  println( "Create tree [1,45,23,33,25,53,54,11] \n");

  120.                 int array[] = { 1, 45, 23, 33, 25, 53, 54,11 };

  121.                 Node Root = binaryTree  create_Tree(array, 0,8);

  122.                 System  out  println( "InOrderTraversal of Tree :  " );

  123.                 binaryTree  traverse_inorder(Root);

  124.                 System  out  println("");

  125.                 System  out  println("pre- order traversal : " );

  126.                 binaryTree  traverse_preorder(Root);

  127.                 System  out  println("");

  128.                 System  out  println("post order Traversal :");

  129.                 binaryTree  traverse_postorder(Root);

  130.                 System  out  println( "");

  131.                 System  out  println("\n \n" );

  132.             System  out  println("Expand the same tree[3,22,7,64]\n" );

  133.                 int expand[] = { 3, 22, 7, 64 };

  134.                 Root =  binaryTree  expand_Tree(Root, expand, 4);

  135.                 System  out  println("InOrderTraversal of Tree : " );

  136.                 binaryTree  traverse_inorder(Root);

  137.                 System  out  println("");

  138.                 System  out  println("pre- order traversal :" );

  139.                 binaryTree  traverse_preorder(Root);

  140.                 System  out  println("");

  141.                 System  out  println( "post order Traversal :" );

  142.                 binaryTree  traverse_postorder(Root);

  143.                 System  out  println( "");

  144.                 System  out  println("\n \n");

  145.         }

  146. }

 

 

bottom of page