binary-search-tree - 如何从 C++ 为 Graphviz 生成二叉树点文件

Question

我已经用 C++ 实现了一个二叉搜索树，它支持动态创建和删除节点。为了可视化树，我首先尝试使用 / 和 \ 显示边。然而，这给出了非常糟糕的可视化，因为需要精确计算 / 和 \ 的位置。目前的数字如下:

所以我找到了一个叫做Graphviz的工具. Graphviz 支持的原始语言是点语言，我不熟悉。

我阅读了文档，发现 dot 语言易于编写和阅读，但我仍然想使用我的 C++ 代码生成树，因为它包含很多内容，例如根据用户输入插入。

是否有机会使用某些函数生成点文件？

我的二叉树的代码:

    //BTNode.h
    #include <iostream>
    using namespace std;
    template<class T>
    struct BTNode{
        BTNode(){
            lChild = rChild = NULL;
        }
        BTNode(const T& x){
            element = x;
            lChild = rChild = NULL;
        }
        BTNode(const T& x, BTNode<T>* l, BTNode<T>* r){
            element = x;
            lChild = l;
            rChild = r;
        }
        T element;
        int digit, row;
        BTNode<T>* lChild, *rChild;
    };

    //BSTree.h
    #include"ResultCode.h"
    #include "BTNode.h"
    #include "seqqueue.h"
    #include <math.h>
    template <class T>
    class BSTree
    {
    public:
        BSTree(){ root = NULL; }
        ResultCode SearchByRecursion(T& x)const;
        ResultCode Insert(T& x);
        ResultCode Remove(T& x);
        void InOrder(void(*Visit)(T& x));
        ResultCode SearchByIteration(T& x);
        void GradeOrder(void(*Visit)(T &x), BTNode<T> *t, int height);
        BTNode<T>* root;
        void printSpace(int num);
        int GetHeight();
        int GetHeight(BTNode<T> *t);
        int  **A;
    private:
        ResultCode SearchByRecursion(BTNode<T> *p, T& x)const;
        void InOrder(void(*Visit)(T& x), BTNode<T> *t);

    };
    template <class T>
    ResultCode BSTree<T>::SearchByRecursion(T &x)const{
        return SearchByRecursion(root, x);
    }
    template <class T>
    ResultCode BSTree<T>::SearchByRecursion(BTNode<T> *p, T& x)const{
        if (!p) return NotPresent;
        else if (x < p->element) return SearchByRecursion(p->lChild, x);
        else if (x > p->element) return SearchByRecursion(p->rChild, x);
        else{
            x = p->element;
            return Success;
        }
    }
    template <class T>
    ResultCode BSTree<T>::SearchByIteration(T& x){
        BTNode<T> *p = root;
        while (p)
            if (x < p->element) p = p->lChild;
            else if (x > p->element) p = p->rChild;
            else{
                x = p->element;
                return Success;
            }
            return NotPresent;
    }
    template<class T>
    ResultCode BSTree<T>::Insert(T& x){
        BTNode<T> *p = root, *q = NULL;
        while (p){
            q = p;
            if (x < p->element) p = p->lChild;
            else if (x > p->element) p = p->rChild;
            else { x = p->element; return Duplicate; }
        }
        p = new BTNode<T>(x);
        if (!root) root = p;
        else if (x < q->element) q->lChild = p;
        else q->rChild = p;
        return Success;
    }

    template <class T>
    ResultCode BSTree<T>::Remove(T& x){
        BTNode<T> *c, *s, *r, *p = root, *q = NULL;
        while (p && p->element != x){
            q = p;
            if (x < p->element) p = p->lChild;
            else p = p->rChild;
        }
        if (!p) return NotPresent;
        x = p->element;
        if (p->lChild&&p->rChild)
        {
            s = p->rChild;
            r = p;
            while (s->lChild){
                r = s; s = s->lChild;
            }
            p->element = s->element;
            p = s; q = r;
        }
        if (p->lChild)
            c = p->lChild;
        else c = p->rChild;
        if (p == root)
            root = c;
        else if (p == q->lChild)
            q->lChild = c;
        else q->rChild = c;
        delete p;
        return Success;
    }
    template <class T>
    void BSTree<T>::InOrder(void(*Visit)(T &x)){
        InOrder(Visit, root);
    }
    template <class T>
    void BSTree<T>::InOrder(void(*Visit)(T &x), BTNode<T> *t){
        if (t){
            InOrder(Visit, t->lChild);
            Visit(t->element);
            InOrder(Visit, t->rChild);
        }
    }
    template <class T>
    void BSTree<T>::GradeOrder(void(*Visit)(T &x), BTNode<T> *t, int height)
    {
        A = new int*[height];
        for (int i = 0; i < height; i++){
            A[i] = new int[(int)pow(2, height) - 1];
        }
        for (int i = 0; i < height; i++)
            for (int j = 0; j < (int)pow(2, height) - 1; j++){
                A[i][j] = -1;
            }
        SeqQueue<BTNode<T>*> OrderQueue(10);
        BTNode<T> * loc = t;
        loc->row = 0;
        loc->digit = 0;
        if (loc){
            OrderQueue.EnQueue(loc);
            A[loc->row][loc->digit] = loc->element;
        }
        while (!OrderQueue.IsEmpty())
        {
            OrderQueue.Front(loc);
            OrderQueue.DeQueue();
            if (loc->lChild)
            {
                A[(loc->row) + 1][2 * (loc->digit)] = loc->lChild->element;
                loc->lChild->row = (loc->row) + 1;
                (loc->lChild->digit) = (loc->digit) * 2;
                OrderQueue.EnQueue(loc->lChild);
            }
            if (loc->rChild)
            {
                A[(loc->row) + 1][2 * (loc->digit) + 1] = loc->rChild->element;
                loc->rChild->row = (loc->row) + 1;
                (loc->rChild->digit) = (loc->digit) * 2 + 1;
                OrderQueue.EnQueue(loc->rChild);
            }
        }
        cout << endl;

        int total = (int)(pow(2, height)) - 1;

        for (int i = 0; i < height; i++){
            if (i != 0){
                cout << endl;
            }
            int space1 = (total / (int)(pow(2, i + 1)));
            int space2;
            if (i == 0){
                space2 = 0;
            }
            else{
                space2 = (total - 2 * space1 - (int)pow(2, i)) / (int)(pow(2, i) - 1);
            }

            printSpace(space1);
            for (int j = 0; j < (int)pow(2, i); j++){

                if (A[i][j] != -1){
                    cout << A[i][j];
                }
                else{
                    cout << " ";
                }
                printSpace(space2);
            }
            printSpace(space1);
            cout << endl;
        }



    }
    template <class T>
    void BSTree<T>::printSpace(int num){
        for (int i = 0; i < num; i++){
            cout << " ";
        }
    }

    template<class T>
    int BSTree<T>::GetHeight()
    {
        return GetHeight(root);
    }

    template<class T>
    int BSTree<T>::GetHeight(BTNode<T> *t)
    {
        if (!t)return 0;               
        if ((!t->lChild) && (!t->rChild)) return 1; 
        int lHeight = GetHeight(t->lChild);
        int rHeight = GetHeight(t->rChild);
        return (lHeight > rHeight ? lHeight : rHeight) + 1; 
    }
    template <class T>
    void Visit(T& x){
        cout << x << " ";
    }
    //main.cpp
    #include <iostream>
    #include "BSTree4.h"
    #include<Windows.h>
    int getDigit(int x);
    int main(){
        BSTree<int> bt;
        int number;
    //  char choice;
        cout << "Welcome to BSTree System, to begin with, you need to create a tree!(Press enter to continue...)" << endl;
        getchar();
        cout << "Please enter the size of the Binary Search Tree:";
        cin >> number;
        int *ToBeInserted = new int[number];
        cout << "Enter the number of each Node(size:" << number << "):";
        for (int i = 0; i < number; i++){
            cin >> ToBeInserted[i];
        }
        cout << "OK,now the tree will be created!" << endl;
        for (int i = 0; i < number; i++){
            cout << "Inserting Node " << i;
            for (int k = 0; k < 3; k++){
                cout << ".";
                //Sleep(200);
            }
            showResultCode(bt.Insert(ToBeInserted[i]));
            //Sleep(500);
        }
        cout << "Done." << endl;
        //Sleep(500);

        int height = bt.GetHeight();
        bt.GradeOrder(Visit, bt.root,height);
        int a;
        cout << "please enter the number to search:";
        cin>>a;
        showResultCode(bt.SearchByRecursion(a));
        bt.GradeOrder(Visit, bt.root,height);
        if (bt.SearchByRecursion(a) == 7){
            cout << "Now delete the number" << "..." << endl;
            showResultCode(bt.Remove(a));
            bt.GetHeight();
            cout << "Deleted!Now the tree is:" << endl;
            bt.GradeOrder(Visit, bt.root, height);
            bt.InOrder(Visit);
            cout << endl;
        }
        return 0;
    }

    //resultcode.h
    #include<iostream>
    using namespace std;
    enum ResultCode{ NoMemory, OutOfBounds, Underflow, Overflow, Failure,    
    NotPresent, Duplicate, Success };
    void showResultCode(ResultCode result)
    {
        int r = (int)result;
        switch (result)
        {
        case 0:cout << "NoMemory" << endl; break;
        case 1:cout << "OutOfBounds" << endl; break;
        case 2:cout << "Underflow" << endl; break;
        case 3:cout << "Overflow" << endl; break;
        case 4:cout << "Failure" << endl; break;
        case 5:cout << "NotPresent" << endl; break;
        case 6:cout << "Duplicate" << endl; break;
        case 7:cout << "Success" << endl; break;
        default: cout << "Exception occured:unknown resultcode" << endl;
        }
    }

更新:我自己解决了这个问题，查看下面的答案。

Answer 1

本题中点语言文件的关键元素是节点和边。基本上，二叉树的点文件结构如下所示:

digraph g {
//all the nodes
node0[label="<f0>|<f1> value |<f2>"]
node1[label="<f0>|<f1> value |<f2>"]
node2[label="<f0>|<f1> value |<f2>"]
...

//all the edges
"node0":f2->"node4":f1;
"node0":f0->"node1":f1;
"node1":f0->"node2":f1;
"node1":f2->"node3":f1;
...

}

点文件的以下输出可用于理解结构:

点文件说明:

对于节点部分node0[label="<f0>|<f1> value |<f2>"]表示名为 node0 的节点包含三个部分:<f0>是左边的部分，<f1>中间部分有一个值，<f2>是正确的部分。这恰好对应于 leftchild , value和 rightchild在二进制节点中。

对于边缘部分，"node0":f2->"node4":f1;表示 node0 的右边部分(即 <f2> )指向 node4 的中间部分(即 <f1> )。

因此，生成点文件的方法很简单，就是通过遍历一棵二叉树。任何方法都可以。 (BFS，DFS ...)我们只需要添加代码来编写 nodes和相应的edges当我们进行遍历时进入文件。我个人使用 BFS 和二叉树的级别顺序遍历来实现，如下所示，它是一个名为 showTree 的函数。 .

    void showTree(BSTree<int> &bst,int total,int *Inserted){
        char filename[] = "D:\\a.gv"; // filename
        ofstream fout(filename);
        fout << "digraph g{" << endl;
        fout << "node [shape = record,height = .1];" << endl;
        SeqQueue<BTNode<int>*> OrderQueue(1000);
        BTNode<int> * loc = bst.root;
        loc->row = 0;
        loc->digit = 0;
        int num = 0;
        if (loc){
            OrderQueue.EnQueue(loc);
            loc->ID = num++;
            fout << " node" << loc->ID << "[label = \"<f0> |<f1>" << loc->element << "|<f2>\"];" << endl;
        }
    
        while (!OrderQueue.IsEmpty())
        {
            OrderQueue.Front(loc);
            OrderQueue.DeQueue();
            if (loc->lChild)
            {
                loc->lChild->row = (loc->row) + 1;
                (loc->lChild->digit) = (loc->digit) * 2;
                OrderQueue.EnQueue(loc->lChild);
                loc->lChild ->ID= (num++);
                fout << " node" << loc->lChild->ID << "[label = \"<f0> |<f1>" << loc->lChild->element << "|<f2>\"];" << endl;
                //cout << loc->ID;
            }
            if (loc->rChild)
            {
                loc->rChild->row = (loc->row) + 1;
                (loc->rChild->digit) = (loc->digit) * 2 + 1;
                OrderQueue.EnQueue(loc->rChild);
                loc->rChild->ID = (num++);
                fout << " node" << loc->rChild->ID << "[label = \"<f0> |<f1>" << loc->rChild->element << "|<f2>\"];" << endl;
                //cout << loc->ID;
            }
    
        }
    
        //begin to draw!
        SeqQueue<BTNode<int>*> OrderQueue2(1000);
        BTNode<int> * loc2 = bst.root;
        loc2->row = 0;
        loc2->digit = 0;
        if (loc2){
            OrderQueue2.EnQueue(loc2);
        }
        while (!OrderQueue2.IsEmpty())
        {
            OrderQueue2.Front(loc2);
            OrderQueue2.DeQueue();
            if (loc2->lChild)
            {
                loc2->lChild->row = (loc2->row) + 1;
                (loc2->lChild->digit) = (loc2->digit) * 2;
                OrderQueue2.EnQueue(loc2->lChild);
                cout << "\"node" << loc2->ID << "\":f0->\"node" << loc2->lChild->ID << "\":f1;" << endl;
                cout << loc2->lChild->element << endl;
                fout << "\"node" << loc2->ID << "\":f0->\"node" << loc2->lChild->ID << "\":f1;" << endl;
                
            }
            if (loc2->rChild)
            {
                loc2->rChild->row = (loc2->row) + 1;
                (loc2->rChild->digit) = (loc2->digit) * 2 + 1;
                OrderQueue2.EnQueue(loc2->rChild);
                cout << "\"node" << loc2->ID << "\":f2->\"node" << loc2->rChild->ID << "\":f1;" << endl;
                cout << loc2->rChild->element << endl;
                fout << "\"node" << loc2->ID << "\":f2->\"node" << loc2->rChild->ID << "\":f1;" << endl;
            }
        }
        fout << "}" << endl;
    }

最终输出: