Binary tree with user input data

[bbto]

Hi, everyone
I'm writing a program(lab assignment), which i need to build a binary tree with user input form keyboard. and output in post order and in-order.
i'm fine with output function, but have big problem on reading user input.
for the read input function i have to make a recursive, and anon recursive
but i cant even work out the non recursive one...

here is my code so far:

#include <iostream>
using namespace std;

struct Node{
    Node *lLink;
    int value;
    Node *rLink;
};

Node *cons(int x){//create new node
    Node *q;
    q = new Node;
    q->lLink = NULL;
    q->value = x;
    q->rLink = NULL;
    return q;
}

Node * readListInter();// read input date and bulid a ninary tree
void preorderPrint(Node *root );
void postorderPrint(Node *root );
void inorderPrint(Node *root );

Node * readListInter(){
    Node *readtemp;
    Node *left, *right,*root;
    root = NULL;
    int x;
    cout << " enter number(>=0 to stop): ";
    cin >>x;
    while(x>=0){
        if(root == NULL){
            root = cons(x);
            left = root;
            right = root;
        }
        else{
            readtemp = cons(x);
            if(readtemp->value < root->value){//compare to root value
                //left
                if(left->lLink==NULL){
                    left->lLink = readtemp;
                    left = readtemp;
                }
                else if(readtemp->value < left->value){
                    //left - left
                    left->lLink = readtemp;
                    left = readtemp;
                }
                else if(readtemp->value >= left->value){
                    //left-right
                    left->rLink = readtemp;
                    left = readtemp;
                }
                
            }
            else{
                //right
                if(right->lLink==NULL){
                    right->lLink = readtemp;
                    right = readtemp;
                }
                else if(readtemp->value < right->value){
                    //right - left
                    right->lLink = readtemp;
                    right = readtemp;
                }
                else if(readtemp->value >= right->value){
                    //right-right
                    right->rLink = readtemp;
                    right = readtemp;
                }
            }
            cin >> x;
        }
    }

    return root;
}

void preorderPrint(Node *root){
    if ( root != NULL ){
        cout << root->value << " ";
        preorderPrint( root->lLink );
        preorderPrint( root->rLink );
    }
}

void postorderPrint(Node *root ){
    if ( root != NULL ){
        postorderPrint( root->lLink );
        postorderPrint( root->rLink );
        cout << root->value << " ";
    }
}

void inorderPrint(Node *root ){
    if ( root != NULL ) {
        inorderPrint( root->lLink );
        cout << root->value << " ";
        inorderPrint( root->rLink );
    }
}

bool search(int x, Node *root){
    if(root==NULL)
        return false;//empty tree
    else if(x == root->value)
        return true;
    else if(x < root->value)
        return search(x, root->lLink);
    else
        return search(x, root->rLink);
}

int main(){
    Node *p;
    p = readListInter();
    
    inorderPrint(p);
    cout << endl;
    postorderPrint(p);
    cout << endl;
    if(search(4,p))
        cout << "found" << endl;
    else
        cout << "not found" << endl;
    system("PAUSE");
}

what is the problem with my readListinter function??

also the instructor said some that i can use
cin.claer
cin.ignore(numeric_limits<streamsize>::max(),'\n') ;
for the read input function, instead of assign a number to stop inputting
but he didn't say anything abot this two code
and it is my first time see it....
please help me with this, this lab will not be mark mark but my midterm is coming soon , so i would like to understand this.

sorry for my poor english

[WingedPanther]

Look at this tutorial for a good example of non-recursively adding a node: Trees 101

[bbto]

Thanks Winged Panther
the tutorial is helpful

i have make a change to my non-recursive readList function:
but still have some problems

Node * readListInter(){
    Node* root = NULL;//returning object
    Node* temp;
    Node* input;//new node to add
    int x;
    
    cout << "enter number (>0 to stop): ";
    cin >> x;
    while(x>=0){
        input = cons(x);
        if(root == NULL){//if root is empty
            root = input;
            temp = root;//temp is use to store value for compare
        }
        else{
            while(input != NULL){
                if( x < temp->value){//if smaller x to add to left
                    if(temp->lLink == NULL){//left is empty
                        temp->lLink = input;
                        input = NULL;//new node added, exit the loop
                    }
                    else{//if not empty set temp to subtree
                        temp = root->lLink;//problem
                        //temp = temp->lLink;
                    }
                }
                else{//otherwise x add to right
                    if(temp->rLink == NULL){//right is empty
                        temp->rLink = input;
                        input = NULL;//new node added, exit the loop
                    }
                    else{
                        temp = root->rLink;//problem
                        //temp = temp->rLink;
                    }
                }
            }
        }
        cin >> x;
    }
    return root;
}

the code above work fine with actually 7 input, if more then 7 it become a infinite loop.

The reason of the problem is those codes I'm commented problem.Because it change the temp to 2nd level(root is 1st Level) every time.

But if i change those code to what i comment out , the order of the tree will not correct.
it will depend on the 3rd input, if the 3rd is lesser the root then start from 4th input all the inputs will go into left side. 3rd is greater then every thing goes to right after 4th........

how can i temp only go back one level? like

------5
----/---\
---1-----9
--/--\--/--\
-0---2-7--10
-------------\
-------------11
temp is on 11, how to make it to 10

[WingedPanther]

I've made three changes, but not tested. See how this works:

Node * readListInter(){
    Node* root = NULL;//returning object
    Node* temp;
    Node* input;//new node to add
    int x;
    
    cout << "enter number (>0 to stop): ";
    cin >> x;
    while(x>=0){
        input = cons(x);
        if(root == NULL){//if root is empty
            root = input;
            temp = root;//temp is use to store value for compare
        }
        else{
            temp = root; //for each new addition, must start at root to find correct spot
            while(input != NULL){
                if( x < temp->value){//if smaller x to add to left
                    if(temp->lLink == NULL){//left is empty
                        temp->lLink = input;
                        input = NULL;//new node added, exit the loop
                    }
                    else{//if not empty set temp to subtree
                        temp = temp->lLink;//need to move left from the current position
                    }
                }
                else{//otherwise x add to right
                    if(temp->rLink == NULL){//right is empty
                        temp->rLink = input;
                        input = NULL;//new node added, exit the loop
                    }
                    else{
                        temp = temp->rLink;//need to move right from the current position
                    }
                }
            }
        }
        cin >> x;
    }
    return root;
}

[bbto]

Thanks WingedPanther!
it works!

i just focus in side the the else's while loop, forget to look outside

thanks you very much~

[WingedPanther]

Glad I could help