When we implement a complex data structure, such as binary tree, graph, hop table, Debug, how to verify their function is correct?

One approach is to visualize data structures and compare them with theoretical results.

Here we go: Graphviz, with an interpretive language called DOT, for graphing in plain code. I recommend this one because it automatically typesets

1. Install

Website download link [1] : www.graphviz.org/download/

Author system for Win10, other operating systems should be similar. Select Add environment variables when installing:

Adding environment variables

2. Apply colours to a drawing

Readers with vscode can install a vscode plug-in:

Install the vscode plug-in

When the installation is complete, create a new.dot file and a render button will appear in the upper right corner:

The render button

Readers without vscode can render manually using the command:

Dot-tpng your code file name -o output image file nameCopy the code

3. Write code

An empty dot code (rendering nothing) :

digraph {
}
Copy the code

Four sample render effects

To create a node named A, use the following code at the top left

digraph {
  a
}
Copy the code

In the lower left part of the figure, the text displayed on the node can be changed by modifying the label. > < p style = “dotted”, which is used to indicate NULL nodes.

Digraph {a[label = "dotted", style = "dotted"]}Copy the code

Create a line with node name -> node name. The same applies to dotted lines, which are used to join NULL nodes. This taillabel displays a value near the first node (can be used to display a value in a node)

digraph {
    node1[label = "A"]
    node2[label = "B"]
    node1 -> node2[style = dotted, taillabel = "0"]
}
Copy the code

Tips: It is recommended to display node[label =] data, i.e. value, in the most prominent and conspicuous way.

4. The pit

3.4.1 track of NULL covering

When a normal node is missing its left or right child, a NULL pointer is used to fill the void.

It is because of its automatic typesetting function that it can cause some pits. For example, we would draw a binary tree like this:

1 | -- -- -- -- -- - | | 0 no right child node (NULL)Copy the code

Since we can’t use variable names that start with numbers, our naming rules are: n + numbers.

Painting effect:

The NULL node complement bit

We find that the tree is pulled into a chain if a node NULL is not used to complete the bits. We just need to use a layer of NULL nodes to fill in the bits and the structure will render properly.

3.4.2 named

Two nodes with the same name are considered to be one node:

The node names are the same

Although this does not exist in binary search trees, it is mentioned here.

How do you tell the difference between nodes? We can name them by Pointers to nodes in C++ programs. Node name: n + pointer Even if two nodes store the same content, the memory address in the computer must be different.

But NULL nodes are all called N0, so you can’t tell them apart. So what do you do? The solution I’m using here is to name the NULL node n + the leaf pointer + whether the left child or the right child

AVL sample

3.5 code

This code is based on the definition of nodes in Part 1.

Void DEBUG() {// FILE *fp = NULL; fp = fopen("./output.dot", "w"); //./output.dot is the output file name fprintf(fp, "digraph {\n"); deque<node*> q; // Use queue to implement node *current; q.push_back(root); while (! q.empty()) { current = q.front(); q.pop_front(); if (current == NULL) { continue; } fprintf(fp, "\tn%d[label = \"%d\"]\n", current, current->value); for (int i = 0; i < 2; ++i) { if (current->child[i]) { fprintf(fp, "\tn%d -> n%d[style = blod]\n", current, current->child[i]); q.push_back(current->child[i]); } else { fprintf(fp, "\tnull%d%d[label = \"NULL\", style = dotted]\n", current, i); fprintf(fp, "\tn%d -> null%d%d[style = dotted]\n", current, current, i); } } } fprintf(fp, "}"); fclose(fp); }Copy the code