Nov 8, 2009

Data Structure -- Trees -- Threaded Binary Tree

 		free web hosting
Open Discussion > MODERATED AREA > Computers > Programming Languages > Others

Data Structure -- Trees -- Threaded Binary Tree

varalu
Nov 20 2007, 10:29 AM
A binary tree having a loop is known as a threaded binary tree.
Have a look at the attachment to have an idea of a threaded binary tree....

A's right child is B and B's left child is A.
Write an algorithm to find out whether the given tree is a threaded binary tree.

[attachment=879:Threaded...ary_Tree.JPG]

Look for time and space complexity.

Comment/Reply (w/o sign-up)

(G)Mubo
Apr 19 2009, 06:03 PM
Adding Elements to a threaded binary tree
Data Structure -- Trees -- Threaded Binary Tree

Using the most efficient way I muss add  50.000 elements in a tree.The key nodes are integers between [-50.000.000 to 5.000.000]. No deleting operation is needed

I need to write a little java code about this but don't get the idea well, so need so tips

thnks guys!

-question by Mubo

 


Comment/Reply (w/o sign-up)

(G)
May 16 2009, 08:32 PM

You wont believe it, but your teachers from uni read forums as well... So maybe you want to look into informatik-forum.At... But to answer your question:

Look up the insert-method in regular Binary Trees (p 75) and think about how to modify it so it works with threadedBinaryTrees. You'd probably want to think about getting the parent of a node without using a stack or a parent-var. For that I can recommend Depth-First Search, since in a TBT some of the node's child-thread points back to the original nodes parent.

Hope that was a little helpfull


Comment/Reply (w/o sign-up)


Got an Opinion! Express your Views! (no registration):-
Add your Reply/ Opinion/ Views/ Comments/ Suggestion/ Questions/ Queries etc.
Posts with decent grammar & English will be accepted and please refrain from profanities.
For asking a Question, We recommend you to sign-up (for free) so that you can track the topic easily.
Nature of your Post*: Opinion/ Reply/ Comments
Question/Query
Feedback to us.
       
Name   Email
Title/Question*

This textarea will convert to Rich-Text automatically (IE, Firefox, Chrome)

Similar Topics

Keywords : data, structure, trees, threaded, binary, tree

  1. Data Structure -- Permutations
    (1)
  2. Data Structure -- Queue -- Implement Using Stack
    (1)
    Implement a Queue using a stack. No restriction on space complexity. One possible Solutions a
    costly procedure... 1. Use a temp stack 2. Insertion into queue - Push the element into the
    original stack 3. Deletion from queue - Pop all the elements from stack into a temp stack
    - pop out the first element from the temp stack - pop all the remaining elements back to the
    original stack What is a queue? QUOTE A queue is a particular kind of collection in which
    the entities in the collection are kept in order and the principal (or only) operation....
  3. Data Structures -- Expression Trees
    (0)
    Construct an expression tree for the expression (a || /cool.gif" style="vertical-align:middle"
    emoid="B)" border="0" alt="cool.gif" /> && (c || d) After constructing the tree convert the tree to
    correspond to the associative property of the given expression. Eg: (1 + 2) * ( 3 + 4) = (1 * 3) +
    (1 * 4) + (2 * 3) + (2 * 4) Similar to that, from the constructed expression tree, construct a new
    expression tree such that inorder traversal of the new tree will be associative value of the given
    expression Inorder traversal of the new tree should be (a && c) || (a && d) || (....
  4. Data Structure -- Arrays -- Odd Number Of Elements
    (0)
    Given an array of elements with many numbers occurring even number of times and two numbers
    occurring odd number of times. Find out the two numbers that occur odd number of times. example:
    Elements in array -- 14433446 The expected result is 1 and 6 One solution 1. Find max of the
    array 2. Hash Function : element/max value 3. Repeat to all elements... 4. Find frequency... yo will
    get the 2 elements with odd frequency. but this is not the optimal.... Do find more solutions to
    this and post it. Look for time and space complexity. Another Solution one more s....
  5. Data Structures -- String -- Arrange Based On Repetition
    String data structure (2)
    Consider a string with any number of elements occurring any number of time. Rearrange the string
    in such a way that the alphabet with most occurrence occurs in the followed by the next most
    occurring alphabet and so on... It should also be seen that the alphabets should occur frequency
    number of times. Example: Input : abcdaeghzabcdbhb Output : bbbbaaaccddhhegz ....
  6. Data Structures -- Linked List -- Point Of Merging
    (4)
    Given two singly linked lists with both of them merging at some point. Find the position at which
    they merge. Eg: 1->30->50->65->2->59 88->46->65->2->59
    The above two linked lists merge at 65. Find this node where they merge.. Question
    Courtesy: Antony(Friend) One possible Answer A simple answer would be to find the length of
    both the linked lists and have two pointers, one for each linked list. Move (difference in lengths)
    steps in the longer linked lists and then start moving both the pointers by one every t....
  7. Data Structures -- String -- Palindrome
    Check if a string is a palindrome... (6)
    Write an algorithm to check whether a given string is palindrome or not in time complexity O(n)
    What is a palindrome?? QUOTE A palindrome is a word, phrase, number or other sequence of units
    that has the property of reading the same in either direction (the adjustment of punctuation and
    spaces between words is generally permitted). Composing literature in palindromes is an example of
    constrained writing. The word "palindrome" was coined from Greek roots palin
    (πάλιν; "back") and dromos (δρóμος; "way,
    direction") by....
  8. Data Structures -- Linked List -- Reverse
    Reverse a linked list (9)
    Give an algorithm to reverse a linked list with a time complexity of O(n) and minimal space
    complexity. What is a linked list? Search trap17.com. i Have already answered this question in
    one of my older questions. Solution 1 Here is one simple solution... CODE Void
    ReverseList(node* head) {     node *temp,*current,*result;     temp=null;     result=null;
        current=head;     while(current!=null)     {         temp=current->next;
            current->next=result;         result=current;         current=temp;     }    head=result;
    The above was suggested by m....
  9. Data Structures -- Binary Tree -- Structurally Same
    Find if 2 binary tress are structurally same?? (5)
    Given two binary trees, find out whether a tree is structurally same to the other. Structurally same
    means that the two trees look alike or a tree looks alike a subtree of the other tree. Look for
    time and space complexity. Some more for readers What is a binary tree? QUOTE A binary
    tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data
    element. The "root" pointer points to the topmost node in the tree. The left and right pointers
    recursively point to smaller "subtrees" on either side. A null pointer represents a binary....
  10. Data Structures -- Linked List
    Find the nth last element in linked list. (14)
    Given a linked list, find the 5th last element with Time complexity O(n) and minimal space
    complexity. Note: If you know the answer and if you feel it is simple also please post the
    answers so that others will come to know about the answers. What is a linked list?? /* this is for
    your further reference and reading */ QUOTE In computer science, a linked list is one of the
    fundamental data structures, and can be used to implement other data structures. It consists of a
    sequence of nodes, each containing arbitrary data fields and one or two references ("links") po....
  11. Data Structures -- Binary Tree -- Mirror Image
    Binary Tree -- Mirror Image (3)
    Given a binary tree, write an algorithm to find its mirror image with minimal time and space
    complexities. Note: If you know the answer and if you feel it is simple also please post the
    answers so that others will come to know about the answers. This question was sent by my friend
    through mail. Solutions Suggested Sol 1 CODE void PrintMirror(node *root) {
        if(node!=NULL)        PrintMirror(root->right);     Printf(root->data);
        PrintMirror(root->left);      } In case of implementation using array 2i+1 stores left child
    of ith node and 2i+2 store....
  12. Data Structure Questions
    (5)
    Question 1 Reply the solutions if you have any so that we can discuss... Given an array of n
    elements (containing only positive numbers) and sum, X. Find the first two elements in the array
    that sum upto X eg: Array of elements - {2, 3,1000, 200, 51, 88, 29, 49, 65, 40, 98, 12, 3}
    Sum - 100. The answer for the above sample is 51, 49. There are other possiblities
    also, but the first two numbers summing upto the given sum, 100 should be taken. How will you do
    this with minimal space and time complexities? Question 2 Given two nodes of ....
  13. Limiting Returned Data To Last X Fields With Sql
    (2)
    Hello, I'm currently developing a social-networking site in ColdFusion and several aspects of
    the site require me to return a limited number of records for display (e.g. displaying the last 3
    news items in the left-hand column on the front page, etc.). I currently only have a small SQL
    "cheet sheet" and what my ColdFusion reference book tells me, and I cannot find anything anywhere
    about limiting the data returned from a SELECT statement to the last X number of records. Any help
    is appreciated! Thanks, zeeman48....
  14. A Question About Data Collecting Program
    usually found in registers (1)
    does anyone know which programming language is used to make applications like those used in shops
    and malls where the sales assistant will enter name of a product and all its details will come up
    and whn someone makes a purchase the details will go to a database , i need to know which language
    is used and also which platform is used ,thanks in advance /laugh.gif"
    style="vertical-align:middle" emoid=":lol:" border="0" alt="laugh.gif" /> Please read the rules.
    The What Is..? forum is for answering a common question or telling everybody about what
    interesting fact you ....


      15. Looking for data, structure, trees, threaded, binary, tree

Searching Video's for data, structure, trees, threaded, binary, tree
See Also,
advertisement


Data Structure -- Trees -- Threaded Binary Tree

Affordable Web Hosting, Low cost Web Hosting - ComputingHost.com