Thread: How create the binary tree and sort the massive there

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    13

    How 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?

  2. #2
    Registered User
    Join Date
    Oct 2006
    Posts
    3,445
    Quote Originally Posted by send View Post
    How to find similar examples?
    I found some information that might help you at this link.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Syntax error on line 1: "massive" is not a noun.

    Please explain better, and post your attempt.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Jan 2013
    Posts
    13

    11

    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.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Jan 2013
    Posts
    13

    1

    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.

  7. #7
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Code:
    for(int i = 0; i < n; i++)
       root = insert(root, A[i]);
    this code already inserts element by element. I don't honestly understand what you are saying and it is programming, details matter. I would advise just to talk with some examples and try to ask for one thing at a time.

  8. #8
    Registered User
    Join Date
    Jan 2013
    Posts
    13

    1

    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?

  9. #9
    the hat of redundancy hat nvoigt's Avatar
    Join Date
    Aug 2001
    Location
    Hannover, Germany
    Posts
    3,130
    Can you read a number from the console and print it? Show us some code
    hth
    -nv

    She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."

    When in doubt, read the FAQ.
    Then ask a smart question.

  10. #10
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    I also do not understand the "it is programming"-what it means.
    It means the topic that we are discussing is 'programming' , and because of that then detail matters - Take time to properly formulate a question, you will get better responses - also format your code so that it is not all shoved into the margin of the page - use indentation.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 08-01-2007, 01:08 PM
  2. Binary sort number arranging tree
    By newtocpp in forum C++ Programming
    Replies: 3
    Last Post: 11-14-2006, 05:19 AM
  3. How do you create a balanced binary tree?
    By Mr_Jack in forum C++ Programming
    Replies: 3
    Last Post: 01-13-2004, 03:02 PM
  4. display tree data in binary tree format
    By xddxogm3 in forum C++ Programming
    Replies: 4
    Last Post: 12-11-2003, 12:47 AM
  5. Binary Tree Sort
    By BakAttack in forum C++ Programming
    Replies: 6
    Last Post: 02-06-2003, 12:07 PM