I'm writing a binary tree program to do the following actions:
a. Print out the tree in inorder
b. Print out the tree in preorder.
c. Print out the tree in postorder.
d. Print out the number of nodes in the tree. (Traverse the tree and count the nodes)
e. Sum up all the values in the tree and computer the average.
f. Count the number of leafs in the tree.
g. Print the value that is the deepest in the tree.
Here's the input file data I must use in the program:
75 97 82 47 90 59 23 51 36 110 66 102 69 79 13 130 49 41 19 67 85 64 115 30 94
The program runs perfectly but only reads in the 1st number. This is the output I get(I added the bold to stand out in this post):
In-Order:
75
Pre-Order:
75
Post-Order:
75
There are 1 nodes in this program.
The average of your input is 75.
The binary tree contains 1 leaves.
The deepest value in this program is 1
Process returned 0 (0x0) execution time : 0.030 s
Press any key to continue.
Also, the DeepVal function in my program can find the depth of the tree but I can't find how to make it say what value is the deepest. Can you help me?
Here's my source code:
#include <iostream>
#include <fstream>
using namespace std;
struct Tree
{
int N;
Tree *Rchild;
Tree *Lchild;
};
Tree *RT;
Tree *NewNode();
void Insert(Tree *c, int N);
void InOrder(Tree *ptr);
void PreOrder(Tree *R);
void PostOrder(Tree *Pr);
int NodeNum(Tree *Node);
int TreeAvg(Tree *ND);
int LeafCount(Tree *root);
int DeepVal(Tree *ro);
ifstream inputFile;
int main()
{
inputFile.open("TreeData.txt");
while (!inputFile.eof())
{
int H;
inputFile >> H;
Insert(RT, H);
}
cout << "In-Order:" << endl;
InOrder(RT);
cout << endl;
cout << "Pre-Order:" << endl;
PreOrder(RT);
cout << endl;
cout << "Post-Order:" << endl;
PostOrder(RT);
cout << endl;
cout << "There are " << NodeNum(RT) << " nodes in this program." << endl << endl;
cout << "The average of your input is " << TreeAvg(RT) << "." << endl << endl;
cout << "The binary tree contains " << LeafCount(RT) << " leaves." << endl << endl;
cout << "The deepest value in this program is " << DeepVal(RT) << endl << endl;
inputFile.close();
return 0;
}
Tree *NewNode()
{
Tree *temp;
temp = new Tree();
temp->N = 0;
temp->Lchild = NULL;
temp->Rchild = NULL;
return temp;
}
void Insert(Tree *c, int Num)
{
if(c == NULL)
{
RT = NewNode();
RT->N = Num;
return;
}
Tree *p;
Tree *T;
p = NULL;
T = NULL;
while(c != NULL)
{
p = c;
if (Num < c->N)
{
c = c->Lchild;
}
else
{
c = c->Rchild;
}
}
if(Num < p-> N)
{
p->Lchild = T;
}
else
{
p->Rchild = T;
}
return;
}
void InOrder(Tree *ptr)
{
if (ptr == NULL)
{
return;
}
InOrder(ptr->Lchild);
cout << ptr->N << endl;
InOrder(ptr->Rchild);
return;
}
void PreOrder(Tree *R)
{
if (R == NULL)
{
return;
}
cout << R->N << endl;
PreOrder(R->Lchild);
PreOrder(R->Rchild);
return;
}
void PostOrder(Tree *Pr)
{
if (Pr == NULL)
{
return;
}
PostOrder(Pr->Lchild);
PostOrder(Pr->Rchild);
cout << Pr->N << endl;
return;
}
int NodeNum(Tree *Node)
{
if(Node != NULL)
{
return 1 + NodeNum(Node->Lchild) + NodeNum(Node->Rchild);
}
else
{
return 0;
}
}
int TreeAvg(Tree *ND)
{
if (ND == NULL)
{
return 0;
}
else
{
return (ND->N + TreeAvg(ND->Lchild) + TreeAvg(ND->Rchild)) / NodeNum(ND);
}
}
int LeafCount(Tree *root)
{
if(root == NULL)
{
return 0;
}
else if(root->Lchild == NULL && root->Rchild == NULL)
{
return 1;
}
else
{
return LeafCount(root->Lchild) + LeafCount(root->Rchild) + 1;
}
}
int DeepVal(Tree *ro)
{
if (ro == NULL)
{
return 0;
}
else
{
int lDepth = DeepVal(ro->Lchild);
int rDepth = DeepVal(ro->Rchild);
if(lDepth > rDepth)
{
return (lDepth + 1);
}
else
{
return (rDepth + 1);
}
}
}
