程式扎記: [ Data Structures with Java ] Section 16.2 : Binary Tree Nodes

標籤

2011年3月9日 星期三

[ Data Structures with Java ] Section 16.2 : Binary Tree Nodes

Preface : 
A binary tree can have different implementations, depending on how you setup the links between a node and its children. An array can be used to store binary trees. Simple index calculations identify the children and the parent of each node. We develop array-based binary trees in Chapter 22. A more flexible implementation defines a node as an instance of the generic TNode class. A node contains three fields. One is the data value, called nodeValue, and the other two are the reference variables, left and right. The references are links that identify the left child and the right child of the node respectively. In the process, the references identify the left and right subtrees of the node. 
 
A reference field, such as left, has the value null to indicate that the node does not have a left child. This is equivalent to saying that the left subtree of the node is empty. Hence, a left node has both null left and a null right reference field. The root node defines an entry point into the binary tree. Below figure gives a abstract model of a binary tree, along with the corresponding representation with TNode objects. 
 

TNode Class : 
The generic TNode class has two constructors that create binary tree node objects. The first constructor takes an argument of generic type T, which initializes nodeValue field. The reference fields are set to null. The resulting object is a node with no children. A second constructor has three arguments that assign initial values to nodeValue field and the two reference fields. We use this constructor to create a parent node with links to its children. The instance variables in the TNode class are public. This simplifies their use when implementing binary tree classes and algorithms and does not violate the object-design principle of information hiding. Programmers use TNode object as building blocks in a binary tree class. A user relies on the class methods and doesn't directly access the low-level TNode objects. The following is a declaration of the TNode class : 

- TNode.java implementation :
  1. package DSwJ.S16;  
  2.   
  3. public class TNode {  
  4.     public T nodeValue;  
  5.     public TNode left, right;  
  6.       
  7.     public TNode(T item) {  
  8.         this(item, nullnull);  
  9.     }  
  10.       
  11.     public TNode(T item, TNode left, TNode right) {  
  12.         this.left = left;  
  13.         this.right = right;  
  14.         nodeValue = item;  
  15.     }  
  16. }  

Building a Binary Tree : 
A binary tree consists of a collection of TNode objects whose reference values specify links to their children. You build a binary tree one node at a time. The constructor with a single argument of generic type creates a leaf node. The constructor with three arguments creates an interior node. The nonnull reference values in the interior node provide links that attach the node to its children. Let us look at how you create child and parent nodes and link them as part of a larger binary tree. The following statements declare two TNode reference variables, p and q, and create nodes that store Integer values. Node q is created as a parent with a link to node p as its right children : 

  1. TNode p,q;  
  2. p = new TNode(8);  
  3. q = new TNode(4null, p); // q is a node with value 4 and p as a right child  
The resulting section of the tree is depicted in below figure : 
 

The Method buildTree() : 
As the previous example illustrates, building a binary tree by hand is a tedious process. Unfortunately, without algorithms to automate the process, we have no alternative. At the same time, we need some examples to illustrate the concepts in this chapter. To address this situation, we provide the static method buildTree() in the class BinaryTree. It can help you to build binary tree in order as complete binary tree : 

- BinaryTree.java : Method buildTree() implementation
  1. package DSwJ.S16;  
  2.   
  3. public class BinaryTree {  
  4.     protected static int getLevel(TNode root) {  
  5.         TNode tmp = root.left;  
  6.         int level=0;          
  7.         while(tmp!=null) {  
  8.             tmp = tmp.left;  
  9.             level++;  
  10.         }  
  11.         return level;  
  12.     }  
  13.       
  14.     protected static TNode searchNext(TNode node, int level) {  
  15.         if(level>0) {  
  16.             TNode tmp;  
  17.             if((tmp=searchNext(node.left, level-1))!=nullreturn tmp;  
  18.             else if((tmp=searchNext(node.right, level-1))!=nullreturn tmp;  
  19.             return null;  
  20.         } else if(level==0){  
  21.             if(node.left==null || node.right==null){  
  22.                 return node;  
  23.             }else  
  24.                 return null;  
  25.         } else {  
  26.             return node;  
  27.         }  
  28.     }  
  29.       
  30.     public static void buildTree(TNode root, T item) {  
  31.         System.out.println("Build tree("+getLevel(root)+")...");  
  32.         TNode tmp = searchNext(root, getLevel(root)-1);  
  33.         TNode newNode = new TNode(item);  
  34.         if(tmp==null) { //Build next level. From left to right  
  35.             tmp = root;  
  36.             while(tmp.left!=null) {  
  37.                 tmp = tmp.left;  
  38.             }  
  39.             System.out.println("\tBuild "+tmp.nodeValue+" left("+newNode.nodeValue+")...");  
  40.             tmp.left = newNode;  
  41.         }else if(tmp.left == null) {          
  42.             System.out.println("\tBuild "+tmp.nodeValue+" left("+newNode.nodeValue+")...");  
  43.             tmp.left = newNode;  
  44.         } else if(tmp.right==null){  
  45.             System.out.println("\tBuild "+tmp.nodeValue+" right("+newNode.nodeValue+")...");  
  46.             tmp.right = newNode;  
  47.         }   
  48.     }  
  49.       
  50.     public static void main(String args[]) {  
  51.         TNode root = new TNode('A');  
  52.         buildTree(root, 'B');  
  53.         buildTree(root, 'C');  
  54.         buildTree(root, 'D');  
  55.         buildTree(root, 'E');  
  56.         buildTree(root, 'F');  
  57.         System.out.println("Final Binary Tree Level="+getLevel(root));  
  58.     }  
  59. }  


Run :
Build tree(0)...
Build A left(B)...
Build tree(1)...
Build A right(C)...
Build tree(1)...
Build B left(D)...
Build tree(2)...
Build B right(E)...
Build tree(2)...
Build C left(F)...
Final Binary Tree Level=2

Supplement : 
* [ 資料結構 小學堂 ] 樹狀結構導論 : 樹 
* [ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的儲存方式

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!