Non-recursive Preorder Traversal - Part 1
Published on 1st of November 2008. Copyright Tavs Dokkedahl. Displayed 3530 time(s)A brief introduction to trees
If you have never heard of trees keep reading otherwise you can safely skip to the next section.
A tree is a datastructure which organizes data as shown on the picture below.
- The root is the top most element. A root element has no parent element nor any siblings.
- A branch has exactly 1 parent element and at least 1 child element. It may have 0 or more siblings.
- A leaf has exactly 1 parent and no child elements. If may have 0 or more siblings.
In general all elements in the tree are called nodes and we differentiate between root, branches and leafs by checking their parent/child properties.
The DOM of a HTML document is such a tree. Below is a picture of how some of the elements of this page are ordered.
This tree corresponds to the following HTML code
1 <html> 2 <head> 3 <title> 4 JavaScript Lab - Articles - Non-recursive Preorder Traversal 5 </title> 6 <meta name=\"language\" content=\"EN\" /> 7 </head> 8 <body> 9 <div id=\"header\"> 10 </div> 11 <div id=\"toolbar\"> 12 <ul> 13 ... 14 </ul> 15 <div class=\"clear\"> 16 </div> 17 </div> 18 ... 19 </body> 20 </html>
The root node is the html element. It has 2 children - the head and the body elements.
The head element has 2 children - the title and the meta elements. These two elements are siblings and share the same parent node.
The meta element is a leaf as it has no child nodes whereas the title is not as it has a string value.
The title string itself is a text node and a leaf.
When we are doing a preorder traversal we are visiting each node in the tree in the following order
So a preorder traversal is a ordering of the elements as they are ordered in the source code.
| Part 2 » |
