Binary Tree 2 Linked List

[DanielJohnson]

I am not asking any solution but please tell me why g++ compiler gives
me the following error. I am converting a Binary Tree to a Doubly
Linked List by using an inorder traversal and changing pointers.

btree struct looks like this

typedef struct btree{
struct btree* left;
int data;
struct btree* right;
} btree;

And this is my function, where I get the error from g++ compiler

btree* ConvertBinaryTree2LinkedList(btree* root){
btree *cursor = root;
btree *head = NULL; // return as first element of linked list
bool isLeftMost = true;
stack < btree* > S;
bool done = false;

// Iterative Inorder Traversal
while(!done){
if (cursor != NULL) {
S.push(cursor);
cursor=cursor->left;
if (isLeftMost) head = cursor;
}
else{
if(!S.empty()){
isLeftMost = false;
cursor = S.top();
S.pop();
cursor->right = S.top();
S.top()->left = cursor;
cursor = cursor->right;
}
else{
done = true;
}
}
}
return head;
}

BinaryTree2LinkedList.cpp: In function 'btree*
ConvertBinaryTree2LinkedList(btree*)':
BinaryTree2LinkedList.cpp:72: error: 'stack' was not declared in this
scope
BinaryTree2LinkedList.cpp:72: error: expected primary-expression
before '*' token
BinaryTree2LinkedList.cpp:72: error: expected primary-expression
before '>' token
BinaryTree2LinkedList.cpp:72: error: 'S' was not declared in this
scope


Please help to fix the error. Every help is appreciated.

 

[david]

Maybe you forgot to add: #include <stack> ?

 

[DanielJohnson]

Maybe you forgot to add: #include <stack>

I actually did.

 

[Jeff Schwab]

I am not asking any solution but please tell me why g++ compiler gives
me the following error. I am converting a Binary Tree to a Doubly
Linked List by using an inorder traversal and changing pointers.

btree struct looks like this

typedef struct btree{
struct btree* left;
int data;
struct btree* right;
} btree;

And this is my function, where I get the error from g++ compiler

btree* ConvertBinaryTree2LinkedList(btree* root){
btree *cursor = root;
btree *head = NULL; // return as first element of linked list
bool isLeftMost = true;
stack < btree* > S;
bool done = false;

// Iterative Inorder Traversal
while(!done){
if (cursor != NULL) {
S.push(cursor);
cursor=cursor->left;
if (isLeftMost) head = cursor;
}
else{
if(!S.empty()){
isLeftMost = false;
cursor = S.top();
S.pop();
cursor->right = S.top();
S.top()->left = cursor;
cursor = cursor->right;
}
else{
done = true;
}
}
}
return head;
}

BinaryTree2LinkedList.cpp: In function 'btree*
ConvertBinaryTree2LinkedList(btree*)':
BinaryTree2LinkedList.cpp:72: error: 'stack' was not declared in this
scope
BinaryTree2LinkedList.cpp:72: error: expected primary-expression
before '*' token
BinaryTree2LinkedList.cpp:72: error: expected primary-expression
before '>' token
BinaryTree2LinkedList.cpp:72: error: 'S' was not declared in this
scope


Please help to fix the error. Every help is appreciated.

Near the top of the file where ConvertBinaryTree2LinkedList is defined,
add the following header inclusion. Make sure the # is in the first
column of the file, i.e. all the way on the left:

#include <stack>

Inside ConvertBinaryTree2LinkedList, before any of the other code,
insert this using-declaration:

using std::stack;

There are some other issues with the code that you may want to know
about. These aren't wrong, but they show that you don't write a lot of
C++ code.

Below are four purely syntactic concerns. The first two, I don't think
anyone will argue about. The latter two may generate some debate, but
I'm going to give my own (firmly held) opinions.

(1) You don't need to typedef structs. You have:

typedef struct btree {
// ...
} btree;

This is correct in C, but in C++, the following
is usually preferred:

struct btree {
// ...
};

(2) It is usual to leave space before opening braces.
You have:

if (condition){

The following is more popular:

if (condition) {

The same is true for struct and class defintions,

(3) There is no need to use the macro NULL. C++ has a null
pointer literal: 0. Instead of:

btree* head = NULL:

Many people prefer:

btree* head = 0;

(4) There is no need to test whether a pointer != 0, since
non-null pointer values are implicitly converted to
"true" in the context of a boolean test. You have:

if (cursor != NULL) {

Many prefer:

if (cursor) {

 

[DanielJohnson]

Near the top of the file where ConvertBinaryTree2LinkedList is defined,
add the following header inclusion. Make sure the # is in the first
column of the file, i.e. all the way on the left:

#include <stack>

Inside ConvertBinaryTree2LinkedList, before any of the other code,
insert this using-declaration:

using std::stack;

There are some other issues with the code that you may want to know
about. These aren't wrong, but they show that you don't write a lot of
C++ code.

Below are four purely syntactic concerns. The first two, I don't think
anyone will argue about. The latter two may generate some debate, but
I'm going to give my own (firmly held) opinions.

(1) You don't need to typedef structs. You have:

typedef struct btree {
// ...
} btree;

This is correct in C, but in C++, the following
is usually preferred:

struct btree {
// ...
};

(2) It is usual to leave space before opening braces.
You have:

if (condition){

The following is more popular:

if (condition) {

The same is true for struct and class defintions,

(3) There is no need to use the macro NULL. C++ has a null
pointer literal: 0. Instead of:

btree* head = NULL:

Many people prefer:

btree* head = 0;

(4) There is no need to test whether a pointer != 0, since
non-null pointer values are implicitly converted to
"true" in the context of a boolean test. You have:

if (cursor != NULL) {

Many prefer:

if (cursor) {

Thank you for helpful tips. I could not compile the code but I have
few other logical errors which I am now going to work upon.

 

[James Kanze]

[...]

Near the top of the file where ConvertBinaryTree2LinkedList is defined,
add the following header inclusion. Make sure the # is in the first
column of the file, i.e. all the way on the left:

Why? It's usually considered good style to start include
directives in column 1, but you make it sound like there's more
too it (and of course, if the include is conditional, a lot of
people would indent it).

[...]

(2) It is usual to leave space before opening braces.
You have:

if (condition){

The following is more popular:

if (condition) {

The same is true for struct and class defintions,

Depending on who's writing the code, it might also be usual to
put the opening brace on a separate line. I write it like you
suggest, but I've also work in companies where the rule was no
space, and in other companies where the rule was to put the
opening brace on a line by itself. There's no consensus about
this, except for the rule that you should be consistent, and
always do it the same way.

(3) There is no need to use the macro NULL. C++ has a null
pointer literal: 0.

Readability. Almost all of the professionals I work with prefer
NULL---and I know I do.

Instead of:
btree* head = NULL:
Many people prefer:
btree* head = 0;

And many more don't. In this case, you know that 0 is actually
going to be used as a pointer---why do you want to hide that
fact from the reader. (Of course, if you don't care if anyone
can understand your code...)

(4) There is no need to test whether a pointer != 0, since
non-null pointer values are implicitly converted to
"true" in the context of a boolean test. You have:
if (cursor != NULL) {
Many prefer:
if (cursor) {

Every coding guideline I've ever seen bans that practice. A
pointer is not a boolean, even if the language (stupidly) allows
it to be converted to one. Just because a misfeature is present
doesn't mean you have to use it.

 

[Jeff Schwab]

[...]

Near the top of the file where ConvertBinaryTree2LinkedList is defined,
add the following header inclusion. Make sure the # is in the first
column of the file, i.e. all the way on the left:

Why? It's usually considered good style to start include
directives in column 1, but you make it sound like there's more
too it

As a purely practical matter, I seem to remember compilers (or
preprocessors) getting confused by it. Maybe I'm mistaken. As a
stylistic issue, I certainly dislike seeing the # indented.

(and of course, if the include is conditional, a lot of
people would indent it).

My preferred style is to indent the command, but not the pound sign:

#ifdef SOMETHING
# include <somefile>
#endif


What really makes my skin crawl is:

void some_func() {
# define MAX_LENGTH
int array[MAX_LENGTH];
// ...
}


I dislike the implication that preprocessor commands are in any way
subject to the scopes defined in the C++ code. Preprocessor commands
are markup.

[...]

(2) It is usual to leave space before opening braces.
You have:

if (condition){

The following is more popular:

if (condition) {

The same is true for struct and class defintions,

Depending on who's writing the code, it might also be usual to
put the opening brace on a separate line. I write it like you
suggest, but I've also work in companies where the rule was no
space, and in other companies where the rule was to put the
opening brace on a line by itself. There's no consensus about
this, except for the rule that you should be consistent, and
always do it the same way.

My preference is the One True Brace Style. Where I work now, the coding
guidelines say to put the brace on a separate line for function and
class definitions only. I haven't decided whether I like that; it may
make the code clearer, but it also makes the code a lot longer for those
of use who write lots of very small functions and classes.

Readability. Almost all of the professionals I work with prefer
NULL---and I know I do.

Ugh.

And many more don't. In this case, you know that 0 is actually
going to be used as a pointer---why do you want to hide that
fact from the reader.

It's not to hide the fact from the reader, but I see no reason to
specify the fact redundantly, especially via the preprocessor. I don't
find the NULL any clearer. I am in good company here, since this is also
Bjarne Stroustrup's opinion.

http://www.research.att.com/~bs/bs_faq2.html#null

To the greatest extent feasible, I try not to make the code depend on
the exact types being used. My own preference is actually:

template<
typename Tree =btree,
typename Tree_pointer =Tree*>
class some_class {

typedef Tree tree_type;
typedef Tree_pointer tree_pointer_type;

void method();

// ...
};

template<typename Tree, typename Tree_pointer>
void
some_class::method() {

tree_pointer_type tree = tree_pointer_type();

// Work with tree.
}

(Of course, if you don't care if anyone
can understand your code...)

There was no call for that kind of remark. I go to great lengths to
make my code as readable and usable by others as possible, and believe I
have been largely successful in that endeavor. I take pride in my work,
and I don't appreciate you bashing it, site unseen. This language is
important to me. Software quality is something I care about deeply. If
you feel the same way, then please recognize that smart, experienced
people will often disagree with each other. This does not in any way
imply that they are either malicious or apathetic.

Every coding guideline I've ever seen bans that practice. A
pointer is not a boolean, even if the language (stupidly) allows
it to be converted to one.

Clearly, whether a feature is "stupid" is a matter of opinion. Thanks
for sharing yours.

Just because a misfeature is present
doesn't mean you have to use it.

I don't think anyone has ever claimed otherwise. I don't consider this
to be a misfeature. I find the following clear and intuitive:

if (Object* object = get_object()) {
// Work with object.
}

The following, equivalent code is lengthier and, in my opinion, less
readable:

{
Object* object = get_object();

if (object != NULL) {
// Work with object.
}
}

Again, Bjarne agrees.