CS3 Coursenotes

Chapter 2 Week 3

Show Source | | About « 2.1. Lists :: Contents :: 3.1. Binary Trees Part 2 »

2.2. Binary Trees Part 1¶

2.2.1. Binary Trees Part 1¶

2.2.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.

A
B
C
D
E
F
G
H
I

2.2.1.2. A Recursive Data Structure¶

23
8
35
10
A node followed by a list

20
5
10
30
15
40
25
Left sub-tree is a binary tree
Right sub-tree is a binary tree

2.2.1.3. Binary Tree Node Class¶

interface BinNode { // Binary tree node ADT
  // Get and set the element value
  public Object value();
  public void setValue(Object v);

  // return the children
  public BinNode left();
  public BinNode right();

  // return TRUE if a leaf node, FALSE otherwise
  public boolean isLeaf();
}

2.2.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)

2.2.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.

2.2.1.6. Preorder Traversal (1)¶

static void preorder(BinNode 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
}

2.2.1.7. Preorder Traversal (2)¶

1 / 56 Settings
<<<>>>

Preorder traversal begins.

static void preorder(BinNode 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
}
A
B
C
D
E
F
G
H
I
rt
A
B
D
C
E
G
F
H
I

Saving...
Server Error
Resubmit

2.2.1.8. How not to write a traversal¶

// This is a bad idea
static void preorder2(BinNode rt) {
  visit(rt);
  if (rt.left() != null) preorder2(rt.left());
  if (rt.right() != null) preorder2(rt.right());
}
Problems:

This has a major bug

It puts the focus in the wrong place: Should focus on the current node, not the children. This version is therefore more complicated.

2.2.1.9. Recursion Examples¶

static int count(BinNode 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());
}

Saving...
Server Error
Resubmit

Contact Us || Privacy | | License « 2.1. Lists :: Contents :: 3.1. Binary Trees Part 2 »