c++ - 如何将二叉树转换为二叉决策图

Question

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;
    }
}

二元决策图 (BDD)

二叉搜索树 (BST)

上面的代码显示了如何创建 BST。但是，我希望我的程序表现得像 BDD 图像中显示的真值表。

两张图的区别：

1. BDD 图像中的虚线表示“0”，实线表示用户输入中的“1”。
2. 对于 BST，当用户输入小于根节点时，它代表左树。
3. BDD 的根节点是字符串“x1”，而 BST 的根节点是 int 8。

例如，如果用户输入字符串“000”、“011”、“110”和“111”，则这些叶节点将具有字符串“1”。

***输入将附加到名为值的字符串向量中。因此，values[0] 代表“000”等等。***

我的问题是：

1. 我应该如何重写ordered_insertion_tree 函数？最初我使用 int 来比较值，但现在它已更改为 std::string ，我不知道如何进行比较。
2. 如何更改节点的值？从代表第一个整数的“x1”，到代表n个整数的“x2”...“xn”，最后到代表真值表的0/1。

感谢您的阅读！

标签： c++data-structurestreebinary-search-treebinary-decision-diagram