3.1. Binary Trees Part 1¶
3.1.1. Binary Trees Part 1¶
3.1.1.1. Binary Trees¶
A binary tree is made up of a finite set of nodes that is either empty or consists of a node called the root together with two binary trees, called the left and right subtrees, which are disjoint from each other and from the root.
Notation: Node, children, edge, parent, ancestor, descendant, path, depth, height, level, leaf node, internal node, subtree.
ABCDEFGHI
3.1.1.2. A Recursive Data Structure¶
2383510A node followed by a list2051030154025Left sub-tree is a binary treeRight sub-tree is a binary tree
3.1.1.3. Binary Tree Node Class¶
interface BinNode<E> { // Binary tree node ADT // Get and set the element value public E value(); public void setValue(E v); // return the children public BinNode<E> left(); public BinNode<E> right(); // return TRUE if a leaf node, FALSE otherwise public boolean isLeaf(); }
3.1.1.4. Question¶
Write a recursive function named count that, given the root to a binary tree, returns a count of the number of nodes in the tree. Function count should have the following prototype:
int count(BinNode root)
3.1.1.5. Traversals¶
Any process for visiting the nodes in some order is called a traversal.
Any traversal that lists every node in the tree exactly once is called an enumeration of the tree’s nodes.
Preorder traversal: Visit each node before visiting its children.
Postorder traversal: Visit each node after visiting its children.
Inorder traversal: Visit the left subtree, then the node, then the right subtree.
3.1.1.6. Preorder Traversal (1)¶
static <E> void preorder(BinNode<E> rt) { if (rt == null) { return; } // Empty subtree - do nothing visit(rt); // Process root node preorder(rt.left()); // Process all nodes in left preorder(rt.right()); // Process all nodes in right }
3.1.1.7. Preorder Traversal (2)¶
1 / 56 Settings<<<>>>Preorder traversal begins.
- static <E> void preorder(BinNode<E> rt) {
- if (rt == null) { return; } // Empty subtree - do nothing
- visit(rt); // Process root node
- preorder(rt.left()); // Process all nodes in left
- preorder(rt.right()); // Process all nodes in right
- }
ABCDEFGHIrt
3.1.1.8. How not to write a traversal¶
// This is a bad idea static <E> void preorder2(BinNode<E> rt) { visit(rt); if (rt.left() != null) { preorder2(rt.left()); } if (rt.right() != null) { preorder2(rt.right()); } }Problems:1. This has a major bug2. It puts the focus in the wrong place: Should focus on the current node, not the children. This version is therefore more complicated.
3.1.1.9. Recursion Examples¶
static <E> int count(BinNode<E> rt) { if (rt == null) { return 0; } // Nothing to count return 1 + count(rt.left()) + count(rt.right()); }1 / 4 Settings<<<>>>When you write a recursive method that traverses a binary tree, you should avoid the following common mistakes.
- static int bad_count(BinNode root) {
- if (root == null) { return 0; } // Nothing to count
- bad_count(root.left());
- 1 + bad_count(root.left()) + bad_count(root.right());
- }
3.1.1.10. Full and Complete Binary Trees¶
Full binary tree: Each node is either a leaf or internal node with exactly two non-empty children.
Complete binary tree: If the height of the tree is d, then all leaves except possibly level d are completely full. The bottom level has all nodes to the left side.
(a)(b)
3.1.1.11. Full Binary Tree Theorem (1)¶
Theorem: The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.
Proof (by Mathematical Induction):
Base case: A full binary tree with 1 internal node must have two leaf nodes.
Induction Hypothesis: Assume any full binary tree T containing n−1 internal nodes has n leaves.
3.1.1.12. Full Binary Tree Theorem (2)¶
Induction Step: Given tree T with n internal nodes, pick internal node I with two leaf children. Remove I’s children, call resulting tree T’.
By induction hypothesis, T’ is a full binary tree with n leaves.
Restore I’s two children. The number of internal nodes has now gone up by 1 to reach n. The number of leaves has also gone up by 1.
3.1.1.13. Full Binary Tree Corollary¶
Theorem: The number of null pointers in a non-empty tree is one more than the number of nodes in the tree.
Proof: Replace all null pointers with a pointer to an empty leaf node. This is a full binary tree.
3.1.1.14. Dictionary¶
/** The Dictionary abstract class. */ public interface Dictionary<K, E> { /** Reinitialize dictionary */ public void clear(); /** Insert a record @param k The key for the record being inserted. @param e The record being inserted. */ public void insert(K key, E elem); /** Remove and return a record. @param k The key of the record to be removed. @return A maching record. If multiple records match "k", remove an arbitrary one. Return null if no record with key "k" exists. */ public E remove(K key); /** Remove and return an arbitrary record from dictionary. @return the record removed, or null if none exists. */ public E removeAny(); /** @return A record matching "k" (null if none exists). If multiple records match, return an arbitrary one. @param k The key of the record to find */ public E find(K key); /** @return The number of records in the dictionary. */ public int size(); }
3.1.1.15. .¶
.
3.1.1.16. Dictionary (2)¶
How can we implement a dictionary?
We know about array-based lists and linked lists.
They might be sorted or unsorted.
What are the pros and cons?
