Code:
#include <iostream>
Code:
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
struct node // the tree node
{
int key;
unsigned char height;
node *left;
node *right;
node(int k)
{
key = k;
left = right = 0;
height = 1;
}
};
unsigned char height(node* p);
int bfactor(node* p);
void fixheight(node* p);
node* rotateright(node* p);
node* rotateleft(node* q);
node* balance(node* p);
node* insert(node* p, int k);
node* findmin(node* p);
node* removemin(node* p);
node* remove(node* p, int k);
void print_tree_infix(node *p);
void tree_to_array(node *p, int *A);
void print_array(int *A, int n);
int main()
{
node *root = NULL;
int A[] = {5, 87, 17, 10, 25, 1, 6, 22};
int n = sizeof(A) / sizeof(A[0]);
// addind massive to tree
for(int i = 0; i < n; i++)
root = insert(root, A[i]);
// displaying initial massive
print_array(A, n);
// copying tree to array by infix method
tree_to_array(root, A);
// displaying sorted massive
print_array(A, n);
// removing massive
for(int i = 0; i < n; i++)
root = remove(root, A[i]);
return 0;
}
void print_tree_infix(node *p)
{
if(!p) return;
else
{
print_tree_infix(p->left);
printf("key=%d\n", p->key);
print_tree_infix(p->right);
}
}
void tree_to_array(node *p, int *A)
{
static int i = 0;
// nulling static variable
if(!A)
{
i = 0;
return;
}
// going through the tree
if(!p) return;
else
{
tree_to_array(p->left, A);
A[i++] = p->key;
tree_to_array(p->right, A);
}
}
void print_array(int *A, int n)
{
for(int i = 0; i < n; i++)
printf("%d ", A[i]);
printf("\n");
}
unsigned char height(node *p)
{
return p ? p->height : 0;
}
int bfactor(node *p)
{
return height(p->right) - height(p->left);
}
void fixheight(node *p)
{
unsigned char hl = height(p->left);
unsigned char hr = height(p->right);
p->height = (hl > hr ? hl : hr) + 1;
}
node *rotateright(node *p) // right rotation
{
node *q = p->left;
p->left = q->right;
q->right = p;
fixheight(p);
fixheight(q);
return q;
}
node *rotateleft(node *q) // left rotation
{
node *p = q->right;
q->right = p->left;
p->left = q;
fixheight(q);
fixheight(p);
return p;
}
node *balance(node *p) // balancing the p node
{
fixheight(p);
if( bfactor(p) == 2 )
{
if( bfactor(p->right) < 0 )
p->right = rotateright(p->right);
return rotateleft(p);
}
if( bfactor(p) == -2 )
{
if( bfactor(p->left) > 0 )
p->left = rotateleft(p->left);
return rotateright(p);
}
return p; // balancing is not needed
}
node *insert(node *p, int k) // inserting key k in the p root
{
if( !p ) return new node(k);
if( k < p->key )
p->left = insert(p->left, k);
else
p->right = insert(p->right, k);
return balance(p);
}
node *findmin(node *p) // seeking the minimal key node
{
return p->left ? findmin(p->left) : p;
}
node *removemin(node *p) // removing the node key minimal
{
if( p->left == 0 )
return p->right;
p->left = removemin(p->left);
return balance(p);
}
node *remove(node *p, int k) // removing k from node p
{
if( !p ) return 0;
if( k < p->key )
p->left = remove(p->left, k);
else if( k > p->key )
p->right = remove(p->right, k);
else // k == p->key
{
node *q = p->left;
node *r = p->right;
delete p;
if( !r ) return q;
node *min = findmin(r);
min->right = removemin(r);
min->left = q;
return balance(min);
}
return balance(p);
}
This is the main function to insert and sort massive elements and turns them back. But what about direct using insert function to paste for example 5 or 6 elements of binary tree and displaying them How to use cin>> tool and how to separate the inserting elements? Everething else seems to be done already.
The second isuue is --is there any simple ways ti convert it from c++ to simply c.