Binary Trees

The Binary Tree ADT (HSM Ch.5.2.1)
- Definition (HSM p.253, Fig.5.28)
- C++ ADT (HSM ADT 5.1)
- Types of binary trees
  - Full binary trees (HSM p.256, Fig.5.11)
  - Complete binary trees (HSM p.257, Fig.5.10)
- Properties (HSM Ch.5.2.2)
  - Maximal number of nodes on a level (HSM Lemma 5.2)
  - Maximal number of nodes in a tree (HSM Lemma 5.2)
  - Relationship between numbers of nodes of degree 0 and 2 (HSM Lemma 5.3)
  - Node numbers in complete binary trees (HSM Lemma 5.4)
- Hierarchy of Binary Tree ADTs (HSM Ch.5.11, Fig.5.44)
  - Binary tree (HSM Fig.5.7)
  - Complete binary tree (HSM Fig.5.10(b), Fig.5.11)
  - Heaps (HSM Fig.5.24, Fig.5.25)
  - Binary search tree (HSM Fig.5.28)
  - Selection trees (HSM Fig.5.31)
Binary Tree Representation (HSM Ch.5.2.3)
- Array representation (HSM Ch.5.2.3.1, Fig.5.12)
  - Space and time efficiency
- Linked representation (HSM Ch.5.2.3.2, Fig.5.14)
  - Space and time efficiency
- Copying and comparing binary trees (HSM Ch.5.4, Prog.5.9-10)
Binary Tree Traversal
- Depth-first
  - Inorder (HSM Ch.5.3.2, Prog.5.1)
  - Preorder (HSM Ch.5.3.3, Prog.5.2)
  - Postorder (HSM Ch.5.3.4, Prog.5.3)
- Breadth-first (HSM Ch.5.3.6, Prog.5.7)
- Inorder traversal
  - Recursive (HSM Ch.5.3.2, Prog.5.1)
  - Non-recursive (HSM Ch.5.3.5, Prog.5.4)
  - With an iterator (HSM Ch.5.3.5, Prog.5.5-6)
  - Threaded binary trees (HSM Ch.5.5)
YABTI
- A binary tree class with external iterator, inherited from YATI
- binarytreeclass.h
- binarytreeclass.cpp
Applications
- Arithmetic expressions (HSM Ch.5.3)
  - Representing expressions
  - Output using traversals
- The SAT problem (HSM Ch.5.4.3)
  - Definition (HSM p.273, Fig.5.18)
  - Representation (HSM p.275)
  - Algorithms (HSM Prog.5.11-12)

Exercises

The binary tree ADT: HSM Ch.5.2, exercise 1-2.
Binary tree representation: HSM Ch.5.2, exercise 3.
Binary tree operations: HSM Ch.5.4, exercise 1-2.
Binary tree traversal: HSM Ch.5.3, exercise 2-3.
Threaded binary trees: HSM Ch.5.5, exercise 2.

Lab Tasks

Reading prefix expressions

Exam Style Questions

Define a {binary tree,complete binary tree,full binary tree}.
What is the maximal number of nodes on a given level of a binary tree?
What is the maximal number of nodes in a binary tree of depth D?
Derive the relationship between the number of nodes of degree 0 and the number of nodes of degree 2, in a binary tree.
Describe how an array may be used to effectively represent a complete binary tree.
Draw the array representation of the following binary tree.
[Picture of some tree, make up your own :-]
In what circumstances is the array representation of a binary tree space efficient and space inefficient?
Give a recursive algorithm for determining if two binary trees are equivalent.
List the nodes visited in the order of an inorder DFS traversal of this binary tree.
[Picture of some tree, make up your own :-]
Draw the inorder-threaded linked representation of this binary tree.
[Picture of some tree, make up your own :-]
Describe, using an example, how an arithmetic expression can be represented using a binary tree. Once represented, how can the expression be output in postfix notation?