Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org [SOLVED] Awkward situation about Data Structure -Tree
 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

 10-30-2013, 09:24 AM #1 v3ct0r Member   Registered: Jun 2013 Location: China Distribution: Archlinux Posts: 67 Rep: 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.
 10-30-2013, 11:27 AM #2 psionl0 Member   Registered: Jan 2011 Distribution: slackware_64 14.1 Posts: 722 Blog Entries: 2 Rep: Pass the root of the subtree as a parameter to your insert function. void insert(bintree head, bintree node);
 10-30-2013, 11:32 AM #3 mina86 Member   Registered: Aug 2008 Distribution: Slackware Posts: 505 Rep: 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.
 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: ... 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."
10-30-2013, 09:17 PM   #5
psionl0
Member

Registered: Jan 2011
Distribution: slackware_64 14.1
Posts: 722
Blog Entries: 2

Rep:
Quote:
 Originally Posted by sundialsvcs 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.
10-31-2013, 04:33 AM   #6
v3ct0r
Member

Registered: Jun 2013
Location: China
Distribution: Archlinux
Posts: 67

Original Poster
Rep:
Quote:
 Originally Posted by mina86 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!!!

 10-31-2013, 05:03 AM #7 millgates Member Contributing Member   Registered: Feb 2009 Location: 192.168.x.x Distribution: Slackware Posts: 852 Rep: 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.
10-31-2013, 05:41 AM   #8
v3ct0r
Member

Registered: Jun 2013
Location: China
Distribution: Archlinux
Posts: 67

Original Poster
Rep:
Quote:
 Originally Posted by millgates 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?

10-31-2013, 06:45 AM   #9
millgates
Member

Registered: Feb 2009
Location: 192.168.x.x
Distribution: Slackware
Posts: 852

Rep:
Quote:
Originally Posted by xeechou
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 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 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 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.

 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: 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.
10-31-2013, 10:59 AM   #11
psionl0
Member

Registered: Jan 2011
Distribution: slackware_64 14.1
Posts: 722
Blog Entries: 2

Rep:
Quote:
 Originally Posted by xeechou 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.

11-01-2013, 11:17 PM   #12
v3ct0r
Member

Registered: Jun 2013
Location: China
Distribution: Archlinux
Posts: 67

Original Poster
Rep:
Quote:
 Originally Posted by sundialsvcs 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.

11-02-2013, 12:27 AM   #13
psionl0
Member

Registered: Jan 2011
Distribution: slackware_64 14.1
Posts: 722
Blog Entries: 2

Rep:
Quote:
 Originally Posted by xeechou 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).

 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 Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Daravon Programming 2 02-25-2013 10:15 PM dina3e Linux - Newbie 1 03-23-2008 06:57 AM kenneho Programming 1 11-04-2005 05:42 AM Hikito Linux - Newbie 1 09-11-2004 05:07 PM Alan Powell Linux - Newbie 1 04-06-2004 03:07 PM

LinuxQuestions.org

All times are GMT -5. The time now is 03:46 AM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -