Preface :
In the previous section, we developed the classic binary tree-scan algorithms and illustrated them with methods that simply display the values of the node. In this section, we want to apply the tree-scan techniques to develop algorithms where a visit involves some calculation or update action. For starters, we implement an algorithm that computes the height of a tree. Anticipating the construction of the binary search tree class, we develop algorithms that copy and delete nodes in a tree. We implement all of the algorithms as static methods in BinaryTree class.
Computing the Tree Height :
The height of a node is the length of the longest path in its subtrees. The height of the tree is the height of the root node. In Section 16.2, we showed how the recursive structure of a binary tree is used to compute the height of a node. Recall that the stopping condition is an empty tree, which has height -1. The height of each nonempty node uses the recursive step, where its height is one more than the maximum height of its subtrees. Assigning an empty tree the height -1 that a leaf node has height 0 :
Below figure illustrates the height for node B. The recursive condition computes the height to be 2, which is one more than the maximum height for the left child D (height 0) and the right child E (height 1). The height of the tree is 3 which is the height of the root node (A) :
An algorithm uses a recursive scan of the nodes to determine the height of a tree. In the previous section, we identified three types of recursive scan: preorder, inorder and postorder. These expand to six when you distinguish the order of descent (left or right) into the subtrees. Computing the height of a node requires information about the heights of the subtrees. You must evaluate the children before you evaluate the parent. This involves a postorder, or bottom-up, scan of the nodes. A method that implements the algorithm has a return value that passes the height of a node back to its parent. In a postorder scan, the root is the last node visited. The return value from the root is the height of the tree :
Copying a Binary Tree :
In many applications, a programmer wants to duplicates a tree structure. The duplicate configures nodes with the same parent-to-child relationships although the data might include additional information specific to the application. For instance, the duplicate tree may contain nodes that have an additional field that references the parent. The duplicate allows the programmer to scan up the tree along the path of parents. Below figure illustrates a copy of Tree0 where a parent field is added to the node. The parent is used to create the path D-B-A that moves from leaf node D up the tree to the root A :
We will now explore the tree copy algorithm for the simple case, where the copy is an exact duplicate of the original tree. Copying a tree requires a recursive scan of its nodes. At each recursive step, we want to create a duplicate of th node including the value and links to its children. Part of the task is easy. Simply create a new node using the operator new and a TNode constructor with the value of the node in the original tree as an argument. The problem lies with the links. The new node must have references "left" and "right" that point to its children. Each child is a duplicate node that was created at some prior recursive step in the scan. You will quickly understand the issue and the solution by tracking a few recursive steps in the algorithm.
Consider the character tree, Tree 0, which has five nodes. Assume that the TNode reference origRoot is the root of the tree. The method copyTree() builds a duplicate tree. The method takes origRoot as the argument, creates a second tree, which is a duplicate of Tree0, and returns a reference that identifies the root of the new tree. In the example, the new root is the TNode reference copyRoot.
A postorder scan of the original tree visits a node only after it visits both the left and the right subtrees. The postorder visit to the node has access to its children and thus to its two subtrees. In our case, the visit will use knowledge of subtrees and the value of the node to create a duplicate node in the copy tree. At each node t in the original tree, we use postorder scan to make a recursive call to copyTree() with argument t.left and then recursive call to copyTree() with argument t.right. The calls creates the duplicate left and right subtrees for the node and method return references to the roots of these subtrees. Assume the reference to the left subtree is newLeftNode and the reference to the right subtree is newRightNode. For the visit to node t, allocate a node whose value is t.nodeValue but whose subtrees are newLeftNode and newRightNode. The stopping condition for the recursive scan occurs when t == null ; that is, when the scan in the original tree reaches an empty tree. The return value in this case is null, which indicates that a similar empty tree will be created in the duplicate tree. Below is the implementation :
Clearing a Tree :
An application may want to use a tree as a temporary storage structure. When no longer needed, the memory should be released for other purpose, Setting the root to null is not sufficient since this only marks a single node for garbage collection. All of the nodes should be marked. This involves a recursive scan of the tree with the visit operation assigning the value null to the node reference. The effect is to deallocate the tree one node at a time.
A bottom-up scan ensures that the children are deleted before the parent is deleted. The method clearTree() takes a TNode reference t, which represents the root of a subtree and uses a postorder scan of the nodes. We include clearTree() as a static method in the BinrayTree class :
In the previous section, we developed the classic binary tree-scan algorithms and illustrated them with methods that simply display the values of the node. In this section, we want to apply the tree-scan techniques to develop algorithms where a visit involves some calculation or update action. For starters, we implement an algorithm that computes the height of a tree. Anticipating the construction of the binary search tree class, we develop algorithms that copy and delete nodes in a tree. We implement all of the algorithms as static methods in BinaryTree class.
Computing the Tree Height :
The height of a node is the length of the longest path in its subtrees. The height of the tree is the height of the root node. In Section 16.2, we showed how the recursive structure of a binary tree is used to compute the height of a node. Recall that the stopping condition is an empty tree, which has height -1. The height of each nonempty node uses the recursive step, where its height is one more than the maximum height of its subtrees. Assigning an empty tree the height -1 that a leaf node has height 0 :
Below figure illustrates the height for node B. The recursive condition computes the height to be 2, which is one more than the maximum height for the left child D (height 0) and the right child E (height 1). The height of the tree is 3 which is the height of the root node (A) :
An algorithm uses a recursive scan of the nodes to determine the height of a tree. In the previous section, we identified three types of recursive scan: preorder, inorder and postorder. These expand to six when you distinguish the order of descent (left or right) into the subtrees. Computing the height of a node requires information about the heights of the subtrees. You must evaluate the children before you evaluate the parent. This involves a postorder, or bottom-up, scan of the nodes. A method that implements the algorithm has a return value that passes the height of a node back to its parent. In a postorder scan, the root is the last node visited. The return value from the root is the height of the tree :
Copying a Binary Tree :
In many applications, a programmer wants to duplicates a tree structure. The duplicate configures nodes with the same parent-to-child relationships although the data might include additional information specific to the application. For instance, the duplicate tree may contain nodes that have an additional field that references the parent. The duplicate allows the programmer to scan up the tree along the path of parents. Below figure illustrates a copy of Tree0 where a parent field is added to the node. The parent is used to create the path D-B-A that moves from leaf node D up the tree to the root A :
We will now explore the tree copy algorithm for the simple case, where the copy is an exact duplicate of the original tree. Copying a tree requires a recursive scan of its nodes. At each recursive step, we want to create a duplicate of th node including the value and links to its children. Part of the task is easy. Simply create a new node using the operator new and a TNode constructor with the value of the node in the original tree as an argument. The problem lies with the links. The new node must have references "left" and "right" that point to its children. Each child is a duplicate node that was created at some prior recursive step in the scan. You will quickly understand the issue and the solution by tracking a few recursive steps in the algorithm.
Consider the character tree, Tree 0, which has five nodes. Assume that the TNode reference origRoot is the root of the tree. The method copyTree() builds a duplicate tree. The method takes origRoot as the argument, creates a second tree, which is a duplicate of Tree0, and returns a reference that identifies the root of the new tree. In the example, the new root is the TNode reference copyRoot.
A postorder scan of the original tree visits a node only after it visits both the left and the right subtrees. The postorder visit to the node has access to its children and thus to its two subtrees. In our case, the visit will use knowledge of subtrees and the value of the node to create a duplicate node in the copy tree. At each node t in the original tree, we use postorder scan to make a recursive call to copyTree() with argument t.left and then recursive call to copyTree() with argument t.right. The calls creates the duplicate left and right subtrees for the node and method return references to the roots of these subtrees. Assume the reference to the left subtree is newLeftNode and the reference to the right subtree is newRightNode. For the visit to node t, allocate a node whose value is t.nodeValue but whose subtrees are newLeftNode and newRightNode. The stopping condition for the recursive scan occurs when t == null ; that is, when the scan in the original tree reaches an empty tree. The return value in this case is null, which indicates that a similar empty tree will be created in the duplicate tree. Below is the implementation :
Clearing a Tree :
An application may want to use a tree as a temporary storage structure. When no longer needed, the memory should be released for other purpose, Setting the root to null is not sufficient since this only marks a single node for garbage collection. All of the nodes should be marked. This involves a recursive scan of the tree with the visit operation assigning the value null to the node reference. The effect is to deallocate the tree one node at a time.
A bottom-up scan ensures that the children are deleted before the parent is deleted. The method clearTree() takes a TNode reference t, which represents the root of a subtree and uses a postorder scan of the nodes. We include clearTree() as a static method in the BinrayTree class :
This message was edited 10 times. Last update was at 15/10/2010 16:19:55
沒有留言:
張貼留言