Trees/Binary Trees

Trees

Definition of a tree: a general tree is a finite set of elements called nodes (vertices) and a finite set of directed edges (arcs) that connect pairs of nodes. If a tree is not empty then one node, called the root, has no incoming edges, and every other node has one incoming edge.

Tree is a recursive data structure. Every node in a tree can be viewed as the root of its own tree. This is a subtree: a node and all its descendents. Here is a recursive definition of a tree:

Definition of a tree: A general tree is a set T which is either empty or consists of one or more nodes such that T is partitioned into disjoint subsets

• a single node r, the root
• subtrees or r, which are themselves general trees

Terminology

• A tree is a non-linear container.
• Each node in a tree has one predecessor and may have multiple successors.
• The immediate successors are the children.
• The immediate predecessor is the parent.
• The root is the node that has no predecessor.
• A leaf is a node with no children.
• An interior node is a node that has at least one child.
• A path is a sequence of nodes which follows the edges from parent to child repeatedly.
• The descendents of a node are all nodes on paths from the node to the leaves.
• A subtree is a node and all its descendents.
• Every node has a level: the root is at level zero, and all other nodes are at level (1 + level of parent).
• The height of a tree is the maximum level of all nodes in the tree. The height can also be defined recursively: height = 1 + max(height of children).

Examples

Inheritance Tree

Expression Tree

Game Tree

Binary Trees

A binary tree is a tree where a node has at most 2 children. A recursive definition similar to the above can be used for binary trees:

Definition of a binary tree A binary tree is a set T which is either empty or consists of one or more nodes such that T is partitioned into disjoint subsets

• a single node r, the root
• the left and right subtrees of r, which are themselves binary trees

Here are some additional definitions that pertain to binary trees.

• A full binary tree is a binary tree where all leaves are on the same level and every node has two children.
• A complete binary tree of height h is either full or is full through level h-1 and all leaves at level h or as far to the left as possible.
• A binary tree is balanced if the height of any node's left and right subtrees differ by at most 1.

Draw the full binary tree of heights 1, 2, 3, and 4. Draw a complete binary tree (one which is not full) of heights 3 and 4.

For each of the following, decide whether it is balanced or not:

Tree Traversals

We just studied iterators to visit every element in a list. As a linear data structure, it's easy to vist every element in a list; just start at the beginning and follow the links to the end. For a tree, the traversal order is not as obvious. The traversals we will study here use the edges of the tree. In describing our traversal we will mention "visiting" a node. Visiting means that we process the node (print its data, update its data, etc). Because we will have to go up and down the tree to reach all nodes we will access a node at other times as we move around the tree, but we will only "visit" it once. We have three standard traversal orders:

• preorder: visit the root, preorder T_L, preorder T_R (pre means before, so visit the root first)
• inorder: inorder T_L, visit the root, inorder T_R (in means between, so visit the root between the subtrees)
• postorder: postorder T_L, postorder T_L, visit the root (post means after, so visit the root after the subtrees)

Notice that the traversals are defined recursively! In each traversal, to process the subtrees you use the same order. Consider the following tree.

Preorder:

1. visit node 1
2. preorder T_L of 1: visit node 2
3. preorder T_L of 2: visit node 4
4. preorder T_R of 2: visit node 5
5. preorder T_R of 1: visit node 3
6. preorder T_L of 3: visit node 6
7. preorder T_R of 3: visit node 7

This results in the following order: 1 2 4 5 3 6 7

Inorder:

1. inorder T_L of 1 (node 2): inorder T_L of 2: visit node 4
2. visit node 2
3. inorder T_R of 2: visit node 5
4. visit node 1
5. inorder T_R of 1 (node 3): inorder T_L of 3: visit node 6
6. visit node 3
7. inorder T_R of 3: visit node 7

This results in the following order: 4 2 5 1 6 3 7

Postorder:

1. postorder T_L of 1 (node 2): postorder T_L of 2: visit node 4
2. postorder T_R of 2: visit node 5
3. visit node 2
4. postorder T_R of 1 (node 3): postorder T_L of node 3: visit node 6
5. postorder T_R of 3: visit node 7
6. visit node 3
7. visit node 1

This results in the following order: 4 5 2 6 7 3 1

Perform preorder, inorder, and postorder traversals of the following tree:

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2017