1
struct TreeNode {
    int num;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* cons_tree(int num, TreeNode *l, TreeNode *r) {
    TreeNode* tmp;
    tmp = new TreeNode;
    tmp->val = num;
    tmp->left = l;
    tmp->right = r;
    return tmp;
}

TreeNode* ordered_insertion_tree(int num, TreeNode *t) {
    if(t == NULL) {
        return cons_tree(num, NULL, NULL);
    }
    else if(num < t->val) {
        t->left = ordered_insertion_tree(num, t->left);
        return t;
    }
    else {
        t->right = ordered_insertion_tree(num, t->right);
        return t;
    }
}

Binary Decision Diagram (BDD)

Binary Search Tree (BST)

The code above shows how to create a BST. But, I would like my program to act like a truth table shown in the BDD image.

Differences between the 2 diagrams:

  1. The dotted lines in the BDD image represent a "0" and the filled line represents a "1" in user input.
  2. For the BST, when the user input is less than the root node it represents the left tree.
  3. Root node for BDD is a string "x1" and for BST is an int 8.

For example, if the user inputs the string "000", "011", "110" and "111", these leaf nodes will have the string "1".

***The input will be appended into a vector of strings named values. So, values[0] represents "000" and so on. ***

My questions are:

  1. How should I rewrite the ordered_insertion_tree function? Initially I was using int which allows me to compare values but now it has changed to std::string and I can't figure out how to make the comparisons.
  2. How do I change the values of the nodes? From "x1", representing the first integer, to "x2" ... "xn" for n number of integers and finally to 0/1 representing the truth table.

Thank you for reading!

Jérôme Richard
  • 41,678
  • 6
  • 29
  • 59
Lun13
  • 11
  • 1
  • Don't try to initialize the BDD the way you'd initialize a BST. Instead build a tree starting from the bottom initializing every leaf with 0 and repeatedly combining 2 neighboring nodes until you're left with only the root node and then search the leafs corresponding to the inputs and change those values to 1. – fabian Mar 14 '21 at 15:30
  • Hi @fabian, I completely understand what you're saying. However, I'm decently new to coding and have no idea how to implement your idea. If it doesn't take up too much of your time, could you link me some resources to read/ personally write some of it? Regardless, I will still find out how I could implement it your way. Thanks! – Lun13 Mar 14 '21 at 15:45
  • It's not really that complicated, if you've got an array of `TreeNode*` storing the leafs. Loop through the array combining nodes at indices 0 and 1, 2 and 3, 4 and 5 ... and store the new nodes at indices 0, 1, 2, ..., then repeat the process (but remember only half of the original elements contain nodes relevant for this step). Repeat this until you're left with 1 node which becomes the root of your BDD. You'll just need to set some of the leafs to 1 at this point... – fabian Mar 14 '21 at 15:57
  • I don't understand, there is no common (outside they're both tree) between binary tree and the BDD you describe (which I think is a prefix tree), you cannot *convert* them (and the input/datatype are actually different in your example...). – apple apple Mar 14 '21 at 15:58
  • @appleapple Yeah, there isn't a common. I guess the term 'convert' is wrong. Basically, I just wanted to know how I could implement the BDD with string inputs replicating the way I did the BST with int inputs. – Lun13 Mar 14 '21 at 16:26
  • Thanks for your reply, @fabian . I will try it and get back to you if I have any further questions. – Lun13 Mar 14 '21 at 16:28
  • @Lun13 you can search for prefix tree for more informations. – apple apple Mar 14 '21 at 17:29
  • one possible simple way is implement the link as `std::map children;` (or `unordered_map`) – apple apple Mar 14 '21 at 17:32
  • 1
    The first image linked in the question is not a binary decision diagram, but a binary decision tree, specifically the one shown at: https://en.wikipedia.org/wiki/Binary_decision_diagram, which also shows the corresponding binary decision diagram. – 0 _ Mar 16 '21 at 18:17
  • If the question is about converting a binary decision tree to a binary decision diagram, then this is essentially the same question as converting a truth table to a binary decision diagram. This is answered by: https://stackoverflow.com/a/66200465/1959808 The answer uses the Python package [`dd`](https://github.com/tulip-control/dd) that implements BDDs. – 0 _ Mar 16 '21 at 18:21
  • Python package `dd` is a wrapper to [CUDD](https://davidkebo.com/cudd) `C` library. – Anton Krouglov Aug 17 '23 at 00:17

0 Answers0