Wednesday, October 18, 2017

binary tree creation and inorder traversal for sorting implemented in c++

//// Created by Laxmi Kadariya on 10/17/17.//
#include "iostream"using namespace std;

struct node{
    int key;
    struct node *left,*right;

};

struct node *newNode(int item)
{
    struct node *temp = new node;
    temp->key = item;
    temp->left = NULL;
    temp->right = NULL;
    return temp;


}

struct node*  insert(node *node,int key)
{
    if (node == NULL)
    {
        return newNode(key);
    }
    if(key<node->key)
    {
        node->left = insert(node->left,key);
    }

    else if(key>node->key)
    {
        node->right = insert(node->right,key);
    }

    return node;

}



struct node* create_binary_tree(int arr[],int n)
{
    struct node *root = NULL;
    root = insert(root,arr[0]);
    for(int i=1;i<n;i++)
    {
        insert(root,arr[i]);
    }

    return root;

}

void storeSorted(node *root, int arr[], int &i)
{
    if (root != NULL)
    {
        storeSorted(root->left, arr, i);
        arr[i++] = root->key;
        storeSorted(root->right, arr, i);
    }
}




int main()
{
    int arr[] = {5,4,7,2,11};
    int n = sizeof(arr)/ sizeof(arr[0]);
    int i =0;
    struct node *root = create_binary_tree(arr,n);

    storeSorted(root,arr,i);

    for (int i=0; i<n; i++)
        cout << arr[i] << " ";







}

No comments:

Post a Comment