my problem in binay search tree implementation C++

Question

1.00/5 (1 vote)

See more:

can any one help me in this. i rewrite it many times and i don't know the reason?

C#

#include<iostream>
#include<stdlib.h>

typedef int EType;
typedef struct tnode
{
  EType data;
  struct tnode* left;
  struct tnode* right;
}TNode;

typedef struct tnode* BTREE;
TNode* insertBST(BTREE T,EType x);
TNode* insert_left(BTREE T,EType x);
TNode* insert_right(BTREE T,EType x);
TNode* find(BTREE T, EType x);
int main(){
BTREE a,s;a=s=NULL;
insertBST(a,4);insertBST(a,3);


}
TNode* insertBST(BTREE T,EType x){
    TNode* comp;
if(T==NULL){
    comp=new TNode;
    if(comp==NULL)return comp;
    else{T->data=x;
    T->left=T->right=NULL;
    }T=comp;


}
else if(x<T->data)T->left=insertBST(T->left,x);
else T->right=insertBST(T->right,x);
return(T);





}
TNode* find(BTREE T, EType x){
 if(T->data==x||T==NULL)return T;
 else if(x<T->data)return find(T->left,x);
 else return find(T->right,x);



}

Posted 25-May-15 15:03pm

Member 11712396

Add a Solution

Comments

Sergey Alexandrovich Kryukov 25-May-15 22:10pm

The reason for what?
But, in very general terms, there are apparent reasons for big troubles. 1) Why not using C++, once you already use a C++ compiler. 2) You need to understand each and every line you write.

The second problem is the biggest. This is the simplest illustration: you write
if (comp==NULL) return comp;
It's apparent that the statement under "if" is never executed, because you assign comp to a constructed instance one line before. And so on, no need to examine each line...

—SA

Mohibur Rashid 26-May-15 0:23am

Question to Sergey, I have never faced that issue, but, what would happen if allocator fails to allocate, in case of memory shortage. Won't it return null? Even though in this case the requested memory is not significant. But if large memory is requested which cannot be fulfilled by os. What would happen then, will the application fail or will alocator will return zero? If the allocator returns zero.
by the way, i am not making a separate question for this.

Sergey Alexandrovich Kryukov 26-May-15 1:08am

This is a pretty difficult question. I think the best answer would be "the result is unpredictable". The problem is: you create an object and then the construction start the chain of construction of all the composed objects. Then eventually, the memory is exhausted somewhere in the middle and an exception is thrown. The memory required by exception object could be a separate problem, but let's assume it is always reserved by the OS. Then the exception propagates to the nearest point of exception handling. You come to the situation when the point of the big allocation is passed. It's not that the object is null or not, but the point on the stack where the object pointer was is no longer exist, because the stack frame is passed. Can you see the point?

Let's say, you catch the not-enough-memory exception so that the allocation point is written under the try-catch block. It won't give you much because the exception may propagate from some unpredictable state of the stack. The object becomes half allocated. In the unmanaged memory systems, it's very difficult to get the heap back to consistent state and at least to undo all the actually allocations, because you don't get exact information on what objects have been already allocated and what's not.

I think it would be safe to say that the mechanism for restoration on the consistence of the heap in unmanaged heap system after non-enough-memory exception simply does not exist. You don't have enough information for restoration it to the consistent state, so, at best, some memory will remain allocated and unreachable for deallocation. That's why I think that the whole process should be eventually terminated, perhaps after completion of some critical tasks, if possible.

You know, long time ago, I tried to create such system for restoration of the unmanaged heap. It was long time ago. I created my own mulithreading system with structural exception handling. It was started from DOS. At that time, even Linux did not have mulithreading yet and even C++ did not have exception mechanism. (I borrowed the ideas from Ada and CLU.) My attempt of restoration of heap was only partially successful. The problem is that it required considerable amount of memory to store additional heap information; and that memory could also be depleted... I came to the ideas more or less similar to the ideas of memory-managed system, which would be too hard to implement...

—SA

Mohibur Rashid 26-May-15 22:26pm

Thank you for the explanation.

Sergey Alexandrovich Kryukov 27-May-15 0:04am

You are welcome.
—SA

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

barneyman · Answer 1 · 2015-05-25T15:38:00

Solution 1

single step it in the debugger - you'll see that InsertBST is fundamentally flawed ...

1. when T is null your if/else clause is incorrectly scoped, i'm guessing you get null+offset exceptions?
2. when T is null, the caller never gets to use what is *supposed* to be returned, so the second call will fail the same way

and an observation, for the love of cheese don't use typedefs that deliberately obscure if something is a ptr or an object (BTREE specifically here)

Posted 25-May-15 15:38pm

barneyman

Comments

Member 11712396 25-May-15 22:00pm

thank you but can you tell what must i do to correct the code.i mean correct the code.

barneyman 25-May-15 22:04pm

i thought i just did?

Member 11712396 25-May-15 22:14pm

i don't understand. forgive me but i'm a junior in programming and data Structures.

barneyman 25-May-15 22:24pm

i get that ... we all were once, but me fixing it *for* you doesn't make you any more senior :)

InsertBST is broken ... the contents of your first if(T==NULL) clause is the root cause of your problem (i'm guessing, you've not actually expressed what the problem is) - format it so it's legible, and read it ... it's 10 lines when formatted correctly - the problem should jump out at you

when you've fixed that, have a look at #2 i made

Member 11712396 25-May-15 22:24pm

i mean can you write code

barneyman 25-May-15 22:25pm

lol - i can - you couldn't afford my hourly rate

Sergey Alexandrovich Kryukov 25-May-15 23:12pm

Damn... My 5. I like the conversation. :-)
But also take a look at my comment to the question.
—SA