Binary Trees problem
Dec 11, 2012 at 5:43am UTC
I only need help with finding the maximum leaf level and the minimum leaf level. I got my code to print out something for them but I'm pretty sure it's not right. Please help. Thank you.
Here is the entire code. I have the min and max in the inorder function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
//=========================================================================================
//=========================================================================================
#include <iostream>
using namespace std;
const int nil = 0;
int oneChild = 0;
int twoChildren = 0;
int leafCount = 0;
int maxLeaf = 0;
int minLeaf = 0;
int height;
int level;
class treenode_type
{
public :
int info;
treenode_type *left;
treenode_type *right;
};
void setleft(int x);
void setright(int x);
void inorder(treenode_type *p);
void preorder(treenode_type *p);
void postorder(treenode_type *p);
treenode_type *p, *q, *root;
int number;
//============================================================================================
int main()
{
cout << "Enter first value: \n" ;
cin >> number;
cout << number << " is the root number\n" ;
root = new treenode_type;
(*root).info = number;
(*root).left = nil;
(*root).right = nil;
cout << "Enter 19 more values: \n" ;
cin >> number;
for (int j=0; j<7; j++)
{
p = root;
q = p;
while ((number != (*p).info) && (q != nil))
{
p = q;
if (number < (*p).info)
q = (*p).left;
else
q = (*p).right;
}
if (number == (*p).info)
cout << number << " is a duplicate \n" ;
else if (number < (*p).info)
{
setleft(number);
cout << number << " is a left child of " << (*p).info << "\n" ;
}
else
{
setright(number);
cout << number << " is a right child of " << (*p).info << "\n" ;
}
cin >> number;
}
cout << "The tree traversed INORDER is \n" ;
p = root;
level = -1;
inorder(p);
cout << endl << "Number of leaves in the tree are: " << leafCount << endl;
cout << "Number of nodes with one child: " << oneChild << endl;
cout << "Number of nodes with two children: " << twoChildren << endl;
cout << "Maximum leaf level = " << maxLeaf << endl;
cout << "Minimum leaf level = " << minLeaf << endl;
cout << "Height = " << height << endl;
if (height == minLeaf)
{
cout << "Balanced" << endl;
}
else
{
cout << "Not balanced" << endl;
}
cout << endl << "The tree traversed PREORDER is \n" ;
p = root;
preorder(p);
cout << endl << "The tree traversed POSTORDER is \n" ;
p = root;
postorder(p);
}
//=========================================================================================
void setleft (int x)
{
treenode_type *q;
q = new treenode_type;
(*q).info = x;
(*q).left = nil;
(*q).right = nil;
(*p).left = q;
}
//=========================================================================================
void setright (int x)
{
treenode_type *q;
q = new treenode_type;
(*q).info = x;
(*q).left = nil;
(*q).right = nil;
(*p).right = q;
}
//=========================================================================================
void inorder (treenode_type *r)
{
if (r != nil)
{
level = level + 1;
inorder((*r).left);
cout << (*r).info << " (Level " << level << ")" << "\n" ;
inorder((*r).right);
level = level - 1;
if (((*r).left != nil) && ((*r).right != nil))
{
twoChildren ++;
}
else if ((((*r).left == nil) && ((*r).right != nil)) || (((*r).left != nil) && ((*r).right == nil)))
{
oneChild ++;
}
else if (((*r).right == nil) && ((*r).left == nil))
{
leafCount ++;
maxLeaf = level + 1;
minLeaf = level -1;
}
height = maxLeaf;
}
}
//=========================================================================================
void preorder (treenode_type *r)
{
if (r != nil)
{
cout << (*r).info << "\n" ;
preorder((*r).left);
preorder((*r).right);
}
}
//=========================================================================================
void postorder (treenode_type *r)
{
if (r != nil)
{
postorder((*r).left);
postorder((*r).right);
cout << (*r).info << "\n" ;
}
}
Topic archived. No new replies allowed.