Data Structures and Abstractions with Java™

5th Edition

Chapter 24

Trees

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Hierarchical Organizations

FIGURE 24-1 Carole’s children and grandchildren

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Hierarchical Organizations

FIGURE 24-2 Jared’s parents and grandparents

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Hierarchical Organizations

FIGURE 24-3 A portion of a university’s administrative structure

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Hierarchical Organizations

FIGURE 24-4 Computer files organized into folders

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Tree Terminology

FIGURE 24-5 A tree equivalent to the tree in Figure 24-4

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Tree Terminology
• Contrast plants with root at bottom
– ADT tree with root at top
– Root is only node with no parent
• A tree can be empty
• Any node and its descendants form a subtree of the
original tree
• The height of a tree is the number of levels in the tree

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Binary trees

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Binary Trees

FIGURE 24-6 Three binary trees

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Binary Trees

Balanced, but not complete

FIGURE 24-7 Some binary trees that are height balanced

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Binary Tree Height (Part 1)

FIGURE 24-8 The number of nodes in a full binary tree as a function of the tree’s height
Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Binary Tree Height (Part 2)

FIGURE 24-8 The number of nodes in a full binary tree as a function of the tree’s height
Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Traversals of A Tree
• Traversal:
– Visit, or process, each data item exactly once
• We will say that traversal can pass through a node without
visiting it at that moment.
• Order in which we visit items is not unique
• Traversals of a binary tree are somewhat easy to understand

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Traversals of a Binary Tree
• We use recursion
• To visit all the nodes in a binary tree, we must
– Visit the root
– Visit all the nodes in the root’s left subtree
– Visit all the nodes in the root’s right subtree

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Traversals of a Binary Tree
• Preorder traversal
– Visit root before we visit root’s subtrees
• Inorder traversal
– Visit root of a binary tree between visiting nodes in
root’s subtrees.
• Postorder traversal
– Visit root of a binary tree after visiting nodes in root’s
subtrees
• Level-order traversal
– Begin at root and visit nodes one level at a time

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Traversals of a Binary Tree

FIGURE 24-9 The visitation order of a preorder traversal

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Traversals of a Binary Tree

FIGURE 24-10 The visitation order of an in-order traversal

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Traversals of a Binary Tree

FIGURE 24-11 The visitation order of a postorder traversal

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Traversals of a Binary Tree

FIGURE 24-12 The visitation order of a level-order traversal

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Traversals of a General Tree
• Types of traversals for general tree
– Level order
– Preorder
– Postorder
• Not suited for general tree traversal
– Inorder

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Traversals of a General Tree

FIGURE 24-13 The visitation order of two traversals of a general tree

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Interfaces for All Trees

package TreePackage;
/** An interface of basic methods for the ADT tree. */
public interface TreeInterface<T>
{
public T getRootData();
public int getHeight();
public int getNumberOfNodes();
public boolean isEmpty();
public void clear();
} // end TreeInterface

LISTING 24-1 An interface of methods common to all trees

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Traversals
package TreePackage;
import java.util.Iterator;
/** An interface of iterators for the ADT tree. */
public interface TreeIteratorInterface<T>
{
public Iterator<T> getPreorderIterator();
public Iterator<T> getPostorderIterator();
public Iterator<T> getInorderIterator();
public Iterator<T> getLevelOrderIterator();
} // end TreeIteratorInterface

LISTING 24-2 An interface of traversal methods for a tree

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Interface for Binary Trees
package TreePackage;
/* An interface for the ADT binary tree. */
public interface BinaryTreeInterface<T> extends TreeInterface<T>,
TreeIteratorInterface<T>
{
/** Sets the data in the root of this binary tree.
@param rootData The object that is the data for the tree's root.
*/
public void setRootData(T rootData);

/** Sets this binary tree to a new binary tree.

@param rootData The object that is the data for the new tree's root.
@param leftTree The left subtree of the new tree.
@param rightTree The right subtree of the new tree. */
public void setTree(T rootData, BinaryTreeInterface<T> leftTree,
BinaryTreeInterface<T> rightTree);
} // end BinaryTreeInterface

LISTING 24-3 An interface for a binary tree

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Building a Binary Tree
BinaryTreeInterface<String> dTree = new BinaryTree<>();
dTree.setTree("D", null, null);

BinaryTreeInterface<String> fTree = new BinaryTree<>();

fTree.setTree("F", null, null);

BinaryTreeInterface<String> gTree = new BinaryTree<>();

gTree.setTree("G", null, null);

BinaryTreeInterface<String> hTree = new BinaryTree<>();

hTree.setTree("H", null, null);
FIGURE 24-14 A
BinaryTreeInterface<String> emptyTree = new BinaryTree<>(); binary tree whose
// Form larger subtrees nodes contain one-
BinaryTreeInterface<String> eTree = new BinaryTree<>(); letter strings
eTree.setTree("E", fTree, gTree); // Subtree rooted at E

BinaryTreeInterface<String> bTree = new BinaryTree<>();

bTree.setTree("B", dTree, eTree); // Subtree rooted at B

BinaryTreeInterface<String> cTree = new BinaryTree<>();

cTree.setTree("C", emptyTree, hTree); // Subtree rooted at C

BinaryTreeInterface<String> aTree = new BinaryTree<>();

aTree.setTree("A", bTree, cTree); // Desired tree rooted at A

Java statements that build a tree

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Building a Binary Tree
// Display root, height, number of nodes
System.out.println("Root of tree contains " + aTree.getRootData());
System.out.println("Height of tree is " + aTree.getHeight());
System.out.println("Tree has " + aTree.getNumberOfNodes() + " nodes");

// Display nodes in preorder

System.out.println("A preorder traversal visits nodes in this order:");
Iterator<String> preorder = aTree.getPreorderIterator();
while (preorder.hasNext())
System.out.print(preorder.next() + " ");
System.out.println();

FIGURE 24-14 A binary

tree whose nodes contain
one-letter strings

Java statements that build a tree and then display some of its characteristics:
Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Expression Trees

FIGURE 24-15 Expression trees for four algebraic expressions

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Expression Trees
Algorithm evaluate(expressionTree)
if (expressionTree is empty)
return 0
else
{
firstOperand = evaluate(left subtree of expressionTree)
secondOperand = evaluate(right subtree of expressionTree)
operator = the root of expressionTree
return the result of the operation operator and its operands firstOperand
and secondOperand
}

Algorithm for postorder traversal of an expression tree.

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Binary Search Tree
• For each node in a binary search tree
– Node’s data is greater than all data in node’s left subtree
– Node’s data is less than all data in node’s right subtree
• Every node in a binary search tree is the root of a binary
search tree

FIGURE 24-19 A binary search tree of names

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Binary Search Tree

FIGURE 24-20 Two binary search trees containing the same data as
the tree in Figure 24-19
Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Binary Search Tree
Algorithm bstSearch(binarySearchTree, desiredObject)
// Searches a binary search tree for a given object.
//Returns true if the object is found.
if (binarySearchTree is empty)
return false
else if (desiredObject == object in the root of binarySearchTree)
return true
else if (desiredObject < object in the root of binarySearchTree)
return bstSearch(left subtree of binarySearchTree, desiredObject)
else
return bstSearch(right subtree of binarySearchTree, desiredObject)

Pseudocode for recursive search algorithm

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Binary Search Tree
• Efficiency of a search
– Searching a binary search tree of height h is O(h)
• To make searching a binary search tree efficient:
– Tree must be as short as possible.

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Heaps
• Complete binary tree whose nodes contain Comparable
objects and are organized as follows:
– Each node contains an object no smaller/larger than
objects in its descendants
– Maxheap: object in node greater than or equal to its
descendant objects
– Minheap: object in node less than or equal to its
descendant objects

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Heaps

FIGURE 24-21 Two heaps that contain the same values

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
Heaps
/** An interface for the ADT maxheap. */
public interface MaxHeapInterface<T extends Comparable<? super T>>
{
/** Adds a new entry to this heap.
@param newEntry An object to be added. */
public void add(T newEntry);

/** Removes and returns the largest item in this heap.

@return Either the largest object in the heap or,
if the heap is empty before the operation, null. */
public T removeMax();

/** Retrieves the largest item in this heap.

@return Either the largest object in the heap or,
if the heap is empty, null. */
public T getMax();

/** Detects whether this heap is empty.

@return True if the heap is empty, or false otherwise. */
public boolean isEmpty();

/** Gets the size of this heap.

@return The number of entries currently in the heap. */
public int getSize();

/** Removes all entries from this heap. */

public void clear();
} // end MaxHeapInterface
LISTING 24-6 An interface for a maxheap
Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved
End

Chapter 24

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved