Centre of the Universe

In my last post I created a binary tree class. This post follows on from that, so I would recommend reading that first, if you have not already done so.

There are three types of traversals that are generally used to traverse a tree. These are preorder, inorder and postorder traversals, and all are similar to each other, except for the order in which the operations are performed.

For the preorder case, we first get the value of the node (starting at the root), and then recursively move down the left branch of the tree, and the recursively move down the right branch of the tree.

        public string preOrderTraversal(int nodeId)
        {
            string str = "";

            str += (string)(((BinaryNode)nodes[nodeId]).getValue());
            if (((BinaryNode)nodes[nodeId]).getLeftChildId() != -1)
            {
                str += preOrderTraversal(((BinaryNode)nodes[nodeId]).getLeftChildId());
            }
            if (((BinaryNode)nodes[nodeId]).getRightChildId() != -1)
            {
                str += preOrderTraversal(((BinaryNode)nodes[nodeId]).getRightChildId());
            }
            return str;
        }

The inorder traversal first recurses along the left branch, then gets the value of the node, and then recurses along the right branch. I find that this tends to be the most useful of the various traversals. It is properly bottom-up, where it works it’s ways to the bottom of the tree before it starts returning values.

        public string inOrderTraversal(int nodeId)
        {
            string str = "";

            if (((BinaryNode)nodes[nodeId]).getLeftChildId() != -1)
            {
                str += inOrderTraversal(((BinaryNode)nodes[nodeId]).getLeftChildId());
            }
            str += (string)(((BinaryNode)nodes[nodeId]).getValue());
            if (((BinaryNode)nodes[nodeId]).getRightChildId() != -1)
            {
                str += inOrderTraversal(((BinaryNode)nodes[nodeId]).getRightChildId());
            }
            return str;
        }

The postorder traversal, predictably, first recurses the left and then the right branch, and lastly gets the value of the node.

        public string postOrderTraversal(int nodeId)
        {
            string str = "";

            if (((BinaryNode)nodes[nodeId]).getLeftChildId() != -1)
            {
                str += postOrderTraversal(((BinaryNode)nodes[nodeId]).getLeftChildId());
            }
            if (((BinaryNode)nodes[nodeId]).getRightChildId() != -1)
            {
                str += postOrderTraversal(((BinaryNode)nodes[nodeId]).getRightChildId());
            }
            str += (string)(((BinaryNode)nodes[nodeId]).getValue());
            return str;
        }

Each of these traversals gives a different ordering of the values in the tree, and are applicable in different circumstances.

Related posts:

1. An implementation of a binary tree in C# Binary trees are a very useful data structure, and are...
2. Writing a family tree application in C# – Importing a Gedcom file – Part 1 In my previous post in this series, I introduced the...
3. Writing a family tree application in C# – The underlying structure I love being able to trace my family tree, and...
4. Combinations, permutations and factorials in C# Factorials are defined as a number that is multiplied by...
5. Vectors in C# A vector is simply a 1-dimensional array of numbers that...

Related posts brought to you by Yet Another Related Posts Plugin.