coding a complete binary tree with Dev-C++

[confusedmind]

ok, here are the questions.

QUESTION NO. 1:
I am asked to build a complete binary tree using linked list. According to my knowledge, you are not able to sort the tree with a complete binary tree otherwise it is impossible to get it complete. I searched thru google and I found no examples on building a CBT with linked list, only couple pages discuss about implementing using array which isn't what I am looking for.

Here is my code, I know it's not gonna work well but I really have no idea how to fix it. Please have a look:

void IntegerNode::insertNode( intNode *root, Item_type item )
// Modificaton Member Function
// PRE: root is a valid intNode pointer, value is a valid Item_type object
// POST: value is inserted to the original tree
{
    if ( root == NULL ) {
        root -> data = item;
        root -> right = root -> left = NULL;
        // size ++;
        // break;
    }
    else if ( root -> left = NULL ) {
        insertNode ( root -> left, item );
    }
    else if ( root -> right = NULL ) {
        insertNode ( root -> right, item );
    }
    else {
        insertNode ( root -> left, item );
        insertNode ( root -> right, item );
    }                
    size ++;

}

I hope the code is clear enough. Users can call the function with a node to the root and an integer which the user wanna insert. To make a tree complete, all nodes have to be added to the as left as possible. SO this tree wont care about the value of the integer, it basically finds the most appropriate slot and place the integer in. For the first three IF statement, I basically check the root itself and left and right pointer, and I believe that so far I am doing correct. The problem raises when tree contains more than 3 nodes, and now with my code, you can see that at the forth IF statement, the function recurrsively calls with left and right pointers, this will make it go thru every node and check if there is space for the new item, but this will eventually result the item inserted into EVERY LEAF! which isn't what I want, but I have no idea how to fix this. Anyone helps?

QUESTION NO.2:

In the same souce file, I have another few functions and Dev-C++ reports errors during the compilation and I have no idea how to fix them since the code looks so right.

In my .h file I have

    // the node to hold information
    struct intNode {
        Item_type data;
        intNode* left; // to the left child
        intNode* right; // to the right child
    };

and

    intNode* makenode ( Item_type item );

in the .cpp file, I implemented the code for the function makenode which has a return type of intNode pointer.

intNode* IntegerNode::makenode ( Item_type item )
// Access Member Function
// PRE: item is a valid Item_type object
// POST: A new intNode is created and the address is returned
{
    intNode *newNode = new intNode;
    newNode -> data = item;
    newNode -> left = intNode -> right = NULL;
    return newNode;
}    

It looks right but Dev-C++ always reports error like
"sybtax error before '*' token"
"sybtax error before '->" token"

lots thanks to those who reads this thread!!

[Stack Overflow]

Greetings,

I did notice a few typographical syntax errors, and a node system error. Let's start off with the syntax errors, as they are easy to fix.

insertNode()
Taking a look inside your insertNode code, you have a few if-else statements in there. These statements may result in faulty executions; see why:

else if ( root -> left = NULL ) {

As seen here, in red, your program will never check if root->left is "equal to" NULL. That's why C comes with equality operators. An equality operator is one that tests a condition such as "is less than", "is greater than", and "is equal to". Here is a closer look of equality operators:

[b][u]name[/u][/b] 	 	 	 	[b][u]symbol[/u][/b] 	[b][u]sample usage[/u][/b] 	 	 	[b][u]result[/u][/b]
is less than 	 	 	< 	bool result = (1 < 2) 	 	true
is greater than 	 	> 	bool result = (2 > 5) 	 	false
is equal to 	 	 	== 	bool result = (8 == 8) 	 	true
is less than or equal to 	<= 	bool result = (45.7 <= 42.3) 	false
is greater than or equal to 	>= 	bool result = (25.6 >= 12.9) 	true
is not equal to 	 	!= 	bool result = (12 != 12) 	false

Back on track, all you have to do is change the = to == in your if statements:

else if ( root -> left == NULL ) {

makenode()
This fix may be a bit more difficult than the last. Let's see why. Most node additions take place like this. First, if the node doesn't exist [NULL] then allocate memory to the node, set any data, and set left and right to NULL. Though usually after this it depends on how you want your node. Do you want it to check for previous entrance, or not.

For example, if you had a node and wanted to check for previous entrance of a word and so forth, it would work as the following:

Node* Node::addNode(Node *p, char *word) {
 	int cond;

 	if (p == NULL) {
 	 	p = (Node *)malloc(sizeof(Node));
 	 	p->word = strdup(word);
 	 	p->count = 1;
 	 	p->left = p->right = NULL;
 	}else if ((cond = strcmp(word, p->word)) == 0)
 	 	p->count++; 	// Repeated word
 	else if (cond < 0) 	// Less than into left subtree
 	 	p->left = addNode(p->left, word);
 	else 			 // Greater than into right subtree
 	 	p->right = addNode(p->right, word);

 	return p;
}

That was just a rough draft example. It may help you understand the syntax of a node though. Here is a useful tutorial on Linked List that may interest you.

If you have further questions, please feel free to ask.

- Stack Overflow

[confusedmind]

thank Stack,

all the information was helpful.

For the second question, the makeNode() one, I am really confused now. Please forget about what I asked in first post.

Here is part of my .h file (only posting some useful information)

#ifndef _INTEGERNODE_H
#define _INTEGERNODE_H

typedef int Item_type;

class IntegerNode {
    
    // private:
        
        // the node to hold information
        struct intNode {
            Item_type data;
            intNode* left; // to the left child
            intNode* right; // to the right child
        };
        
            Item_type data;
            intNode* left;
            intNode* right;
            
        int size; // remember how many nodes are there
    
    
    public:
        
        intNode* makeNode( Item_type item );
        // Access Member Function
        // PRE: item is a valid Item_type object
        // POST: A new intNode is created and the address is returned

};
#endif

and here is the implementation of makeNode() function

#include <iostream>
#include "IntegerNode.h"
using namespace std;

intNode* IntegerNode::makeNode ( Item_type item )
// Access Member Function
// PRE: item is a valid Item_type object
// POST: A new intNode is created and the address is returned
{
    intNode *newNode = new intNode;
    newNode -> data = item;
    newNode -> left = newNode -> right = NULL;
    return newNode;
}

this is supposed to return the address of the new node create by makeNode() function. but the compiler always gives errors during compilation like following:

IntegerNode.cpp:128: error: syntax error before `*' token
IntegerNode.cpp:134: error: syntax error before `->' token
IntegerNode.cpp:135: error: syntax error before `->' token

make.exe: *** [IntegerNode.o] Error 1

Execution terminated

where line128 is intNode* intNode::makeNode ( Item_type item )
line 134 and 135 are
newNode -> data = item;
newNode -> left = newNode -> right = NULL;

I correct this by removing class IntegerNode { } in the .h file. But I have no idea why I am doing that. ( I learned that from someone's example )
Any way that I can keep class IntegerNode { } decleration in my .h file and still have the code compiled?

Please have a look and any suggestion is welcome.