A linear collection, such as a LinkedList or ArrayList, allows us to scan the elements by using their position in the sequence. Because a binary tree is a nonlinear structure, a sequential scan by position is impossible, because there is no unambiguous meaning for the location of the "next element." At each node, we can select between the left and right child. If the left child is chosen, we proceed to the left subtree of the node. Once there, we have another decision to select the left or the right child of this child node. As the process continues, we move further and further from the starting node and have a backlog of unfinished tasks; namely, at each node, we need to visit the other child who was not initially selected. Without some organization, we face the possibility of skipping some of the nodes or accessing them multiple times. Fortunately, the recursive structure of a binary tree offers a variety of techniques that allow us to visit each node exactly once. The tree scan algorithms identify three tasks that must be carried out at each node in the tree. These tasks include visiting the node to perform some action and selecting each of the children for their own visit. The different scanning strategies depend on the order in which we perform the tasks.
In this section, we discuss the classical tree-scan algorithms. We begin by focusing on strategies that will ensure that the scan visit each node exactly once. A visit to a node simply accesses the value of the node; namely, the value of the nodeValue field.
Recursive Tree Traversals :
A binary tree is a recursive structure in which each node is specified by its value and its left and right subtrees. We use this structure to design a series of scanning algorithms that designate three separate tasks at each node. The tasks include visiting the node and performing some action(N) ; selecting the left child (L); and selecting the right child (R). Selecting the left child takes us to a node which is the root of a subtree. In effect, this is a recursive descent into the left subtree of the node. The same is true for selection of the right child. A chain of recursive descents terminate when we reach an empty tree. This is a stopping condition. The recursive step sets into motion a scan of nodes with the repetition of the same three tasks at each node. The order in which we perform the N, L and R tasks determines the different recursive scan algorithms :
Inorder Scan Algorithm :
The inorder scan of a binary tree specifies an L N R ordering of tasks at each node in the scan. In following the recursive structure of a tree, the scan contacts a node at the root of a subtree and then immediately departs into its left subtree (L). It returns to make the formal visit (N) and then departs into its right subtree (R).
Let us trace the inorder scan in detail for a simple example. Please check below character tree and we will use it to perform Inorder scan algorithm :
Assuming X is the name of the node, the labels Lx, Nx and Rx present the corresponding tasks :
* Lx : Select the left child and descend into the left subtree > "Go left to left child of X"
* Nx : Output the value of X > "Visit X."
* Rx : Select the right child and descend into the right subtree > "Go right to right child of X"
The scan begins at node A, the root of the tree. The following table lists the steps in the order of their execution. The table includes the name of current node, the task to perform, and a description of the outcome. After completing all of the specified operations at a node, the recursive process returns to the parent node and picks up with the unfinished tasks at that node :
Designing Scanning Methods :
The recursive tree-scan algorithms have relatively easy implementations as methods. They all follow a pattern. An if-else statement distinguishes the stopping condition and the recursive step. In a scan, the stopping condition occurs when it reaches an empty tree. The recursive step at each node involves the three tasks L, N and R. The action during a visit is specific to the particular application. The order in which tasks are performed determines the type of the scan. A TNode parameter t provides a reference to the current node, which represents the root of a subtree. The return type is void when the visit carries out a self-contained action. A return value is required when the visit acquires information that must be passed back to the parent. In some cases, information is acquired at the stopping condition (empty tree) and must be returned for use by a recursive step. Below is the implementation of recursive scan pattern : (Assuming an inorder scan (L N R))
The method inorderDisplay() returns a string that provides an inorder listing of the node values. It builds the string at each node that includes a listing of the order of visits in the left subtree, the node's own value, and the order of visits in the right subtree :
Iterative Level-Order Scan :
The recursive tree scans access elements by moving up and down through subtrees. Some application need to access elements by levels, with the root coming first (level 0), then the children of root (level 1), followed by the next generation (level 2) and so forth. For obvious reasons, the algorithm is called alevel-order scan. The character Tree illustrate the order of visit to the nodes :
A level-order scan is an iterative process that uses a queue as an intermediate storage collection. Initially, the root enters the queue. An iterative step involves popping a node from the queue, performing some actions with the node, and then pushing its children into the queue. Because siblings enter queue during a visit of their parent, the siblings (on the same level) will exit the queue in successive iterations.
The algorithm involves an initialization step and a while-loop that removes the nodes, level by level, from a queue. The loop terminates when the queue is empty. The initialization creates a queue and pushes the root node into the queue.
The static method levelorderDisplay() in the BinaryTree class traverses the nodes of a binary tree in level order and returns a string displaying the value of each node. The method has a TNode reference argument t that designates the starting node (root) of the scan. We use a LinkedQueue collection to store the nodes. Each element of the LinkedQueue is an object of type TNode
Supplement :
* [ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的走訪
沒有留言:
張貼留言