Bài giảng Cấu trúc dữ liệu_ Phần Tree

Chapter 12
Trees
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-2
Chapter Objectives

Define trees as data structures
Define the terms associated with trees
Discuss the possible implementations of trees
Analyze tree implementations of collections
Discuss methods for traversing trees
Examine a binary tree example

Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-3
Trees
A Tree is a non-linear structure defined by the concept that each node in the tree, other than the first node or root node, has exactly one parent

For trees, the operations are dependent upon the type of tree and it’s use
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-4
Definitions
In order to discuss trees, we must first have a common vocabulary

We have already introduced a couple of terms:
node which refers to a location in the tree where an element is stored, and
root which refers to the node at the base of the tree or the one node in the tree that does not have a parent
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-5
Definitions
Each node of the tree points to the nodes that are directly beneath it in the tree

These nodes are referred to as its children

A child of a child is then called a grandchild, a child of a grandchild called a great-grandchild

A node that does not have at least one child is called a leaf

A node that is not the root and has at least one child is called an internal node
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-6
FIGURE 12.1 Tree terminology
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-7
Definitions
Any node below another node and on a path from that node is called a descendant of that node

Any node above another node on a connecting path from the root to that node is called an ancestor of that node

All children of the same node are called siblings

A tree that limits each node to no more than n children is called an n-ary tree
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-8
Definitions
Each node of the tree is at a specific level or depth within the tree

The level of a node is the length of the path from the root to the node

This pathlength is determined by counting the number of links that must be followed to get from the root to the node

The root is considered to be level 0, the children of the root are at level 1, the grandchildren of the root are at level 2, and so on
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-9
Definitions
The height or order of a tree is the length of the longest path from the root to a leaf

Thus the height or order of the tree in the next slide is 3

The path from the root (A) to leaf (F) is of length 3

The path from the root (A) to leaf (C) is of length 1
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-10
FIGURE 12.2 Path length and level
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-11
Definitions
A tree is considered to be balanced if all of the leaves of the tree are at roughly the same depth

While the use of the term “roughly” may not be intellectually satisfying, the actual definition is dependent upon the algorithm being used

Some algorithms define balanced as all of the leaves being at level h or h-1 where h is the height of the tree (where h = logNn for an N-ary tree)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-12
FIGURE 12.3 Balanced
and unbalanced trees
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-13
Definitions
The concept of a complete tree is related to the balance of a tree

A tree is considered complete if it is balanced and all of the leaves at level h are on the left side of the tree

While a seemingly arbitrary concept, as we will discuss in later chapters, this definition has implications for how the tree is stored in certain implementations

Trees a and c on the next slide are complete while tree b is not
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-14
FIGURE 12.4 Some complete trees
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-15
Implementing Trees with Links
While it is not possible to discuss the details of an implementation of a tree without defining the type of tree and its use, we can look at general strategies for implementing trees

The most obvious implementation of tree is a linked structure

Each node could be defined as a TreeNode class, as we did with the LinearNode class for linked lists
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-16
Implementing Trees with Links
Each node would contain a pointer to the element to be stored in that node as well as pointers for each of the possible children of the node

Depending on the implementation, it may also be useful to store a pointer in each node to its parent
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-17
Implementing Trees with Arrays
For certain types of trees, specifically binary trees, a computational strategy can be used for storing a tree using an array

For any element stored in position n of the array, that elements left child will be stored in position ((2*n) + 1) and that elements right child will be stored in position (2*(n+1))
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-18
Implementing Trees with Arrays
This strategy can be managed in terms of capacity in much the same way that we did for other array-based collections

Despite the conceptual elegance of this solution, it is not without drawbacks

For example, if the tree that we are storing is not complete or relatively complete, we may be wasting large amounts of memory allocated in the array for positions of the tree that do not contain data
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-19
FIGURE 12.5 Computational strategy
for array implementation of trees
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-20
Implementing Trees with Arrays
A second possible array implementation of trees is modeled after the way operating systems manage memory

Instead of assigning elements of the tree to array position by location in the tree, array positions are allocated contiguously on a first come first served basis

Each element of the array will be a node class similar to the TreeNode class that we discussed earlier
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-21
Implementing Trees with Arrays
However, instead of storing object reference variables as pointers to its children (and perhaps its parent), each node would store the array index of each child (and perhaps its parent)

This approach allows elements to be stored contiguously in the array so that space is not wasted

However, this approach increases the overhead for deleting elements in the tree since either remaining elements will have to be shifted to maintain contiguity or a free-list will have to be maintained
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-22
FIGURE 12.6 Simulated link strategy for array implementation of trees
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-23
Analysis of Trees
Trees are a useful and efficient way to implement other collections
In our analysis of list implementations in Chapter 8, we described the find operation as expected case n/2 or O(n)
However, if we implemented an ordered list using a balanced binary search tree, a binary tree with the added property that the left child is always less than the parent which is always less than or equal to the right child, then we could improve the efficiency of the find operation to O(log n)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-24
Analysis of Trees
This is due to the fact that the height or order of such a tree will always be log2n where n is the number of elements in the tree
This is very similar to our discussion of binary search in Chapter 11
In fact, for any balanced N-ary tree with n elements, the tree’s height will be logNn
With the added ordering property of a binary search tree, you are guaranteed to at worst search one path from the root to a leaf
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-25
Tree Traversals
There are four basic algorithms for traversing a tree:
Preorder traversal
Inorder traversal
Postorder traversal
Levelorder traversal
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-26
Preorder traversal
Preorder traversal is accomplished by visiting each node, followed by its children, starting with the root
Given the complete binary tree on the next slide, a preorder traversal would produce the order:
A B D E C
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-27
FIGURE 12.7 A complete tree
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-28
Preorder traversal
Stated in pseudocode, the algorithm for a preorder traversal of a binary tree is:

Visit node
Traverse(left child)
Traverse(right child)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-29
Inorder traversal
Inorder traversal is accomplished by visiting the left child of the node, then the node, then any remaining child nodes starting with the root
An inorder traversal of the previous tree produces the order:
D B E A C
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-30
Inorder traversal
Stated in pseudocode, the algorithm for an inorder traversal of a binary tree is:

Traverse(left child)
Visit node
Traverse(right child)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-31
Postorder traversal
Postorder traversal is accomplished by visiting the children, then the node starting with the root
Given the same tree, a postorder traversal produces the following order:
D E B C A
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-32
Postorder traversal
Stated in pseudocode, the algorithm for a postorder traversal of a binary tree is:


Traverse(left child)
Traverse(right child)
Visit node
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-33
Levelorder traversal
Levelorder traversal is accomplished by visiting all of the nodes at each level, one level at at time, starting with the root
Given the same tree, a levelorder traversal produces the order:
A B C D E
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-34
Levelorder traversal
Stated in pseudocode, the algorithm for a preorder traversal of a binary tree is:
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-35
Implementing Binary Trees
As an example of possible implementations of trees, lets explore a simple implementation of a binary tree

Having specified that we are implementing a binary tree, we can identify a set of possible operations that would be common for all binary trees

Notice however, that other than the constructors, none of these operations add any elements to the tree

It is not possible to define an operation to add an element to the tree until we know more about how the tree is to be used
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-36
FIGURE 12.8
The operations on a binary tree
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-37
FIGURE 12.9 UML description
of the BinaryTreeADT interface
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-38
Listing 12.1
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-39
Listing 12.1 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-40
Listing 12.1 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-41
LinkedBinaryTree
Lets examine a linked implementation of a binary tree
Our implementation will need to keep track of the node that is the root of the tree as well as the count of elements in the tree
protected int count;
protected BinaryTreeNode root;
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-42
LinkedBinaryTree
We will provide three constructors
One to create a null tree
One to create a tree containing a single element
One to create a new tree with the given element at the root and combining two existing trees
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-43
LinkedBinaryTree - constructors
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-44
LinkedBinaryTree - constructors
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-45
The BinaryTreeNode Class
We will also need a class to represent each node in the tree
Since this is a binary tree, we will create a BinaryTreeNode class that contain a reference to the element stored in the node as well as references for each of the children
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-46
Listing 12.2
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-47
Listing 12.2 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-48
Listing 12.2 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-49
The LinkedBinaryTree Class
Lets examine some of the methods of the LinkedBinaryTree Class
Keep in mind that each node of a tree represents a sub-tree
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-50
The removeLeftSubtree Method
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-51
The find and findagain Methods
The find method provides an excellent example of the recursion that is possible given the nature of a tree

We use the private method findagain to support the public find method

This allows us to distinguish between the original invocation of the method and the recursive calls
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-52
The find Method
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-53
The findagain Method
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-54
The iteratorInOrder Method
Like the find method, the iteratorInOrder method uses a private method, inorder, to support recursion

The traversals for a tree might be implemented as toString methods or iterators or both
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-55
The iteratorInOrder Method
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-56
The inorder Method
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-57
Expression Trees
Now lets look at an example using a binary tree

In Chapter 6, we used a stack to evaluate postfix expressions

Now we modify that algorithm to construct an expression tree
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-58
FIGURE 12.10
An example expression tree
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-59
Expression Trees
Our expression tree class will extend our LinkedBinaryTree class

This class provides constructors that reference the constructors of the LinkedBinaryTree class

The class also provides an evaluate method to recursively evaluate an expression tree once it has been constructed

The ExpressionTreeObj class represents the expression tree objects to be stored in the binary tree
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-60
Listing 12.3
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-61
Listing 12.3 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-62
Listing 12.3 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-63
Listing 12.3 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-64
Listing 12.3 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-65
Listing 12.4
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-66
Listing 12.4 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-67
Listing 12.4 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-68
Listing 12.4 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-69
FIGURE 12.11 Building an Expression Tree from a postfix expression
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-70
The Postfix and PostfixEvaluator Classes
The Postfix and PostfixEvaluator classes are modifications of those presented in chapter 6

The solve method of the PostfixEvaluator class uses a pair of stacks to create an expression tree from a valid post-fix expression

It then outputs the result using the evaluate method of the ExpressionTree class
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-71
Listing 12.5
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-72
Listing 12.6
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-73
Listing 12.6 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-74
Listing 12.6 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-75
Listing 12.6 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-76
Listing 12.6 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-77
Listing 12.6 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
12-78
FIGURE 12.12
UML description of the Postfix example