BST In Order Traversal

I have written code to input data into a BST.  This data after being placed in the tree is shown below.  I would like to print this data in order.  After making the tree on paper i noticed that the path we need to take is Left pointer, parent, right pointer.  What is the best way to do this?
microsoft        3989898989 02 03 
java             1357357357 05 12 
zipinfo          0490080000 04 28 
pizzahut         3789789789 20 07 
google           3333333333 06 08 
cnn              1444444444 21 09 
yahoo            2121212121 11 00 
ilounge          4040404040 18 00 
dictionary       0555555555 31 10 
expedia          1234543210 00 17 
un               3939393939 13 14 
limewire         1010101010 22 00 
quicken          4294967295 00 15 
verizon          2468246824 00 16 
secondlive       1888888888 25 26 
wikipedia        4242424242 00 19 
facebook         1616161616 00 29 
howstuffworks    0000000001 00 00 
xe               0123123123 00 00 
nytimes          1234554321 27 23 
barnesandnoble   1111111111 24 00 
kalamazoocity    2444666888 00 00 
oprah            2999999999 00 00 
amazon           2222222222 00 30 
radioshack       4294000000 00 00 
tripadvisor      0777777777 00 00

Open in new window

jmkotmanAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
Bill-HansonConnect With a Mentor Commented:
It looks like you are storing the BST in a 2-dimensional string array where the first index indicates the node location and the second index indicates the data stored in the node.  This is not the best way to store a tree, but it should work.  I would normally define a custom Node class and store the nodes in a linked list.

Anyway, here's my attempt at writing a PrintTree function for your array.  You will need to add the code that prints the actual values and I'm not sure if I'm passing your tree variable correctly, but it should get you on the right path.  Notice that PrintTree operates on one node at a time and calls itself to traverse the entire tree.

To print the entire tree, just call PrintTree with the root node (ex: PrintTree(BSTHold[0], BSTHold);).

You can also print a partial tree by passing in any node (ex: PrintTree(BSTHold[5], BSTHold);).
public static void PrintTree(ref node, ref string[,] BSTHold){
	if (node[2] != "0") PrintTree(BSTHold[node[2]], ref BSTHold);
	// Insert code to print the node here.
	if (node[3] != "0") PrintTree(BSTHold[node[3]], ref BSTHold);
}

Open in new window

0
 
Bill-HansonCommented:
The easiest way uses a recursive function to walk the nodes.  It would be easier to explain if I saw your data structure, but here's some pseudo-code to get started.  Pass the root node to PrintTree to print the entire tree or any child node to print just that node and all descendants.

Function:  PrintTree(node_pointer)
1. If node_pointer is null, return.
2. Call PrintNode(node_pointer.left_pointer).
3. Print the current node.
3. Call PrintNode(node_pointer.right_pointer).

That should do it.
0
 
jmkotmanAuthor Commented:
The data for the BST was attached to this question.  If you look at the BST, Microsoft is the root of the tree and then the left and right child pointers point to other nodes.
0
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
Bill-HansonCommented:
I understand that.  What part of my answer are you having trouble with?  This is a standard BST search algorithm.
0
 
jmkotmanAuthor Commented:
I am able to find the last node of the tree by following the left pointer until it equals 00.  Once i get to there i know i need to write the parent node and then the right node.  The trouble i have is, when i get to cnn lets say, i have multiple nodes off of that which i have to write.  Then after that i have to come back to cnn and write the parent node of that.  The code that i am writing for this isn't working out.
0
 
Bill-HansonCommented:
Did you read my post about creating a recursive function to handle this?  The beauty of using a recursive function is that you don't need to follow any path, the function is smart enough to find all nodes and print them in order.  It works every time.  If you post some of your source code, I'll help you create one.  I need to know how you are storing the nodes.
0
 
jmkotmanAuthor Commented:
Below is the code that i use to create the BST.  A line is read in from a file and inputed into a string[,] BSTHold.  Once this is done, it ouputs the array i placed in my original question.  Let me know if this helps, thanks a lot!
public static void Create(ref int nextEmpty, ref int rootPtr, ref string url, ref string ipAddress, 
            ref int Incrementer, ref int Incrementer2, ref string data, ref int N, ref StreamWriter WriteToLog, 
            ref int leftChPtr, ref int rightChPtr, ref string[,] BSTHold, ref StreamReader ReadInFile, ref int menuchoice, ref int NodeCount)
        {
 
            data = ReadInFile.ReadLine();//Reads first line of file
 
            for (int i = 0; i < 16; i++)//Reading the first 16 characters of the data string
            {
                url += data[i];
            }
 
            for (int j = 17; j < 27; j++)//Reading the second 10 characters of the data string
            {
                ipAddress += data[j];
            }
 
            N++;
 
            while (data != null)
            {
                InsertInBST(ref rootPtr, ref BSTHold, ref nextEmpty, ref url, ref ipAddress, 
                    ref Incrementer, ref Incrementer2, ref rightChPtr, ref leftChPtr, ref N, ref data, ref ReadInFile, ref menuchoice, ref NodeCount);
            }
 
            WriteToLog.WriteLine("*Create BST Done: {0} BST nodes, root is at node 1", N.ToString("d2"));
        }
 
 
        public static void InsertInBST(ref int rootPtr, ref string[,] BSTHold, ref int nextEmpty, ref string url, ref string ipAddress,
            ref int Incrementer, ref int Incrementer2, ref int leftChPtr, ref int rightChPtr, ref int N, ref string data, ref StreamReader ReadInFile, ref int menuchoice, ref int NodeCount)
        {
            if (rootPtr == 0)
            {
 
                BSTHold[nextEmpty, 0] = url;
                BSTHold[nextEmpty, 1] = ipAddress;
                BSTHold[nextEmpty, 2] = leftChPtr.ToString();
                BSTHold[nextEmpty, 3] = rightChPtr.ToString();
 
                rootPtr = 1;
                nextEmpty++;
            }
 
            else
            {
                BSTHold[nextEmpty, 0] = url;
                BSTHold[nextEmpty, 1] = ipAddress;
                BSTHold[nextEmpty, 2] = leftChPtr.ToString();
                BSTHold[nextEmpty, 3] = rightChPtr.ToString();
 
                int v = 1;
                Incrementer2 = 1;
                int RowDim = 0;
 
                while (BSTHold[Incrementer + 1, 0] != null)
                {
                    while (BSTHold[Incrementer2 + 1, 0] != null)
                    {
                        if (string.Compare(url, BSTHold[v, 0]) < 0)
                        {
                            if (BSTHold[v, 2].Equals("0"))
                            {
                                BSTHold[v, 2] = nextEmpty.ToString();
                                v++;
 
                                Incrementer2 = (BSTHold.GetLength(RowDim) - 3);
                            }
                            else
                            {
                                v = Convert.ToInt32(BSTHold[v, 2]);
                            }
 
                            Incrementer2++;
                        }
                        else
                        {
                            if (BSTHold[v, 3].Equals("0"))
                            {
                                BSTHold[v, 3] = nextEmpty.ToString();
                                v++;
 
                                Incrementer2 = (BSTHold.GetLength(RowDim) - 3);
                            }
                            else
                            {
                                v = Convert.ToInt32(BSTHold[v, 3]);
                            }
 
                            Incrementer2++;
                        }
 
                        NodeCount++;
                    }
                    Incrementer++;
                    v++;
                }
 
                nextEmpty++;
            }
 
            if (menuchoice == 1)
            {
                data = ReadInFile.ReadLine();//Reads first line of file
 
                if (data != null)
                {
                    ipAddress = "";
                    url = "";
 
                    for (int i = 0; i < 16; i++)//Reading the first 16 characters of the data string
                    {
                        url += data[i];
                    }
 
                    for (int j = 17; j < 27; j++)//Reading the second 10 characters of the data string
                    {
                        ipAddress += data[j];
                    }
 
                    N++;
                }
            }
        }

Open in new window

0
 
JimBrandleyConnect With a Mentor Commented:
Bill-Hanson has given you good advice. However, after looking at your code, there are a few things I would like to add.

1. There are two advantages to using a tree. First, a pre-order traversal will return the nodes in a specific order - in this case alphabetic order. Second, you can search for any node in the tree very quickly - order of LOG-Base2(n) compares. There is also one big disadvantage. In order to preserve the fast search, you have to balance the tree as you add nodes. In your code, the first node entered is always the root. There is no balancing. Consider what your tree would look like if the nodes were added in alphabetic order. In that case, no node would have a left child, and you are left with a linear list of nodes. That's still a valid tree, but it's not balanced, and searches become Order(n).

2. You are converting numeric values to strings, then back to numbers when you want to use them. That's expensive. If you want to keep various data types together in a list or array, it is more efficient to create a very thin class or struct to contain the data.

3. When you read the data in from the file, you are concatenating a fixed number of characters one at a time to a new string. Each iteration through each of those two loops causes a new string to be allocated on the heap, and the previous one is abandoned for garbage collection. Substring would be much more efficient in both time and memory consumption.

4. Balancing a tree is a complex task. Given the way you are using the string array, I believe it would be much more efficient, and easier to write and debug if you just create an ordered list. If you always know in advance how big the list will be, you can use an array, but inserts are easier in a list. It's not hard to write a simple binary search for an ordered list. That gives you Order LOG(n) searches without the need to balance the tree.

Jim
0
All Courses

From novice to tech pro — start learning today.