Thread: N-ary tree setup?

  1. #1
    Registered User
    Join Date
    Oct 2008

    N-ary tree setup?

    Hello there,

    I'm not new to writing programs but I am quite new to proper programming (i.e. C);

    Anyways, I have to write a program to parse an expression into a boolean circuit. The expressions have to follow a strict grammar. For example:
    xY zRg     =    ((x AND (NOT y) OR (z AND (NOT r) AND g))
    I'm thinking the best way to implement this would be using an N-ary tree. But I have no idea how to set one up.

    Can someone show me how to set one up simply, please?

    Thanks for your time,


  2. #2
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    I had once implemented what you ask. Yeah, a tree is perfect for what you want. You will probably need a 3-ary tree. Okay, you know the board's policy about homework. So I ll give you some code to start with and you can continue from there. If you get stuck just post again.
    Here is how you would define a node for a 3-ary tree. I will make it double-linked, meaning you can go up and down the tree.
    typedef nodeTag {
        struct nodeTag *rightChild;
        struct nodeTag *leftChild;
        char operator;
        char leftVar;
        char rightVar;
    } node;
    So you have a node. Now, you will connect all the nodes with the next and previous pointers. Each node will have tree character. The operator for AND, OR etc etc resambled as 'a', 'o' etc etc and two variables.

    The above code should get you stared. For example you can create two nodes like:
    node *root; //the starting point
    node n1;
    node n2;
    node n3;
    root = &n1;
    n1.rightChild = &n2;
    n1.leftChild = &n3
    n2.leftChild = NULL;
    n3.righChild = NULL;
    n1.operator = '0'; 
    n1.leftVar = 'x';
    // go through one path of the tree through the left childs and make every operator 'a'
    node *ptr = root;
    while (ptr != NULL) {
        (*ptr).operator = 'a'
        ptr = ptr->leftChild;
    It needs some work by the way...

  3. #3
    Registered User
    Join Date
    Oct 2008
    Excellent, thank you very much.

    Yes I'm aware of the HW policy, I wasn't look for spoon feeding, just a point in the right direction. Anyway, I want to achieve this myself!


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of
    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, 10:45 PM