Binary Tree Issues

[nmcentire]

I have updated the code. I can get it to build a tree, yet the lnr (in order traversal) doesn't work. I've looked at several tutorials - even copy/pasted someone else's inorder traversal code and just changed the keywords around to fit mine and still it didn't work.

[code]#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
using namespace std;


// Typedef of prezname and node.
typedef char prezname[80];
typedef struct node *nref;
typedef struct node {prezname prez; node *left; node *right;};



/*******************Global Variables**************************/


prezname keyname;
node root;
nref where = NULL;
nref whereprev = NULL;
nref rootref = &root;
bool found;



/*******************Function Declarations*********************/
void search(prezname, nref);
void insertNode(prezname, nref &);
void lnr(nref);
/*******************Main Function*****************************/


void main()
{

nref p = NULL;

bool found = false;


ifstream fin("C:\\Prez.dat");


do{
fin.getline(keyname, 80);
p = &root;
if(found == false && p == NULL)
{
insertNode(keyname,p);
}
else if(found == false && p != NULL)
{
insertNode(keyname,p);
}
else if(found == true)
cout << endl << keyname << " is already in the tree!" << endl;

}while(!fin.eof());
fin.close();
cout << root.prez;
lnr(rootref);
cin.get();



}



/*****************************search***************************
* Used to search for a keyname. *
**************************************************************/


void search(prezname keyname, nref root)
{
nref p = root, pprev = NULL;


while(p != NULL && strcmp(keyname,p->prez) != 0)
{
pprev = p;

if(strcmp(keyname,p->prez) < 0)
{
p = p->left;

}
else if(strcmp(keyname,p->prez) > 0)
{
p = p->right;

}
else if(strcmp(keyname,p->prez) == 0)
{
found = true;
cout << keyname << " is already in the list!" << endl;
}
}

where = p;
whereprev = pprev;


}
/***************************insertNode****************************
* Used to insert a node into the tree *
*****************************************************************/

void insertNode(prezname keyname, nref &p)
{
search(keyname,p);

if(whereprev == NULL)
{
p = rootref;
strcpy(p->prez,keyname);
p->left = NULL;
p->right = NULL;
whereprev = NULL;
}
else
{

p = new node;
strcpy(p->prez,keyname);
p->left = NULL;
p->right = NULL;
if(strcmp(keyname,whereprev->prez) < 0)
{
whereprev->left = p;
}
else
{
whereprev->right = p;
}
}




}

/**************************lnr function****************************
* Traverses the tree by going left branch, node, right branch *
******************************************************************/

void lnr(nref p)
{
cout << "Starting LNR" << endl;
if(p != NULL)
{
cout << p->prez << endl;
lnr(p->left);
cout << p->prez;
lnr(p->right);
} else
cout << "p == NULL" << endl;
}

[Mal Reynolds]

i'm a little tired, but just glancing at your code, I believe that in line 72:
while(p != NULL && strcmp(keyname,p->prez) != 0),
even though a NULL root will invalidate the first condition, i'm pretty sure strcmp() still gets called, and if so, you are trying to access a data member of a structure that doesn't exist. also, it looks like your search function is non-recursive, meaning it will not be able to find anything that is not in the first node. notice that probably your biggest problem is that in your insertNode() function, you make a new node, set all of it's data... then never assign it anywhere. then when that function exits, you lose the pointer to it, and have no way to access that memory anymore! then in main, right after that, you print out that it has been inserted without ever checking if it really was. you also don't need the '&' in front of 'root' in the definition of your insertNode() function because you are not actually calling that function there. hope that helped

[firedraco]

No, it doesn't, the && operator short-circuits.

[Mal Reynolds]

thank you firedraco. so just to clarify, as i am interested, when using && or ||, and multiple expressions, they are evaluated left to right? so whichever you put first will be evaluated first?

[nmcentire]

I've updated the previous post including the code.

[firedraco]

@Mal: Yes, I believe they are operated left to right, with the following precedence rules: http://www.cppreference.com/wiki/operator_precedence

EX: A && B || C != A && (B || C) because && has a higher precedence then ||.

I'm pretty sure most of them short circuit, i.e. and returns false is left it false, or returns true if left is true, etc. Although if you overload them, they will NOT short circuit the same way, which can cause problems...

@nmcentire: I may be wrong, but I think:

fin.getline(keyname, 80); will read a line of "fin" until it reaches character 80 or the end of the file...you should leave the parameter blank (it defaults to the newline character for you)