CODEWITHSUNDEEP
c++binary-search-tree
user119420
user119420

Reputation: 107

How to show binary search tree results in arrays?

This is my program, but I don't know how to show the binary search tree results in array (one dimensional). I use random as inputs. How to show binary search tree results in arrays? Help me please.

#include<iostream>
#include<algorithm>

using namespace std;

struct BstNode{
    int data;
    BstNode* left;
    BstNode* right;
};

BstNode* GetNewNode(int data){
    BstNode* newNode = new BstNode();
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

BstNode* Insert(BstNode* root, int data){
    if(root == NULL){
        root = GetNewNode(data);
    }
    else if(data <= root->data){
        root->left = Insert(root->left,data);
    }
    else{
        root->right = Insert(root->right,data);
    }
    return root;
}


int main(){
    int x, i, n, data;
    BstNode* root = NULL;
    cout<<"The number of data : ";cin>>n; 
    for (i=1;i<=n;i++) {
        data=(rand()%100+1);
        cout<<data<<" ";  
        Insert(root,data);
    }
}

Upvotes: 1

Views: 610

Answers (1)

Arun
Arun

Reputation: 20383

I guess OP is looking to fill an array with the elements of BST as observed in in-order traversal. If so, we can try something like the following.

void
fillArrayInorder( BstNode const * pCurr, int * pArr, int & arrIdx ) { 
    if( pCurr ) {
        fillArrayInorder( pCurr->left, pArr, arrIdx );
        pArr[ arrIdx++ ] = pCurr->data;
        fillArrayInorder( pCurr->right, pArr, arrIdx );
    }
}

Call it as

int arr[ MAX_ELEMS ];
int arrIdx = 0;
fillArrayInorder( root, & arr, arrIdx );

Note: Instead of the raw array, it might be better to use a vector and its push_back() method, so that the length and index updating complexity is not necessary in the application code.

Upvotes: 1

Related Questions