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 :
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 :
- TNode
p,q; - p = new TNode
( 8); - q = new TNode
( 4, null, p); // q is a node with value 4 and p as a right child
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 :
Supplement :
* [ 資料結構 小學堂 ] 樹狀結構導論 : 樹
* [ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的儲存方式
沒有留言:
張貼留言