TREE
Linked lists, stacks and queues are linear data structures. A tree is a nonlinear, two-dimensional data structure. Tree nodes contain two or more links. trees whose nodes all contain two links (none, one or both of which may be null).
Basic TerminologyFor this discussion, refer to nodes A, B, C and D. The root node (node B) is
the first node in a tree. Each link in the root node refers to a child (nodes A and D). The
left child (node A) is the root node of the left subtree (which contains only node A), and
the right child (node D) is the root node of the right subtree (which contains nodes D and
C). The children of a given node are called siblings (e.g., nodes A and D are siblings). A node
with no children is a leaf node (e.g., nodes A and C are leaf nodes). Computer scientists
normally draw trees from the root node down—the opposite of how trees grow in nature.
A binary search tree (with no duplicate node values) has the characteristic that the values
in any left subtree are less than the value in its parent node, and the values in any right
subtree are greater than the value in its parent node. illustrates a binary search
tree with 9 values. Note that the shape of the binary search tree that corresponds to a set
of data can vary, depending on the order in which the values are inserted into the tree.
The program of creates a binary search tree and traverses it (i.e., walks
through all its nodes) three ways—using recursive inorder, preorder and postorder traversals. We explain these traversal algorithms shortly.
Code:
1 // TreeNode.h
2 // Template TreeNode class definition.
3 #ifndef TREENODE_H
4 #define TREENODE_H
5
6 // forward declaration of class Tree
7 template< typename NODETYPE > class Tree;
8
9 // TreeNode class-template definition
10 template< typename NODETYPE >
11 class TreeNode
12 {
13
14 public:
15 // constructor
16 TreeNode( const NODETYPE &d )
17 : leftPtr( 0 ), // pointer to left subtree
18 data( d ), // tree node data
19 rightPtr( 0 ) // pointer to right substree
20 {
21 // empty body
22 } // end TreeNode constructor
23
24 // return copy of node's data
25 NODETYPE getData() const
26 {
27 return data;
28 } // end getData function
29 private:
2 // Template TreeNode class definition.
3 #ifndef TREENODE_H
4 #define TREENODE_H
5
6 // forward declaration of class Tree
7 template< typename NODETYPE > class Tree;
8
9 // TreeNode class-template definition
10 template< typename NODETYPE >
11 class TreeNode
12 {
13
14 public:
15 // constructor
16 TreeNode( const NODETYPE &d )
17 : leftPtr( 0 ), // pointer to left subtree
18 data( d ), // tree node data
19 rightPtr( 0 ) // pointer to right substree
20 {
21 // empty body
22 } // end TreeNode constructor
23
24 // return copy of node's data
25 NODETYPE getData() const
26 {
27 return data;
28 } // end getData function
29 private:
30 TreeNode< NODETYPE > *leftPtr; // pointer to left subtree
31 NODETYPE data;
32 TreeNode< NODETYPE > *rightPtr; // pointer to right subtree
33 }; // end class TreeNode
34
35 #endif
34
35 #endif
0 Comments