Basic concepts:

Tree consist of a set of nodes and a set of edges. There are multiple important concepts to clarify.

Leaf: nodes with no children
Sibling: nodes with common parent
Ancestors of node d: nodes on the path from d to the root, including node itself
Depth of node d: length of the path from d to the root
Height of node d: length of the path from d to its deepest descendant
The height of a tree is the depth of its deepest node = height of the root
Binary tree: a tree in which no node has more than two children

For the height, it starts from the leaf node. All leaf nodes have height of 0. For example, node 7, 5, 9, 10.

For the depth, it starts from the root. The root has depth of 0.

For example, node 8 has height 1, depth 3.

Tree traversal:

preorder: A preorder traversal is a natural way to print a directory’s structure.

visit the parent first and then left and right children.

public void preorder() {
     this.visit();
     if (firstChild != null) {
         firstChild.preorder();
     }
     if (nextSibling != null) {
         nextSibling.preorder();
     }
 }

postorder: A postorder traversal is the natural way to sum the total disk space used in the root directory and its descendants.

visit left child, then the right child and then the parent.

 public void postorder() {
     if (firstChild != null) {
         firstChild.postorder();
     }
     this.visit();
     if (nextSibling != null) {
         nextSibling.postorder();
     }
 }

inorder: recursively traverse the root’s left subtree (rooted at the left child), then the root itself, then the root’s right subtree.

visit the left child, then the parent and the right child.

levelorder: visit the root, then all the depth-1 nodes (from left to right), then all the depth-2 nodes, et cetera.

Use a queue, which initially contains only the root. Then
repeat the following steps:
 - Dequeue a node.
 - Visit it.
 - Enqueue its children (in order from left to right).
Continue until the queue is empty

Month: August 2016

Tree Summary

Basic concepts:

Tree traversal: