Thread: Fast generation of a binary tree

  1. #1
    Registered User
    Join Date
    Jun 2009

    Question Fast generation of a binary tree

    Hi all,

    I am trying to generate a binary tree in C which considers all the possible combination for a number of array elements and a number of different options for each array element.

    For example, consider that the array has 3 values which are the following:

    #define NO_OF_IDS 3
    Array[NO_OF_IDS] = {“ID1”, “ID2”, “ID3”}
    And 2 different option (OPTION 1 and OPTION 2) for each array value.

    Then the tree generated should be that:
    Fast generation of a binary tree-tree-jpg

    where “1” stands for “OPTION 0” and “2” for “OPTION 1”.

    I can create the above tree manually by using the code below:

    root = newNode(“ROOT”, 0);
    /* HEIGHT 1 */
    root->left = newNode(&Array[1], 0);
    root->right = newNode(&Array[1], 1);
    /* HEIGHT 2 */
    root->left->left = newNode(&Array[2], 0);
    root->left->right = newNode(&Array[2], 1);
    root->right->left = newNode(&Array[2], 0);
    root->right->right = newNode(&Array[2], 1);
    /* HEIGHT 3 */
    root->left->left->left = newNode(&Array[3], 0);
    root->left->left->right = newNode(&Array[3], 1);
    root->left->right->left = newNode(&Array[3], 0);
    root->left->right->right = newNode(&Array[3], 1);
    root->right->left->left = newNode(&Array[3], 0);
    root->right->left->right = newNode(&Array[3], 1);
    root->right->right->left = newNode(&Array[3], 0);
    root->right->right->right = newNode(&Array[3], 1);

    struct node* newNode(char *String, uint8_t OPTION)
        struct node* node = (struct node*)
        malloc(sizeof(struct node));
        node->String = String;
        node->OPTION = OPTION;
        node->left = NULL;
        node->right = NULL;
    struct node
        char* String;
        struct node* left;
        struct node* right;
        uint8_t OPTION;
    The question is that: Can I create the tree in a faster way for a specific ID number?

    Thank you all in advance.
    Attached Images Attached Images Fast generation of a binary tree-tree-jpg 

  2. #2
    Registered User
    Join Date
    Apr 2008
    Quote Originally Posted by limp View Post
    The question is that: Can I create the tree in a faster way for a specific ID number?
    Yes, you can generate that tree using a function which takes, for instance, a root node as argument, an array and its size. Use some recursion for a simple solution.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    New Zealand
    Write a recursive function. Have you done any of those before?
    Each call should create two child nodes, and call itself recursively for each of those two child nodes. It should also pass along the index of the item from 'Array' to add to that node. You stop when the index of the item from Array is beyond the end of the array.

    Please have a go at this 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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting From Binary Tree to Threaded Binary Trees
    By elton_fan in forum C Programming
    Replies: 15
    Last Post: 11-08-2007, 11:41 PM
  2. Replies: 2
    Last Post: 08-01-2007, 01:08 PM
  3. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  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. fast random number generation
    By Heraclitus in forum C Programming
    Replies: 4
    Last Post: 02-09-2003, 07:48 PM