0

I am working on a code which should parse a boolean expression and load it into a binary tree. However I'm confused about how I should start adding node to the tree.

If I have an expression like: a AND b OR C then I should end up with the following tree:

      AND

  a        OR

        b      c

I found following example which explains how to create a binary tree but not sure how I can modify this to work with boolean expression.

class btree
{
    public:
        btree();
        ~btree();

        void insert(int key);
        node *search(int key);
        void destroy_tree();

    private:
        void destroy_tree(node *leaf);
        void insert(int key, node *leaf);
        node *search(int key, node *leaf);

        node *root;
};

void btree::insert(int key)
{
  if(root!=NULL)
    insert(key, root);
  else
  {
    root=new node;
    root->key_value=key;
    root->left=NULL;
    root->right=NULL;
  }
}
void btree::insert(int key, node *leaf)
{
  if(key< leaf->key_value)
  {
    if(leaf->left!=NULL)
     insert(key, leaf->left);
    else
    {
      leaf->left=new node;
      leaf->left->key_value=key;
      leaf->left->left=NULL;    //Sets the left child of the child node to null
      leaf->left->right=NULL;   //Sets the right child of the child node to null
    }  
  }
  else if(key>=leaf->key_value)
  {
    if(leaf->right!=NULL)
      insert(key, leaf->right);
    else
    {
      leaf->right=new node;
      leaf->right->key_value=key;
      leaf->right->left=NULL;  //Sets the left child of the child node to null
      leaf->right->right=NULL; //Sets the right child of the child node to null
    }
  }
}

I need some pointers on how to get started since I have never done it before. What should the basic algorithm for the insert function look like? I didn't find any similar examples on line.

madm
  • 1
  • Copying your tree is going to be disastrous. – chris Nov 05 '14 at 02:35
  • I don't understand your comment. – madm Nov 05 '14 at 02:38
  • [Rule of Three](http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three). You don't want your destructor freeing something you already freed because a copy did so. – chris Nov 05 '14 at 02:40
  • I am focusing on finding algorithm on how to write the insert function. I'm ignoring the other things for now. – madm Nov 05 '14 at 02:43
  • Think about how you would manage tokens and lexems in your parsing algorithm, then what `key` could actually mean in that context. If you figure out the answer of the first question, you'll probably have enough to figure out how to use a binary tree. – didierc Nov 05 '14 at 03:15
  • Also, the tree you are showing here is a sorted binary tree (there's a comparison on `key_values` in the nodes and the `key` parameter). Maybe you don't need a sorting tree to represent an [AST](https://en.wikipedia.org/wiki/Abstract_syntax_tree)? – didierc Nov 05 '14 at 03:17

0 Answers0