如何从 C++ 为 Graphviz 生成二叉树点文件
Bob*_*bHU 3 visualization graphviz graph-visualization binary-search-tree
我用 C++ 实现了一个二叉搜索树，它支持动态创建和删除节点。为了可视化树，我首先尝试使用/和显示边缘\。/然而，这给出了非常糟糕的可视化效果，因为和的位置\需要精确计算。目前的数字如下：
于是我找到了一个叫做Graphviz的工具。Graphviz支持的原始语言是点语言，我不太熟悉。
我阅读了文档，发现点语言易于编写和阅读，但我仍然想使用我的 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;
}
}
更新：我自己解决了这个问题，请检查下面的答案。
该问题中点语言文件的关键元素是节点和边。基本上，二叉树的点文件结构如下所示：
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
对于边缘部分，表示(ie )"node0":f2->"node4":f1;的右侧部分指向(ie ) 的中间部分。node0<f2>node4<f1>
因此，生成dot文件的方式很简单，就是通过二叉树的遍历。什么方法都可以。（BFS，DFS...）我们需要做的就是在遍历时添加将nodes和 相应写入文件的代码。edges我个人使用 BFS 和二叉树的层序遍历来实现，如下所示，为一个名为 的函数showTree。
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;
...
}
最终输出：
