Inserting infix into a binary tree

This is a discussion on Inserting infix into a binary tree within the C++ Programming forums, part of the General Programming Boards category; This shows the general technique of recursive descent. It evaluates expressions like 4 + (((3 + 5) * 6 + ...

  1. #16
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    This shows the general technique of recursive descent.
    It evaluates expressions like
    4 + (((3 + 5) * 6 + 8 + 4));
    val = 64

    Code:
    #include <iostream>
    using std::cout;
    using std::cin;
    using std::endl;
    
    /*
      start->expr;
      expr-> term | term + expr | term - expr
      term-> factor * term | factor / term | factor
      factor-> (expr) | num
      num-> [0..N]
    */
    
    enum { END_FILE, END_STATEMENT, PLUS, MINUS,
           MULTIPLY, DIVIDE, LEFT_PARAN, RIGHT_PARAN, NUMBER};
    
    struct Token {
        int type;
        int val;
    };
    
    void read_next_token();
    bool match(int token_type);
    int start();
    int expr();
    int term();
    int factor();
    
    Token next_token;
    
    
    int main(void)
    {
        int val;
        
        read_next_token();
        val = start();
        cout << "val = " <<  val << endl;
        return 0;
    }
    
            
    
    void read_next_token()
    {
        int c;
    
        next_token.type = END_FILE;
        next_token.val  = 0;
        
        while((c = cin.get()) && isspace(c))
            continue;
    
        if (isdigit(c)) {
            int n = 0;
            
            cin.putback(c);
            cin >> n;
            next_token.type = NUMBER;
            next_token.val  = n;
            return;
        }
        
        switch(c) {
        case ';':
            next_token.type = END_STATEMENT;
            break;
        case '+':
            next_token.type = PLUS;
            break;
        case '-':
            next_token.type = MINUS;
            break;
        case '*':
            next_token.type = MULTIPLY;
            break;
        case '/':
            next_token.type = DIVIDE;
            break;
        case '(':
            next_token.type = LEFT_PARAN;
            break;
        case ')':
            next_token.type = RIGHT_PARAN;
            break;
        }
    }
    
    bool match(int token_type)
    {
        bool ret;
        
        if (next_token.type == token_type) {
            read_next_token();
            ret = true;
        } else {
            ret = false;
        }
    
        return ret;
    }
    
    int start()
    {
        int val = expr();
        return val;
    }
    
    int expr()
    {
        int val = 0;
    
        val = term();
        switch(next_token.type) {
        case PLUS:
            match(PLUS);
            val += expr();
            break;
        case MINUS:
            match(MINUS);
            val -= expr();
            break;
        default:
            break;
        }
     
        return val;
    }
    
    int term()
    {
        int val;
    
        val = factor();
    
        switch(next_token.type) {
        case MULTIPLY:
            match(MULTIPLY);
            val *= term();
            break;
        case DIVIDE:
            match(DIVIDE);
            val /= term();
            break;
        default:
            break;
        }
    
        return val;
    }
        
    
    int factor()
    {
        int val = 0;
        
        switch(next_token.type) {
        case NUMBER:
            val = next_token.val;
            match(NUMBER);
            break;
        case LEFT_PARAN:
            match(LEFT_PARAN);
            val = expr();
            match(RIGHT_PARAN);
            break;
        default:
            break;
        }
        
        return val;
    }

  2. #17
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Urg I just give up. I am never going to get this done. the struct is a simple

    struct node{
    char data;
    node *left, *right;
    }

    that's it.

    I don't know how I'd insert into a tree using recursive descent either. No idea whatsoever

  3. #18
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    It's easy to insert using recursive descent.

    Code:
    int factor()
    {
        int val = 0;
        
        switch(next_token.type) {
        case NUMBER:
            val = next_token.val;
            match(NUMBER);
            break;
        case LEFT_PARAN:
            match(LEFT_PARAN);
            val = expr();
            match(RIGHT_PARAN);
            break;
        default:
            break;
        }
        
        return val;
    }
    What type of tree would generate if next_token.type is
    a NUMBER like 4? Just a single node tree with
    '4'
    What about a left param? Just a single node tree
    '('

    Now how would you code expr

    Code:
    int expr()
    {
        int val = 0;
    
        val = term();
        switch(next_token.type) {
        case PLUS:
            match(PLUS);
            val += expr();
            break;
        case MINUS:
            match(MINUS);
            val -= expr();
            break;
        default:
            break;
        }
     
        return val;
    }
    You would first generate a tree from term. Call that
    tree left. Set right = 0.
    If next_token.type == PLUS you generate
    a tree from expr and assign that to right. Similarly for
    next_token.type == MINUS. Then to generate the tree
    for expr you would right something like this
    Code:
    if (right != 0) {
          root = new_node(left, right);
    } else {
          root = left;
    }
    It's really easy for all of the functions. Just add a little error
    checking in match and your finished.

  4. #19
    Blank
    Join Date
    Aug 2001
    Posts
    1,034

    Post

    I'm not going to show you the code because that
    would cheating but I was able to modifiy it to do
    preorder, postorder and inorder traversals in only 230 lines.
    The protypes of the functions are

    void read_next_token();
    bool match(int token_type);
    Node* start();
    Node* expr();
    Node* term();
    Node* factor();
    void inorder(Node* root);
    void postorder(Node* root);
    void preorder(Node* root);
    Last edited by Nick; 01-20-2003 at 04:33 PM.

  5. #20
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Is there any place I can talk to you besides this board?

  6. #21
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Code:
    void traverseInOrder(node *root){
    	
    	if (!root)		//test first to see if done
    		return;
    		
    	traverseInOrder(root->left);
    	cout << root->data << " ";	
    	traverseInOrder(root->right);	   
    }
    
    
    void traversePreOrder(node *root){
    	
    	if (!root)		//test first to see if done
    		return;
    		
    	cout << root -> data << " ";		
    	traversePreOrder(root -> left);
    	traversePreOrder(root -> right);	
    }
    
    
    void traversePostOrder(node *root){
    	
    	if (!root)		//test first to see if done
    		return;
    		
    	traversePostOrder(root -> left);
    	traversePostOrder(root -> right);
    	cout << root -> data << " ";	
    }
    I can get those three of your list

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21