Any connected graph without a cycle is called a tree. Every edge of a tree is a bridge. In general, a graph without any cycles, whether connected or not, is called a forest. We have already seen some trees:
And many non-trees:
Some Facts and Theorems about Trees
A rooted tree has one vertex distinguished from the others. This distinguished vertex is called the root. A vertex of a tree is called a leaf if it has no children. Vertices that have children are called internal vertices. The root is an internal vertex unless it is the only vertex in the graph, in which case it is a leaf. The level of a vertex is the number of edges (length) of a path from the root to that vertex. The height of a rooted tree is the maximum level of any of its vertices. Given an internal vertex v, the children of v are all those vertices that are adjacent to v and are one level farther away from the root than v. If w is a child of v, then v is called the parent of w and all other vertices in the path from the root to w are ancestors of w, while w is a descendant of each of these vertices. Vertices with the same parent are called siblings.
Let T be a tree. If T has
only one or two vertices, then each is called a terminal vertex. If T has at least three vertices, then
a vertex of degree 1 in T is
called a terminal vertex (or a
leaf), and a vertex of degree
greater than 1 is called an internal
vertex (or a branch vertex).
An m-ary tree is a tree in which each vertex has at most m children. The order in which the children are listed is relevant. In particular, in a binary tree, if an internal vertex has two children, one must distinguish between the the first child called the left child and the right child (the second child). An internal vertex of a binary tree has at most one left child and one right child. A full binary tree is a binary tree in which every internal vertex has exactly two children. Given any internal vertex v of a binary tree, the left subtree of v is the binary tree whose root is the left child of v and includes all the descendants of v and their edge set. The right subtree is analogous.
Full and Complete Binary Trees
Full binary tree:
Each node is either a leaf or internal node with exactly two non -empty children. Note: In other words, every node is either a leaf or has two children. For efficiency, any Huffman coding (animation) is a full binary tree.
Complete Binary Tree:
If the height of the tree is h, then all levels except possibly level h are completely full. Level h has all nodes filled in to the left side. "In the general case we may number the nodes 1, 2, ..., n; this numbering has the useful property that the father of node k is node ë k/2 û; the sons of node k are nodes 2k and 2k + 1. The terminal nodes are numbers n + 1 through 2n + 1, inclusive." (Knuth, The Art of Computer Programming -Vol 1 Fundamental Algorithms, 1969, p 401)
Example For the following graph complete the following: The root is ___. The left child of b is ____, while i is a _____ child of h. The right subtree of g is ___&__, the left subtree of g is ___&___. Vertex i is a ________ of g, g is an _______ of i. The height of this tree is _____. The root, a, is located at level __ and c is located at level ___. There are eleven vertices and consequently ____ arcs in this tree. Vertices c and f are __________ of b and ___________ to each other.
Two more Theorems
Example Is there a full binary tree with 5 internal vertices
and 6 terminal vertices? If so, how many total vertices does this tree
Example Is there a binary tree with height 4 and 8 terminal
vertices? What is the greatest
possible number of terminal vertices in a binary tree of height 4?
Traversal of a Binary Tree
One frequently has to perform operations on trees involving every vertex. In order to perform the operation a recursive tree traversal is required. There are three principal ways to traverse a tree: preorder, inorder, and postorder.
The essential difference is the order in which the root is processed: first, middle, or last.
To help with clarity of operation, consider a tree in which the root and internal vertices are arithmetic operators and the terminal vertices are variables:
What is the preorder traversal of this tree? Solution
What is the inorder traversal of this tree? Solution
What is the postorder traversal of this tree? Solution
Let m = 1 and n = 0.5 then determine the value of the expression found in your three solutions above.
What are the preorder, inorder, and postorder expresions for the binary tree in the m-ary example above?