Ad:

C++ Discussion Thread
Unsolved
Views: 23874

Oct 20th, 2004

coding a complete binary tree with Dev-C++

Expand Post »

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!!

Similar Threads

Coding a Complete Binary Tree in C
C++ complete binary tree using an array. Unexpected end file in C++
Binary Tree help! in C++
Binary tree in Computer Science
complete binary tree using an array help in C++

confusedmind

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

6 posts
since Oct 2004

Permalink

Oct 20th, 2004

Re: coding a complete binary tree with Dev-C++

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:

(Toggle Plain Text)

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:

(Toggle Plain Text)

name 	 	 	 	symbol 	sample usage 	 	 	result
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:

(Toggle Plain Text)

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:

(Toggle Plain Text)

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

Stack Overflow

Reputation Points: 26

Solved Threads: 4

Junior Poster

Offline

185 posts
since Sep 2004

Permalink

Oct 23rd, 2004

Re: coding a complete binary tree with Dev-C++

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)

C++ Syntax (Toggle Plain Text)
#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
#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

C++ Syntax (Toggle Plain Text)
 
 
#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;
}

#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:

C++ Syntax (Toggle Plain Text)
 
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
 
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.

confusedmind

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

6 posts
since Oct 2004

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Please help me out with this C++ program

Next Thread in C++ Forum Timeline: Need some help plz; ima newb (not sure how to catagorize this particular prob)

DaniWeb Message

Cancel Changes

User Name
Password