Thread: Converting From Binary Tree to Threaded Binary Trees

  1. #1
    Registered User
    Join Date
    Jan 2007
    Posts
    72

    Angry Converting From Binary Tree to Threaded Binary Trees

    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.
    proud to be from aui www.aui.ma and also a great elton john's fan

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    What exactly are you trying to run in parallel?

    gg

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Codeplug View Post
    What exactly are you trying to run in parallel?
    No, it has nothing to do with multiple threads. A threaded-tree is a modified binary tree data structure allowing faster travelling between nodes.
    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
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Jan 2007
    Posts
    72
    Please help me
    proud to be from aui www.aui.ma and also a great elton john's fan

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by elton_fan View Post
    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"

    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Jan 2007
    Posts
    72
    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("&#37;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 
    	}
    proud to be from aui www.aui.ma and also a great elton john's fan

  7. #7
    Registered User
    Join Date
    Jan 2007
    Posts
    72
    please try to find out what is the problem with me
    proud to be from aui www.aui.ma and also a great elton john's fan

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Registered User
    Join Date
    Jan 2007
    Posts
    72
    because you couldn't find the solution you're sending me a ........ing website
    proud to be from aui www.aui.ma and also a great elton john's fan

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by elton_fan View Post
    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!

    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Registered User
    Join Date
    Jan 2007
    Posts
    72
    By experience, I know the experienced programmers by the way that they are looking at the code.
    proud to be from aui www.aui.ma and also a great elton john's fan

  12. #12
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by elton_fan View Post
    please try to find out what is the problem with me
    You don't really want to be asking that but...
    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)
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Jan 2007
    Posts
    72
    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.
    proud to be from aui www.aui.ma and also a great elton john's fan

  15. #15
    Registered User
    Join Date
    Jan 2007
    Posts
    72
    by the way you have a very nice page iMalc.
    did you use Textpad to created?????
    proud to be from aui www.aui.ma and also a great elton john's fan

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM