Binary Tree Manipulaton

[Nuluvius]

Hi,

I was wondering if I might be able to find a bit of assistance here. Iv created a program that demonstrates very simple functions on a binary search tree. This is indeed part of an assignment on my degree.

The tree stores words (lists of the type char) in order of ASCII value. Iv writen functions for inerting, finding, printing in verious traversal orders & counting the list items (words). Iv also writen functions for finding the height of the tree and its least item - which as I understand it, leastItem, will be required for the function Im struggeling with.

Obviously the one missing is delete. I have a prototype of the function:

BSTreeADT removeItem(wordADT item, BSTreeADT t);

But no real solid idea as to the first steps I need to take. I know this will be a lengthy function, Id like to make sure I get the base correct.. would someone be kind enough to help me on the first steps?

Thank you for any help in advance. I apprechaite you taking the time.

[Mybowlcut]

If I remember my Java BST assignment correctly, you'll need to find the item to remove before you can remove it, so can you post up the find function?

[Nuluvius]

Certanly, and thank you.

boolean isPresent(BSTreeADT t, wordADT item)
{
	if (isEmptyBSTree(t))
	{
		return FALSE;
	}
	else if (wordEqual(item, rootTree(t)))
	{
		return TRUE;
	}
	else if (wordLess(item, rootTree(t)))
	{
		return isPresent(leftTree(t), item);
	}
	else
	{
		return isPresent(rightTree(t), item);
	}
}

So firstly I should attempt a stopping condition for the recursion - something like:

if the item is not present
    return the tree unalterd
else if the item is present
    do something...

[Zachm]

1. First of all, this doesn't look like C++ code to me. Are you sure you posted this in the right forum ?
2. You'll need your "find" function to return the found node(in case it is found) and not just true or false - otherwise you can't remove it can't you ?
3. In order to remove a node from a BST, you need to consider several possible cases. Let v be the node to be removed, then consider all of the following cases:
a. v is a leaf
b. v has only one child (left or right)
c. v has 2 children (both left and right).

See this link for more details.

Regards,
Zachm

[Paul McKenzie]

Certanly, and thank you.

boolean

There is no such thing as "boolean" in C++.

Regards,

Paul McKenzie

[Nuluvius]

There is no such thing as "boolean" in C++.

Regards,

Paul McKenzie

There is indeed if you create the type.

#ifndef _boole_h
#define _boole_h

#define FALSE 0
#define TRUE 1

typedef int boolean;

void writeboolean(boolean value);

#endif

And no this is not C++, this particular issue should be C, my appologies.

[Lindley]

The only difficult part of node removal in a BST is figuring out how to restructure the tree once the node is gone. Indeed, this is the primary difference between all the various BST data structures.

The simplest possible approach would be to hang the lesser subtree under the removed node off the smallest node in the greater subtree, and move the root of the greater subtree up to replace the removed node.

[Paul McKenzie]

There is indeed if you create the type.

No. The typedef keyword doesn't create new types.

Regards,

Paul McKenzie

[Nuluvius]

No. The typedef keyword doesn't create new types.

Regards,

Paul McKenzie

Unless I am mistaken I do beleave that I never at any point stated that the typedef keyword was used in that manor?
I only meant to demonstrate that I had defined boolean in a seperate library for conveniant usage.

[Paul McKenzie]

Unless I am mistaken I do beleave that I never at any point stated that the typedef keyword was used in that manor?

The code you posted to claim that "boolean" exists in C++ (which it doesn't) uses typedef. So what am I to conclude from that?

Secondly, the question you're asking delves into algorithms. Do you have an algorithm planned first before writing any code? If not, the algorithm forum is more appropriate.

Regards,

Paul McKenzie

[Nuluvius]

The code you posted to claim that "boolean" exists in C++ (which it doesn't) uses typedef. So what am I to conclude from that?

Secondly, the question you're asking delves into algorithms. Do you have an algorithm planned first before writing any code? If not, the algorithm forum is more appropriate.

Regards,

Paul McKenzie

No. You are attempting to display condescension, it will not work.

To your second point. I am attempting to obtain a base for a plan, perhapse it should be relocated to that forum in such a case. However, that is a decision for the moderators.. furthermore the point of the thread would seem to be becoming blured now. Perhapse it may be more constructive to return to it and place other issues aside?

[Lindley]

No. The typedef keyword doesn't create new types.

Actually it does to a certain extent. A typedef is considered a definition, not a declaration----hence why you can't have two of them for the same type even if they're non-conflicting.

Besides which, the meaning was obvious and there's no point in debating semantics this way.

[Paul McKenzie]

No. You are attempting to display condescension, it will not work.

Correcting an incorrect statement is condescension?

I am correcting what you're saying. That's all. Others are reading this thread, and wrong information should be corrected.

Regards,

Paul McKenzie

[Paul McKenzie]

Actually it does to a certain extent. A typedef is considered a definition, not a declaration----hence why you can't have two of them for the same type even if they're non-conflicting.

All of this is stated with the following caveat:

Don't go into an interview and answer the question "does typedef create a new type?" with a "yes" answer.

Regards,

Paul McKenzie

[Paul McKenzie]

To your second point. I am attempting to obtain a base for a plan,

The link provided by Zachm should be self-explanatory. What you should do is code each case, the simple one first, and then move on from there. Then once that's done, you should see a general pattern used in deleting nodes, thereby improving the code.

Second, if this is actually your prototype:

BSTreeADT removeItem(wordADT item, BSTreeADT t);

And BSTreeADT is not aliased as a pointer, then this function will not do what you think it will do. What will happen is that the compiler will create a temporary tree, delete the node from the temporary tree, and then on return, you don't see the results because the tree was temporary.

The reason is that "t" is not passed using a pointer. Again, this is assuming that BSTreeADT isn't a pointer, i.e.

typedef struct tagBSTreeADT
{
    // whatever
} *BSTreeADT;

The code will work, since the name "BSTTreeADT" is a typedef for a pointer to a tagBSTreeADT, but not this:

typedef struct tagBSTreeADT
{
    // whatever
} BSTreeADT;

If the above is how you've defined the struct, then the code will produce the ill-effects I described earlier.

Regards,

Paul McKenzie