1 /*
2 *_________________________________________________________________________*
3 * POEMS: PARALLELIZABLE OPEN SOURCE EFFICIENT MULTIBODY SOFTWARE *
4 * DESCRIPTION: SEE READ-ME *
5 * FILE NAME: poemsnodelib.h *
6 * AUTHORS: See Author List *
7 * GRANTS: See Grants List *
8 * COPYRIGHT: (C) 2005 by Authors as listed in Author's List *
9 * LICENSE: Please see License Agreement *
10 * DOWNLOAD: Free at www.rpi.edu/~anderk5 *
11 * ADMINISTRATOR: Prof. Kurt Anderson *
12 * Computational Dynamics Lab *
13 * Rensselaer Polytechnic Institute *
14 * 110 8th St. Troy NY 12180 *
15 * CONTACT: anderk5@rpi.edu *
16 *_________________________________________________________________________*/
17
18 #ifndef NODELIB_H
19 #define NODELIB_H
20
21 #include <iostream>
22
23 using namespace std;
24
25
26 TreeNode *GetTreeNode(int item,TreeNode *lptr = nullptr,TreeNode *rptr =nullptr);
27
28 void FreeTreeNode(TreeNode *p);
29
30 void Postorder(TreeNode *t, void visit(TreeNode* &t));
31
32 void Preorder (TreeNode *t, void visit(TreeNode* &t));
33
34 void CountLeaf (TreeNode *t, int& count);
35
36 int Depth (TreeNode *t);
37
38 void IndentBlanks(int num);
39
40 void PrintTree (TreeNode *t, int level);
41
42
43 // ---------------- Global functions-----------------//
44
45 // postorder recursive scan of the nodes in a tree
Postorder(TreeNode * t,void visit (TreeNode * & t))46 void Postorder (TreeNode *t, void visit(TreeNode* &t))
47 {
48 // the recursive scan terminates on a empty subtree
49 if (t != nullptr)
50 {
51 Postorder(t->Left(), visit); // descend left
52 Postorder(t->Right(), visit); // descend right
53 visit(t); // visit the node
54 }
55 }
56
57
58 // preorder recursive scan of the nodes in a tree
Preorder(TreeNode * t,void visit (TreeNode * & t))59 void Preorder (TreeNode *t, void visit(TreeNode* &t))
60 {
61 // the recursive scan terminates on a empty subtree
62 if (t != nullptr)
63 {
64 visit(t); // visit the node
65 Preorder(t->Left(), visit); // descend left
66 Preorder(t->Right(), visit); // descend right
67 }
68 }
69
70
71 //create TreeNode object with pointer fields lptr and rptr
72 // The pointers have default value nullptr
GetTreeNode(int item,TreeNode * lptr,TreeNode * rptr)73 TreeNode *GetTreeNode(int item,TreeNode *lptr,TreeNode *rptr)
74 {
75 TreeNode *p;
76
77 // call new to allocate the new node
78 // pass parameters lptr and rptr to the function
79 p = new TreeNode(item, lptr, rptr);
80
81 // if insufficient memory, terminatewith an error message
82 if (p == nullptr)
83 {
84 cerr << "Memory allocation failure!\n";
85 exit(1);
86 }
87
88 // return the pointer to the system generated memory
89 return p;
90 }
91
92
93 // deallocate dynamic memory associated with the node
94
FreeTreeNode(TreeNode * p)95 void FreeTreeNode(TreeNode *p)
96 {
97 delete p;
98 }
99
100
101 // the function uses the postorder scan. a visit
102 // tests whether the node is a leaf node
CountLeaf(TreeNode * t,int & count)103 void CountLeaf (TreeNode *t, int& count)
104 {
105 //use postorder descent
106 if(t !=nullptr)
107 {
108 CountLeaf(t->Left(), count); // descend left
109 CountLeaf(t->Right(), count); // descend right
110
111 // check if node t is a leaf node (no descendants)
112 // if so, increment the variable count
113 if (t->Left() == nullptr && t->Right() == nullptr)
114 count++;
115 }
116 }
117
118
119 // the function uses the postorder scan. it computes the
120 // depth of the left and right subtrees of a node and
121 // returns the depth as 1 + max(depthLeft,depthRight).
122 // the depth of an empty tree is -1
Depth(TreeNode * t)123 int Depth (TreeNode *t)
124 {
125 int depthLeft, depthRight, depthval;
126
127 if (t == nullptr)
128 depthval = -1;
129 else
130 {
131 depthLeft = Depth(t->Left());
132 depthRight = Depth(t->Right());
133 depthval = 1+(depthLeft > depthRight?depthLeft:depthRight);
134 }
135 return depthval;
136 }
137
IndentBlanks(int num)138 void IndentBlanks(int num)
139 {
140 // const int indentblock = 6;
141
142 for(int i = 0; i < num; i++)
143 cout << " ";
144 }
145
PrintTree(TreeNode * t,int level)146 void PrintTree (TreeNode *t, int level)
147 {
148 //print tree with root t, as long as t!=nullptr
149 if (t != nullptr)
150 {
151 int indentUnit = 5;
152 // print right branch of tree t
153 PrintTree(t->Right(),level + 1);
154 // indent to current level; output node data
155 IndentBlanks(indentUnit*level);
156 cout << t->GetData() << endl;
157 // print left branch of tree t
158 PrintTree(t->Left(),level + 1);
159 }
160 }
161 #endif
162
163