Difference between revisions of "CSC212 Lab 10 2014"
(→Create Another Tree) |
(→Create Another Tree) |
||
| Line 35: | Line 35: | ||
|- | |- | ||
| | | | ||
| − | ==Create | + | ==Challenge 1: Create A Binary-Search Tree== |
|} | |} | ||
[[Image:QuestionMark4.jpg|right|120px]] | [[Image:QuestionMark4.jpg|right|120px]] | ||
| Line 45: | Line 45: | ||
<br /> | <br /> | ||
<br /> | <br /> | ||
| + | * You will notice that the tree doesn't display well when a node only has 1 child. To get a more accurate left-right balance of the nodes, we simply need to create "fake" nodes for the null pointers. | ||
| + | <br /> | ||
| + | ===Adding "Fake" Null Nodes=== | ||
| + | <br /> | ||
| + | The two nodes that do not display well are 10 and 14 because they have only 1 child each. To prevent the vertical alignment, we can declare them as follows, in the DOT language: | ||
| + | <br /> | ||
| + | ::<source lang="dot" hightlight="8,9,12,13"> | ||
| + | digraph "Lab10" { | ||
| + | 8 -> 3; | ||
| + | 8 -> 10; | ||
| + | 3 -> 1; | ||
| + | 3 -> 6; | ||
| + | 6-> 4; | ||
| + | 6 -> 7; | ||
| + | null10left [shape=point]; | ||
| + | 10 -> null10left; | ||
| + | 10 -> 14; | ||
| + | 14 -> 13; | ||
| + | null14right [shape=point]; | ||
| + | 14 -> null14right; | ||
| + | } | ||
| + | </source> | ||
| + | <br /> | ||
| + | * Go ahead and enter the new definition for the tree. Observe that it is now correctly oriented. | ||
=Dot Language= | =Dot Language= | ||
Revision as of 22:25, 28 October 2014
--D. Thiebaut (talk) 22:52, 28 October 2014 (EDT)
Contents
Generating Graphic Representation of Trees
Graphviz is a simple engine for generating very polished images of trees or graphs. Graphviz takes the definition of a tree, or of a graph, written in a specific language called DOT and produces images of the tree or graph structure. Graphviz is sometimes installed on Linux systems, and can be installed as well on Windows and Mac computers. See the see Graphviz's Download page for more details.
Let's generate a simple Tree.
- Open this page in your browser: http://graphviz-dev.appspot.com/ (if the site is down, try this one instead: http://sandbox.kidstrythisathome.com/erdos/
- Make sure DOT is selected as the language
- Enter the following graph definition in the Edit window.
digraph "Lab10" {
8 -> 3;
3 -> 4;
3 -> 10;
3 -> 7;
8 -> 12;
}
- As you type, you should see a graph appearing in the right window.
Challenge 1: Create A Binary-Search Tree |
- Use the same utility to create the tree used in the lecture slides, and shown below:
- You will notice that the tree doesn't display well when a node only has 1 child. To get a more accurate left-right balance of the nodes, we simply need to create "fake" nodes for the null pointers.
Adding "Fake" Null Nodes
The two nodes that do not display well are 10 and 14 because they have only 1 child each. To prevent the vertical alignment, we can declare them as follows, in the DOT language:
digraph "Lab10" { 8 -> 3; 8 -> 10; 3 -> 1; 3 -> 6; 6-> 4; 6 -> 7; null10left [shape=point]; 10 -> null10left; 10 -> 14; 14 -> 13; null14right [shape=point]; 14 -> null14right; }
- Go ahead and enter the new definition for the tree. Observe that it is now correctly oriented.
Dot Language
- If you are interested in learning more about the Dot language for generating trees or graphs with graphviz, you may want to read this Wikipedia page on the Dot Language.
