Programming Forums > Application Development > Java

algatt · Apr 20th, 2005, 1:08 PM

Hi,

I have the following sample data in a table in MySQL.
a level 1 35
b level 2 a 34
c level 2 a 33
d level 3 b 32
e level 3 b 31
f level 3 c 30
g level 3 c 29
h level 4 d 28
i level 4 d 27
j level 4 e 26

Basically, the third column points to the first column. I need to develop an algorithm which finds all the leaf nodes in the table. I know it must be recursive, but I simply can't do it!

Thanks!

Berto · Apr 21st, 2005, 3:07 AM

can you possibly explin the data a bit more?

Ooble · Apr 21st, 2005, 11:36 AM

I think I get it. Including headers, it would be:

(Toggle Plain Text)

 ID | Level | Parent | Data
----+-------+--------+--------
 a  |   1   |        |  35
 b  |   2   |   a    |  34
 c  |   2   |   a    |  33
 d  |   3   |   b    |  32
 e  |   3   |   b    |  31
 f  |   3   |   c    |  30
 g  |   3   |   c    |  29
 h  |   4   |   d    |  28
 i  |   4   |   d    |  27
 j  |   4   |   e    |  26

Create an array of 10 structures (or whatever you call them in Java), like this (C++ code below):

(Toggle Plain Text)

struct data
{
    int ID;
    data *childLeft;
    data *childRight;
    string data;
}

data nodes [10];

I'm not sure how they work in Java, but in C and C++, those things with asterisks ( * ) before them are pointers - they point to another node. First of all, change the IDs to numbers instead of letters. Next, loop through the table and add each one to the array. That should get your started.

Eggbert · Apr 21st, 2005, 12:01 PM

>(or whatever you call them in Java)
Classes.

>I'm not sure how they work in Java
Java references work pretty much the same as C++ pointers. The only real difference is that references in Java are more restricted than C++ pointers. The equivalent code in Java would be:

(Toggle Plain Text)

class Node {
  public int ID;
  public String data;
  public Node left, right;
}

Node[] nodes = new Node[10];

>I need to develop an algorithm which finds all the leaf nodes in the table
The table represents a tree structure. You can either build the tree and then traverse it to find leaves, or process the table such that any ID that is not a parent is a leaf. Simple code to do that follows:

(Toggle Plain Text)

char[] IDs;
char[] parents;

// Fill IDs and parents with the corresponding table values

char[] leaves = new char[IDs.length]; // Too big, but better than too small
int k = 0;

for ( int i = 0; i < IDs.length; i++ ) {
  int j;

  // Seach for IDs[i] in the parents list
  for ( j = 0; j < parents.length; j++ ) {
    if ( parents[j] == IDs[i] )
      break;
  }

  // Not found, must be a leaf
  if ( j == parents.length )
    leaves[k++] = IDs[i];
}

algatt · Apr 26th, 2005, 12:49 PM

Thanks for all your help.

I solved the problem by creating an array, and traversing the tree and storing each node in the array. Once I had all the nodes in the array, I traversed the array and check whether or not that node was a parent to any other node. If it returned nothing, it means that it's a leaf node.

Apr 20th, 2005, 1:08 PM	#1
algatt Newbie Join Date: Apr 2005 Posts: 2 Rep Power: 0	Extracting nodes and leaves Hi, I have the following sample data in a table in MySQL. a level 1 35 b level 2 a 34 c level 2 a 33 d level 3 b 32 e level 3 b 31 f level 3 c 30 g level 3 c 29 h level 4 d 28 i level 4 d 27 j level 4 e 26 Basically, the third column points to the first column. I need to develop an algorithm which finds all the leaf nodes in the table. I know it must be recursive, but I simply can't do it! Thanks!

Apr 21st, 2005, 11:36 AM	#3
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	I think I get it. Including headers, it would be: (Toggle Plain Text) ID \| Level \| Parent \| Data ----+-------+--------+-------- a \| 1 \| \| 35 b \| 2 \| a \| 34 c \| 2 \| a \| 33 d \| 3 \| b \| 32 e \| 3 \| b \| 31 f \| 3 \| c \| 30 g \| 3 \| c \| 29 h \| 4 \| d \| 28 i \| 4 \| d \| 27 j \| 4 \| e \| 26 ID \| Level \| Parent \| Data ----+-------+--------+-------- a \| 1 \| \| 35 b \| 2 \| a \| 34 c \| 2 \| a \| 33 d \| 3 \| b \| 32 e \| 3 \| b \| 31 f \| 3 \| c \| 30 g \| 3 \| c \| 29 h \| 4 \| d \| 28 i \| 4 \| d \| 27 j \| 4 \| e \| 26 Create an array of 10 structures (or whatever you call them in Java), like this (C++ code below): (Toggle Plain Text) struct data { int ID; data childLeft; data childRight; string data; } data nodes [10]; struct data { int ID; data childLeft; data childRight; string data; } data nodes [10]; I'm not sure how they work in Java, but in C and C++, those things with asterisks ( * ) before them are pointers - they point to another node. First of all, change the IDs to numbers instead of letters. Next, loop through the table and add each one to the array. That should get your started. __________________ Me :: You :: Them

Apr 21st, 2005, 12:01 PM	#4
Eggbert Professional Programmer Join Date: Nov 2004 Posts: 250 Rep Power: 4	>(or whatever you call them in Java) Classes. >I'm not sure how they work in Java Java references work pretty much the same as C++ pointers. The only real difference is that references in Java are more restricted than C++ pointers. The equivalent code in Java would be: (Toggle Plain Text) class Node { public int ID; public String data; public Node left, right; } Node[] nodes = new Node[10]; class Node { public int ID; public String data; public Node left, right; } Node[] nodes = new Node[10]; >I need to develop an algorithm which finds all the leaf nodes in the table The table represents a tree structure. You can either build the tree and then traverse it to find leaves, or process the table such that any ID that is not a parent is a leaf. Simple code to do that follows: (Toggle Plain Text) char[] IDs; char[] parents; // Fill IDs and parents with the corresponding table values char[] leaves = new char[IDs.length]; // Too big, but better than too small int k = 0; for ( int i = 0; i < IDs.length; i++ ) { int j; // Seach for IDs[i] in the parents list for ( j = 0; j < parents.length; j++ ) { if ( parents[j] == IDs[i] ) break; } // Not found, must be a leaf if ( j == parents.length ) leaves[k++] = IDs[i]; } char[] IDs; char[] parents; // Fill IDs and parents with the corresponding table values char[] leaves = new char[IDs.length]; // Too big, but better than too small int k = 0; for ( int i = 0; i < IDs.length; i++ ) { int j; // Seach for IDs[i] in the parents list for ( j = 0; j < parents.length; j++ ) { if ( parents[j] == IDs[i] ) break; } // Not found, must be a leaf if ( j == parents.length ) leaves[k++] = IDs[i]; }

Apr 26th, 2005, 12:49 PM	#5
algatt Newbie Join Date: Apr 2005 Posts: 2 Rep Power: 0	Solved Thanks for all your help. I solved the problem by creating an array, and traversing the tree and storing each node in the array. Once I had all the nodes in the array, I traversed the array and check whether or not that node was a parent to any other node. If it returned nothing, it means that it's a leaf node.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Apr 21st, 2005, 3:07 AM	#2
Berto Programming Guru Join Date: Aug 2004 Posts: 1,022 Rep Power: 6	can you possibly explin the data a bit more?

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > Java

Extracting nodes and leaves