Hello,
I'm having trouble in Converting From Binary Tree to Threaded Binary Trees.
Please could you help me writing a function that can make the conversion.
Thanks in Advance.
Printable View
Hello,
I'm having trouble in Converting From Binary Tree to Threaded Binary Trees.
Please could you help me writing a function that can make the conversion.
Thanks in Advance.
What exactly are you trying to run in parallel?
gg
No, it has nothing to do with multiple threads. A threaded-tree is a modified binary tree data structure allowing faster travelling between nodes.Quote:
Originally Posted by Codeplug
It's kind of a binary tree and linked-list all in one data structure. See here:
http://en.wikipedia.org/wiki/Threaded_binary_tree
Please help me
I think the pointer by iMalc should get you on the right path. I also got plenty of hits from google by entering "Threaded Binary Tree implementation"Quote:
Originally Posted by elton_fan
What exactly do you want us to do? Write a function that takes some arbitrary C code and adds a "thread pointer" [either as a separate pointer or using the left/right nodes that should be NULL as backpointers] - that is a MAJOR task that would take a very experienced C parser writer quite some time to develop. I'm not experienced in writing C parsers, but I understand this problem enough to know that it's non-trivial.
--
Mats
This is the best I could do please try to help me
Code:#include<stdio.h>
#include<stdlib.h>
typedef struct _x{
int th_left,th_right,num;
struct _x *left,*right;
}node;
node *insert(node *x,int num);
node *convert(node*x);
node *link(node *x);
int
main(void){
node *root;
int number,sentinel;
sentinel=-10;
root=NULL;
printf("Enter a number of -10 to exit\n");
do{
scanf("%d",&number);
if(number!=-10)
root=insert(root,number);
}while(number!=sentinel);
root=convert(root);
return(0);
}
node
*insert(node *x,int num){
if(x==NULL){
x=(node*)malloc(sizeof(node));
x->num=num;
x->left=NULL;
x->right=NULL;
x->th_right=0;
x->th_left=0;
}
else if(num>x->num)
x->right=insert(x->right,num);
else if(num<x->num)
x->left=insert(x->left,num);
return(x);
}
node
*convert(node*x){
// filling the threads
node *walker;
walker=x;
while(walker->left!=NULL)
walker=walker->left;
walker->th_left=1;
walker=x;
while(walker->right!=NULL)
walker=walker->right;
walker->th_right=1;
// threads are successfully filled
x=link(x);
return(x);
}
node
*link(node *x){
node *temp;
temp=x;
if(x==NULL)
return;
else{
if(!x->th_right){
while(x->right!=NULL)
x=x->right;
x->right=temp;
}
if(!x->th_left){
while(x->left!=NULL)
x=x->left;
x->left=temp;
}
}
free(temp);
x->left=link(x->left); // moving
x->right=link(x->right); // moving
}
please try to find out what is the problem with me
Have a look at this:
http://www.catb.org/~esr/faqs/smart-....html#explicit
Please feel free to go back to the top and read the rest of the page too!
--
Mats
because you couldn't find the solution you're sending me a ........ing website
No, because I can't be bothered to spend half an hour of my time FIGURING OUT something that you should be able to write down in 5 minutes - namely: a summary of what you are do to test the code, and how it fails!Quote:
Originally Posted by elton_fan
If you ask the right questions, you will get the right answers. If you can't even be bothered to write a decent question, how do you expect someone to help you?
--
Mats
By experience, I know the experienced programmers by the way that they are looking at the code.
You can't exactly see his eyes can you? :)
You can't expect to type a half assed question and expect someone like matsp to see, "ohh he means this" and give you the 'answer'. In fact you didn't even ask a question.
> please try to find out what is the problem with me
That's a question I can answer, http://www.catb.org/~esr/faqs/smart-....html#explicit
You don't really want to be asking that but... :p :rolleyes:Quote:
Originally Posted by elton_fan
Well you're English is slightly poor and lacks capital letters and punctuation, you don't ask a specific question (no question mark), and you behave less than nicely towards those who are trying to help you to help yourself.
Now, let me ask you a question, which if you can answer, will enable us to properly help you. Can you describe for us please in your own words how you are trying to solve the problem, and what doesn't work with the code you posted?
(I have studied and implemented a kind of threaded tree before)
I have never thought that this forum is one of the few forums which holds the stupidest computer programmers in the world.
I will quite before being attacked by the epidemic which called "stupidity" that you acquired here.
by the way you have a very nice page iMalc.
did you use Textpad to created?????
Nope. I actually wrote my own C++ code html-formatter in Delphi! :confused:Quote:
Originally Posted by elton_fan
I found my threaded tree code, and unfortunately back then when I tried it I used seperate prev & next pointers as well as left & right pointers, and never got around to combining them and using flags. I do remember that it was one of the trickier things I wrote back then.
If I read your code correctly, you're constructing the tree and then modifying it to be threaded afterwards? Mine was a threaded-AVL-tree which was threaded from the beginning. It's so different thast the code would be no user whatsoever to you.
Is 'link' simply meant to find the successor? Something that jumps out at me as being very wrong is that there's a call to 'free' in there.