Binary Search Tree to sorted Double Linked List

#include <stdio.h>


class BinarySearchTree
{
    private:
int data;
BinarySearchTree *left, *right;

    public:
BinarySearchTree(const int d):data(d), left(NULL), right(NULL){}

~BinarySearchTree()
{
if(left != NULL)
{
delete left;
}
if(right != NULL)
{
delete right;
}
}

//constructs bst from an array
void construct(const int a[], const int n, const int i)
{
int j;

for(j = i; j < n; ++j)
{
insert(a[j]);
}
}


//converts the BST to Double Linked List
BinarySearchTree* BstToDbl(BinarySearchTree **prev)
{
BinarySearchTree *head = NULL;

if(left)
head = left->BstToDbl(prev);

if(*prev)
{
(*prev)->right = this;
left = *prev;
}

*prev = this;

if(right)

right->BstToDbl(prev);

if(head == NULL) //no prev, this is the first element
return this;
else
return head;
}


int median(BinarySearchTree **prev, float *md, int pos, const int num)
{
if(left)
pos = left->median(prev, md, pos, num) + 1;

if(pos == num)
{
const int prevData = (*prev) ? (*prev)->data : 0;

if(num & 1) //odd
{
*md = data;
}
else //even
{
*md = (data + prevData) / 2.0;
}
}

*prev = this;

if(right)
pos = right->median(prev, md, pos + 1, num);

return pos;
}

void print()
{
printf("%d ", data);

if(right)
right->print();
}

int inorder(int pos)
{
if(left)
pos = left->inorder(pos) + 1;

printf("%d ", data);

if(right)
pos = right->inorder(pos + 1);

return pos;
}

void insert(const int el)
{
if(el < data)
{
if(left)
left->insert(el);
else
{
left = new BinarySearchTree(el);
}
}
else
{
if(right)
right->insert(el);
else
{
right = new BinarySearchTree(el);
}
}
}

};


int main()
{
int n;

scanf("%d", &n);

int i;

int a[n];

for(i = 0; i <n; ++i)
scanf("%d", a + i);


BinarySearchTree *t = new BinarySearchTree(a[0]);

t->construct(a, n, 1);

BinarySearchTree *prev = NULL;

// BinarySearchTree *d = t->BstToDbl(&prev);

// d->print();

int num = t->inorder(0);

printf("\n");

printf("num: %d\n", num);

float md = -1;

t->median(&prev, &md, 0, (num & 1) ? (num +1)/2 : num / 2 );

printf("median = %.2f\n", md);

return 0;
}
Advertisements

One thought on “Binary Search Tree to sorted Double Linked List

  1. This converts tree to list in place—————————————–void TreetoList(node *root){ static node *prev; if(root){ TreetoList(root->lptr); if(root->lptr) { prev=root->lptr; while(prev->rptr)prev=prev->rptr; prev->rptr=root; root->lptr=prev; printf("\n%d is connected to %d as left node",prev->data,root->data); } if(root->rptr) { prev=root->rptr; while(prev->lptr)prev=prev->lptr; printf("\n%d is connected to %d as right node",prev->data,root->data); } TreetoList(root->rptr); }}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s