Transcript Ch26v2.0

Tree
Implementations
Chapter 26
Slides by Steve Armstrong
LeTourneau University
Longview, TX
2007, Prentice Hall
Chapter Contents
• The Nodes in a Binary Tree
 An Interface for a Node
 An implementation of BinaryNode
• An Implementation of the ADT Binary Tree
 Creating a Basic Binary Tree
 The Method privateSetTree
 Accessor and Mutator Methods
 Computing the Height and Counting Nodes
 Traversals
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Chapter Contents
• An Implementation of an Expression Tree
• General Trees
 A Node for a General Tree
 Using a Binary Tree for Represent a General
Tree
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Nodes in a Binary Tree
Fig. 26-1 A node in a binary tree.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Interface for a Node
• View interface for class of nodes suitable
for a binary tree
• View implementation of BinaryNode
• Usually the class that represents a node in
a tree is a detail hidden from the client
• It is placed within a package
 Makes it available
 Available to all classes involved in
implementation of a tree
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
An Implementation of the ADT
Binary Tree
• Recall interface for class of binary trees
from previous chapter
• In that interface
 TreeInterface specifies basic
operations common to all trees
 TreeInteratorInterface specifies
operations for tree traversal
• View implementation of BinaryTree,
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Method privateSetTree
• Problem: previous implementation of
privateSetTree not sufficient
• Given: treeA.setTree(a, treeB, treeC);
 Now treeA shares nodes with treeB, treeC
 Changes to treeB also affect treeA (Fig. 26-2)
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Method privateSetTree
• Possible solution
 Have privatSetTree copy the nodes in
TreeB and TreeC
• Now treeA is separate and distinct from
treeB and treeC
 Changes to either treeB or treeC do NOT
affect treeA
• Note that copying nodes is expensive
 Other solutions are considered
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Method privateSetTree
• Another possible solution for
treeA.setTree(a, treeB, treeC);
 Have privateSetTree first link the root node of
treeA to root nodes of treeB, treeC (Fig. 26-3)
 Then set treeB.root, treeC.root to null
This still has some
problems
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Method privateSetTree
View second solution which does the following:
1. Create root node r for containing the data
2. If left subtree exists, not empty

Attach root node to r as left child
If right subtree exists, not empty, distinct from
left subtree
3.


Attach root node r as right child
If right, left subtrees are the same, attach copy of
right subtree to r instead
If left (right) subtree exists, different from the
invoking tree object
4.

Set its data field root to null
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Accessor, Mutator Methods
• View detail of methods implemented
 getRootData
 isEmpty
 clear
 setRootData
 setRootNode
 getRootNode
 BinaryNodeInterface
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Computing Height, Counting Nodes
• Within BinaryTree – view methods in
context
 getHeight()
 getNumberOfNodes()
• Within BinaryNode – view methods in
context
 getHeight()
 getHeight(BinaryNode node)
 getNumberOfNodes()
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Traversals
• Make recursive method private
 Call from public method with no parameters
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Traversals
Fig. 26-4 A binary tree.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Traversals
Fig. 26-5 Using a stack to perform an
inorder traversal of the binary tree
Click to view iterative
implementation of
inorderTraverse
Click to view inorder
traversal as an iterator
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Traversals
Fig. 26-6 Using a stack to traverse
the binary tree in (a) preorder
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Traversals
Fig. 26-6 Using a stack to traverse the
binary tree in (b) postorder.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Traversals
Fig. 26-7
Using a queue
to traverse the
binary tree in
level order.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Implementation of an Expression Tree
• Defining an interface for an expression
tree
 Extend the interface for a binary tree
 Add a declaration for the method evaluate
 View ExpressionTreeInterface
• An expression tree is a binary tree
 Implement evaluate in derived class
 Note source code for ExpressionTree
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
General Trees
Fig. 26-8 A node for a general tree.
Click to view interface
for node in general tree
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using a Binary Tree to Represent a
General Tree
Fig. 26-9 (a) A general tree;
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using a Binary Tree to Represent a
General Tree
Fig. 26-9 (b) an equivalent binary tree;
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using a Binary Tree to Represent a
General Tree
Fig. 26-9 (c) a more
conventional view
of the same binary tree.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Traversals
• Traversals of general tree in 26-9a
 Preorder: A B E F C G H I D J
 Postorder: E F B G H I C J D A
 Level order: A B C D E F G H I J
• Traversals of binary tree in 26-9c
 Preorder: A B E F C G H I D J
 Postorder: F E I H G J D C B A
 Level order: A B E C F G D H J I
 Inorder: E F B G H I C J D A
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X