You should try to avoid them as much as possible.
Global variables come in two forms: those everyone can see and those only one function can see. Here are the global variables found in your program:
static int preIndex = 0;
The first two really belong to main(). It is where they first gain value and last have it.
The last one is, yes, also a form of global variable with restricted visibility. In this case, it is a crutch for maintaining state between function calls. Make it an argument instead.
Struct in C and C++
In C, a structure type name gets its own section in the compiler’s symbol table. In order to use it, you must signal to the compiler that you want a ‘struct’ name and not a normal type name by using the keyword struct
In C++, that still happens, but the name is added to both
symbol tables. So you no longer need
to type “struct” before a structure type name.
A lot of these errors would be caught if you crank up your compiler’s warning level to maximum. It may seem opprobrious at first, but it really does help you to find and repair errors in your code.
Google around your IDE+compiler combination for increasing the warning level.
C-string vs std::string
In C, strings are just arrays of characters. To find the declared
(that is, actual amount of memory taken up by the array), use the sizeof
That is not what you want, though. You want the number of characters used
in the array. That is what std::strlen()
You have one other potential problem: overflow. Your two arrays can store at maximum only nine
characters entered by the user (9 + 1 for the '\0'
value at the end of the string = 10 characters of available space).
Using the stream extraction operator on a char*
is just as dangerous as using std::gets()
— the computer will be happy to add characters to the end of the string as long as there is input, even if it is adding way past
the actual space available.
Granted, C++ could have easily fixed this problem, but the die is currently cast...
You should instead use a bounded input function, such as:
cin.getline( preorder, sizeof(preorder) );
cin.getline( inorder, sizeof(inorder) );
(You could also consider making both arrays a bit larger, say 50 elements or so.)
The other option is to just use a std::string
string preorder, inorder;
cin >> preorder >> inorder;
You are guaranteed there will be no bounds/overflow failures. You can then use the data as before, since a std::string is a managed character array:
node* root = buildTree(inorder.c_str(), preorder.c_str(), 0, inorder.size() - 1);
The only thing you would have to do is change all the
— which is fine since buildTree()
never attempts to modify the strings.
Dynamic Memory Management
Whenever you create something you must destroy it. That is, for every malloc()
there must be a free()
I suspect you were endeavoring to do something with
to free stuff. Don’t do that.
Pointers are special. An no matter what you read anywhere, you really should avoid simply writing zeros across all bytes of a pointer. See, the value of a zero pointer might not actually be zero
. So whenever you have to initialize a pointer variable, assign it a nullptr
directly, even in structs.
foozle* createFoozle( int x )
foozle* fooz = new foozle;
fooz->next = nullptr;
fooz->x = x;
or some other thing is technically a no-no, even though so much code on PC systems does it.
Having allocated memory from the dynamic store you must give it up at some point. For a linked tree like yours (or a linked list like foozle), it is entirely likely that left
) will point to data that also needs to be freed.
This is where you need a procedure to clean up. I have added a function shell to your code which you can fill out to do the cleanup. Remember, it may call itself to free children of the argument node. (Hint hint!)
Overflow and Undefined Behavior
As already mentioned above, attempts to access memory beyond the bounds of an array is not guaranteed to do anything benign. The first potential problem is where you read the input strings. The second is in the indices to your buildTree()
algorithm. What you have currently works, but not because it is doing exactly what you think it is.
It might be worth your time to trace through the function for the given input strings. Keep track of where each index points as you follow the code, line-by-line.
You might also check your algorithm against invalid input, like:
It should fail gracefully — return nothing or an error message. (Check your assignment for any instructions regarding invalid input.)
I hope not to sound rude or condescending — it is clear you have cobbled this together from several sources. (The BFS was clearly not written by you.) I hope you have taken the time to understand what is going on at each step.
The fact that you have gotten so close helps me to believe that you are competently approaching the problem.
Hope this helps.