Trees Notes

Chapter Scope

• The chapter covers trees as data structures, tree terminology, tree implementations, analyzing tree efficiency, tree traversals, and expression trees.

Trees

• A tree is a non-linear structure where elements are organized hierarchically.

• A tree consists of a set of nodes, where elements are stored, and edges, which connect nodes.

• Each node is located on a particular level.

• There is only one root node in the tree.

• A rooted tree T is defined as a triple (N, r, E), where:

  • N: a set of nodes

  • r \in N: the root of T

  • E: N-r \rightarrow N: parent function such that if (n1, n2) \in E, then n2 is the parent of n1.

Tree Terminology

• Nodes at the lower level of a tree are the children of nodes at the previous level.

• A node can have only one parent but may have multiple children.

• Nodes that have the same parent are siblings.

• The root is the only node which has no parent.

• A node that has no children is a leaf node.

• A node that is not the root and has at least one child is an internal node.

• A subtree is a tree structure that makes up part of another tree.

• A path can be followed through a tree from parent to child, starting at the root.

• A node is an ancestor of another node if it is above it on the path from the root.

• Nodes that can be reached by following a path from a particular node are the descendants of that node.

• The level of a node is the length of the path from the root to the node.

• The path length is the number of edges followed to get from the root to the node.

• The height of a tree is the length of the longest path from the root to a leaf.

• Terms (example):

  • Parent: parent(b) = a, parent(h) = d

  • Child: b, e, f are children of a, h is a child of d

  • Sibling: e, f are siblings of b

  • Ancestor: a, b, d are ancestors of h

  • Descendant: c, d, h are descendants of b

  • Subtree: b and its descendants form a subtree of a

  • Degree: degree(a) = 3, degree(e) = 1, degree(c) = 0

  • Level: level(a) = 0, level(b) = level(e) = level(f) = 1, level(h) = 3

  • Height: height(T) = 3

Binary Tree ADT

• getRoot: Returns a reference to the root of the binary tree.

• isEmpty: Determines whether the tree is empty.

• size: Returns the number of elements in the tree.

• contains: Determines whether the specified target is in the tree.

• find: Returns a reference to the specified target element if it is found.

• toString: Returns a string representation of the tree.

• iteratorInOrder: Returns an iterator for an inorder traversal of the tree.

• iteratorPreOrder: Returns an iterator for a preorder traversal of the tree.

• iteratorPostOrder: Returns an iterator for a postorder traversal of the tree.

• iteratorLevelOrder: Returns an iterator for a level-order traversal of the tree.

Binary Tree Structure

• A binary tree is composed of zero or more nodes.

• In Java, a reference to a binary tree may be null.

• Each node contains:

  • A value (some sort of data item).

  • A reference or pointer to a left child (may be null).

  • A reference or pointer to a right child (may be null).

• A binary tree may be empty (contain no nodes).

• If not empty, a binary tree has a root node.

• Every node in the binary tree is reachable from the root node by a unique path.

• A node with no left child and no right child is called a leaf.

• In some binary trees, only the leaves contain a value.

Left vs. Right

• Left and right are not relative terms.

• The following two binary trees are different:

  • In the first binary tree, node A has a left child but no right child.

  • In the second, node A has a right child but no left child.

Terminology Reminder

• Node A is the parent of node B if node B is a child of A.

• Node A is an ancestor of node B if A is a parent of B, or if some child of A is an ancestor of B.

  • In less formal terms, A is an ancestor of B if B is a child of A, or a child of a child of A, or a child of a child of a child of A, etc.

• Node B is a descendant of A if A is an ancestor of B.

• Nodes A and B are siblings if they have the same parent.

Size and Depth

• The size of a binary tree is the number of nodes in it.

• The depth of a node is its distance from the root.

• The depth of a binary tree is the depth of its deepest node.

Balance

• A binary tree is balanced if every level above the lowest is “full” (contains 2^n – 1 nodes).

• In most applications, a reasonably balanced binary tree is desirable.

Sorted Binary Trees

• A binary tree is sorted if every node in the tree is larger than (or equal to) its left descendants, and smaller than (or equal to) its right descendants.

• Equal nodes can go either on the left or the right (but it has to be consistent).

Binary Search in a Sorted Array

• Look at array location (lo + hi)/2.

Tree Traversals

• A binary tree is defined recursively: it consists of a root, a left subtree, and a right subtree.

• To traverse (or walk) the binary tree is to visit each node in the binary tree exactly once.

• Tree traversals are naturally recursive.

• Since a binary tree has three “parts,” there are six possible ways to traverse the binary tree:

  • root, left, right

  • left, root, right

  • left, right, root

  • root, right, left

  • right, root, left

  • right, left, root

Preorder Traversal

• In preorder, the root is visited first.

• Algorithm:
  java public void preorderPrint(BinaryTree bt) { if (bt == null) return; System.out.println(bt.value); preorderPrint(bt.leftChild); preorderPrint(bt.rightChild); }

Inorder Traversal

• In inorder, the root is visited in the middle.

• Algorithm:
  java public void inorderPrint(BinaryTree bt) { if (bt == null) return; inorderPrint(bt.leftChild); System.out.println(bt.value); inorderPrint(bt.rightChild); }

Postorder Traversal

• In postorder, the root is visited last.

• Algorithm:
  java public void postorderPrint(BinaryTree bt) { if (bt == null) return; postorderPrint(bt.leftChild); postorderPrint(bt.rightChild); System.out.println(bt.value); }

Tree Traversals Using "Flags"

• The order in which the nodes are visited during a tree traversal can be easily determined by imagining there is a “flag” attached to each node.

Other Traversals

• The other traversals are the reverse of these three standard ones.

  • That is, the right subtree is traversed before the left subtree is traversed.

• Reverse preorder: root, right subtree, left subtree

• Reverse inorder: right subtree, root, left subtree

• Reverse postorder: right subtree, left subtree, root