LinuxQuestions.org
Latest LQ Deal: Linux Power User Bundle
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 10-30-2013, 09:24 AM   #1
v3ct0r
Member
 
Registered: Jun 2013
Location: China
Distribution: Archlinux
Posts: 67

Rep: Reputation: Disabled
Wink Awkward situation about Data Structure -Tree


Hey guys, I'm building my Data structures for Lesson's need.
What I met was the insertion problem of tree.
It's about a travelsal problem of binary tree, yeah, a typical Travelsal Algorithm is reasonable simple, but I found I dont know how to insert a node in tree, my tree was declared in this way.
Code:
typedef struct Btreenode {
        /* indicate what the Telemtype is */
        /* flag == 0: char
         * flag == 1: int
         * flag == 2: float
         * flag == 4: double;
         * flag == 8: pointer, point to somewhere else */
        int  flag;
        Telemtype data;
        //int nodenum;
        struct Btreenode *lsubtr;       /* left  subtree */
        struct Btreenode *rsubtr;       /* right subtree */
} *btrnode;

typedef struct Btree {
        btrnode root;
        btrnode last;           //easy for insertion? */
} *bintree;
Looking at this structures, How do I know WHERE TO INSERT when I want to insert a node in my tree, since what user get is just the address of "bintree".
So that if I got no tree, how can I do a traversal?

Just give me a hint, I think I can finish rest of it.
Thanks for all your help.
 
Old 10-30-2013, 11:27 AM   #2
psionl0
Member
 
Registered: Jan 2011
Distribution: slackware_64 14.1
Posts: 722
Blog Entries: 2

Rep: Reputation: 123Reputation: 123
Pass the root of the subtree as a parameter to your insert function.

void insert(bintree head, bintree node);
 
Old 10-30-2013, 11:32 AM   #3
mina86
Member
 
Registered: Aug 2008
Distribution: Slackware
Posts: 493

Rep: Reputation: 211Reputation: 211Reputation: 211
This is a bit off topic, but since all values of “flag” are mutually exclusive, there is no need to use powers of two, and furthermore, you might consider using and enum.
 
Old 10-30-2013, 03:12 PM   #4
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 9,078
Blog Entries: 4

Rep: Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170
... also, use a descriptive name, not something like flag. You definitely should declare an enumerated type, and give the variable a meaningful name.

Also ... remember that "a B-tree has been done to death." Look for an existing library, or C++ class, to do the majority of the work for you. There's no point in writing, and debugging, a "stock part."
 
Old 10-30-2013, 09:17 PM   #5
psionl0
Member
 
Registered: Jan 2011
Distribution: slackware_64 14.1
Posts: 722
Blog Entries: 2

Rep: Reputation: 123Reputation: 123
Quote:
Originally Posted by sundialsvcs View Post
There's no point in writing, and debugging, a "stock part."
If you are learning programming then there is no superior way than trying to write a "stock part".
 
1 members found this post helpful.
Old 10-31-2013, 04:33 AM   #6
v3ct0r
Member
 
Registered: Jun 2013
Location: China
Distribution: Archlinux
Posts: 67

Original Poster
Rep: Reputation: Disabled
Quote:
Originally Posted by mina86 View Post
This is a bit off topic, but since all values of “flag” are mutually exclusive, there is no need to use powers of two, and furthermore, you might consider using and enum.
I'm using a flag because I just want to know if Telemtype is a pointer or not, so that we I need to free a node, I will know if I need to free data first. The declaration I use was quite prolix, In fact, more simple way is like this:
Code:
typedef struct Btreenode {
        /* indicate what the Telemtype is */
        /* ispointer == 0: nopointer
        
         * ispointer == 1: pointer, point to somewhere else */
        int  ispointer;
        Telemtype data;
        //int nodenum;
        struct Btreenode *lsubtr;       /* left  subtree */
        struct Btreenode *rsubtr;       /* right subtree */
} *btrnode;

typedef struct Btree {
        btrnode root;
} *bintree;
But hell, it's not what I asked, I mean, if I wanna insert or delete a node, apperantly I dont know where to insert, the prototype

int insert(bintree, btrnode) not gonna work!!!
 
Old 10-31-2013, 05:03 AM   #7
millgates
Member
 
Registered: Feb 2009
Location: 192.168.x.x
Distribution: Slackware
Posts: 852

Rep: Reputation: 389Reputation: 389Reputation: 389Reputation: 389
It's the same as searching. Start at the top of the tree and go left or right based on whether your new item should go before or after the node you're currently at. When you get to a NULL pointer, that's where you insert the new item.
 
Old 10-31-2013, 05:41 AM   #8
v3ct0r
Member
 
Registered: Jun 2013
Location: China
Distribution: Archlinux
Posts: 67

Original Poster
Rep: Reputation: Disabled
Quote:
Originally Posted by millgates View Post
It's the same as searching. Start at the top of the tree and go left or right based on whether your new item should go before or after the node you're currently at. When you get to a NULL pointer, that's where you insert the new item.
What does
Quote:
whether your new item should go
mean? Can I say to the node" Hey, you, just go right, then go left, then go right, then you will find a place for you!"
That is definitely not possible, parameters wont be able to carry that much information. Think about when we use touch and mkdir
Either I know the abosulte name of a file, or we just create a file under my current location!!!
That's a nature way!
So, I dont get what you are trying to tell me, please be a little patient?
 
Old 10-31-2013, 06:45 AM   #9
millgates
Member
 
Registered: Feb 2009
Location: 192.168.x.x
Distribution: Slackware
Posts: 852

Rep: Reputation: 389Reputation: 389Reputation: 389Reputation: 389
Quote:
Originally Posted by xeechou View Post
What does
Quote:
whether your new item should go
mean?
It means that one of the fundamental assumptions about building a binary tree is that there is some kind of comparison defined between the elements of the tree that allows us to determine the particular order of the elements in an ordered set. For example, strings may be ordered alphabetically, which means that "apple" goes before "banana", but "orange" goes after it.

Quote:
Originally Posted by xeechou View Post
Can I say to the node" Hey, you, just go right, then go left, then go right, then you will find a place for you!"
Actually, yes you can! That's what programming is all about.

Quote:
Originally Posted by xeechou View Post
That is definitely not possible, parameters wont be able to carry that much information.
You don't need to carry that information into the function. It's the job of the function to take care of that. All you need to tell the function is the begining (root) of the tree and the data to insert.

Quote:
Originally Posted by xeechou View Post
Think about when we use touch and mkdir
Either I know the abosulte name of a file, or we just create a file under my current location!!!
Well, the point is, the process of inserting data into a binary tree consists of two parts:
1) finding the correct place to insert the data
2) inserting data into a specific place in a tree

I could very well write a script in bash that will create a hierarchy of directories with a structure equivalent to a binary tree. I could write code to create (insert) a new directory in the correct place in the hierarchy with just the root directory of the hierarchy and the name of the new directory as parameters. The actual execution of mkdir will only constitute the second part of the process.

Last edited by millgates; 10-31-2013 at 07:14 AM.
 
Old 10-31-2013, 09:34 AM   #10
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 9,078
Blog Entries: 4

Rep: Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170Reputation: 3170
A binary tree seeks to split the data constantly in-half. It is far easier for you to surf the Internet for an existing example of tree algorithms, complete with code-snippet examples, than for you to blunder through figuring it all out on your own. (Trees, especially balanced trees, can become quite complicated indeed, very fast ...)

Even if you are "learning programming," you are not the first to be doing so, and "the right answer(s)" are thoroughly and completely known. Therefore, a good on-line textbook on Data Structures is what you need. (In my college days, that was an entire 15-week and very difficult course.) Yes, you are "learning." But, be efficient about doing so.

And, again, if you simply want to use a tree of a particular type, a (say ...) C++ "class" is the way to go. Devise custom classes that descend from the provided ancestors, and, as the old bus-line commercial say, "Leave the Driving to Us." Peek inside the source-code if you are truly interested, to see how they did it.

Last edited by sundialsvcs; 10-31-2013 at 09:37 AM.
 
Old 10-31-2013, 10:59 AM   #11
psionl0
Member
 
Registered: Jan 2011
Distribution: slackware_64 14.1
Posts: 722
Blog Entries: 2

Rep: Reputation: 123Reputation: 123
Quote:
Originally Posted by xeechou View Post
Hey guys, I'm building my Data structures for Lesson's need.
What I met was the insertion problem of tree.
It's about a travelsal problem of binary tree, yeah, a typical Travelsal Algorithm is reasonable simple, but I found I dont know how to insert a node in tree, my tree was declared in this way.
It's no different to what you would have considered when you did singly-linked lists. (You did start with that didn't you?)

It's a question of comparing newItem.data with treeNode.data and then deciding which direction to take for the next treeNode.

In the case where this is the first node to be inserted into the tree, the new node becomes the address of the root node. Just pass a pointer to the root node pointer so you can store this address there.
 
Old 11-01-2013, 11:17 PM   #12
v3ct0r
Member
 
Registered: Jun 2013
Location: China
Distribution: Archlinux
Posts: 67

Original Poster
Rep: Reputation: Disabled
Quote:
Originally Posted by sundialsvcs View Post
A binary tree seeks to split the data constantly in-half. It is far easier for you to surf the Internet for an existing example of tree algorithms, complete with code-snippet examples, than for you to blunder through figuring it all out on your own. (Trees, especially balanced trees, can become quite complicated indeed, very fast ...)

Even if you are "learning programming," you are not the first to be doing so, and "the right answer(s)" are thoroughly and completely known. Therefore, a good on-line textbook on Data Structures is what you need. (In my college days, that was an entire 15-week and very difficult course.) Yes, you are "learning." But, be efficient about doing so.

And, again, if you simply want to use a tree of a particular type, a (say ...) C++ "class" is the way to go. Devise custom classes that descend from the provided ancestors, and, as the old bus-line commercial say, "Leave the Driving to Us." Peek inside the source-code if you are truly interested, to see how they did it.
Yeah, typical Insertion method is to compare "node->data", and decide which way to go, it's certainly easy to do so, and much like a look up algorithm. In addition, I did surf Internet for a exist algorithm and I know what they did.

But what if my "node->data" was not build for that easy case, data is not in order(just like a directory tree), traversal() and lookup() still works, but Insertion failed anyway.
 
Old 11-02-2013, 12:27 AM   #13
psionl0
Member
 
Registered: Jan 2011
Distribution: slackware_64 14.1
Posts: 722
Blog Entries: 2

Rep: Reputation: 123Reputation: 123
Quote:
Originally Posted by xeechou View Post
But what if my "node->data" was not build for that easy case, data is not in order(just like a directory tree), traversal() and lookup() still works, but Insertion failed anyway.
No matter what sort of data you are dealing with, it can always be ranked - even if you have the make up the comparison rules yourself (ie write your own compare() function yourself).
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
How to generate a graphical plot of a tree data structure Daravon Programming 2 02-25-2013 10:15 PM
removeing the files but tree structure should be same dina3e Linux - Newbie 1 03-23-2008 06:57 AM
Perl/Linux: Syncronize tree structure on network kenneho Programming 1 11-04-2005 05:42 AM
Preserving directory tree structure /etc/fstab Hikito Linux - Newbie 1 09-11-2004 05:07 PM
Recommendation for webpage tree structure Alan Powell Linux - Newbie 1 04-06-2004 03:07 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 04:29 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration