#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;

}

### Like this:

Like Loading...

*Related*

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); }}