I have such task: create binary tree. Than I need to add massive there. After it i need sort out the elements of massive and then turn iut them to massive-but sorted. How to do it. How to find similar examples?

Printable View

- 01-30-2013sendHow create the binary tree and sort the massive there
I have such task: create binary tree. Than I need to add massive there. After it i need sort out the elements of massive and then turn iut them to massive-but sorted. How to do it. How to find similar examples?

- 01-30-2013Elkvis
I found some information that might help you at this link.

- 01-30-2013iMalc
Syntax error on line 1: "massive" is not a noun.

Please explain better, and post your attempt. - 02-04-2013send11Code:

#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. - 02-04-2013iMalc
Cross posting is frowned upon: How make binary tree with this code - C++ Forum

Please stop using the word "massive". Whatever you think it means, you are wrong. Using a spelling checker before posting wouldn't hurt too.

I still don't understand your first question. You would not use cin if you want this to be in pure C because cin is C++ only.

If you want to turn it into C then change the file extension to .c and then fix the compilation errors. Most of it looks like C already except for the first 5 lines. - 02-04-2013send1
Sorry for massive. About c or c++. The first option has too many errors so i need use cin or gets. But how. I need also use function insert so maybe there are no need to use cin. So question is very simple. How using insert function create several elements of tree. And display them. In the last case maybe there will be need to create another function. But for inserting it is but how to do it in main function to make it element by element.

- 02-05-2013C_ntuaCode:
`for(int i = 0; i < n; i++)`

root = insert(root, A[i]);

- 02-10-2013send1
I also do not understand the "it is programming"-what it means. My question is about how to insert for example from console (command line) such elements of binary tree-1, 5,6, 15 etc. I understand that we should use cin>> but how?

- 02-11-2013nvoigt
Can you read a number from the console and print it? Show us some code :)

- 02-11-2013rogster001Quote:

I also do not understand the "it is programming"-what it means.