How to create a binary tree

Question

I did'nt mean binary search tree.

for example, if I insert values 1,2,3,4,5 in to a binary search tree the inorder traversal will give 1,2,3,4,5 as output.

but if I insert the same values in to a binary tree, the inorder traversal should give 4,2,5,1,3 as output.

Binary tree can be created using dynamic arrays in which for each element in index n, 2n+1 and 2n+2 represents its left and right childs respectively.

so representation and level order traversal is very easy here.

but I think, in-order,post-order,pre-order is difficult.

my question is how can we create a binary tree like a binary search tree. ie. have a tree class which contains data, left and right pointers instead of arrays. so that we can recursively do traversal.

Answer 1

The tree class declaration part is, certainly, not the difficulty here. You basically stated exactly how to declare it, in the question:

class BinaryTree
{
private:
    int data;
    BinaryTree *left, *right;
};

This supports various forms of traversal, like so:

void Inorder(const BinaryTree *root)
{
  if(root == 0)
    return;
  Inorder(root->left);
  printf("now at %d\n", root->data);
  Inorder(root->right);
}

You should be able to deduce pre- and post-order traversals from that. In a real implementation, the tree would probably be templated to store random data, the traversal routines would be more general (with a user-data input, or perhaps user-supplied per-node callback, or whatever), of course.

Answer 2

Since I have not received any answers to the question which I asked, I will post my own implementaion of the binary tree using arrays. now I know that array implementaion is easier than i thought ,but still i dont know how to implement the same using linked lists.

the code is in c#

class BinaryTree { private static int MAX_ELEM = 100; //initial size of the array int lastElementIndex; int?[] dataArray;

    public BinaryTree()
    {
        dataArray = new int?[MAX_ELEM];
        lastElementIndex = -1;
    }

    //function to insert data in to the tree
    //insert as a complete binary tree
    public void insertData(int data)
    {
        int?[] temp;
        if (lastElementIndex + 1 < MAX_ELEM)
        {
            dataArray[++lastElementIndex] = data;
        }
        else
        {  //double the size of the array on reaching the limit
            temp = new int?[MAX_ELEM * 2];
            for (int i = 0; i < MAX_ELEM; i++)
            {
                temp[i] = dataArray[i];
            }
            MAX_ELEM *= 2;
            dataArray = temp;
            dataArray[++lastElementIndex] = data;
        }
    }

    //internal function used to get the left child of an element in the array
    int getLeftChild(int index) {
        if(lastElementIndex >= (2*index+1))
            return (2*index + 1);
        return -1;
    }

    //internal function used to get the right child of an element in the array
    int getRightChild(int index) {
        if(lastElementIndex >= (2*index+2))
            return (2*index + 2);
        return -1;
    }
    //function to check if the tree is empty
    public bool isTreeEmpty() {
        if (lastElementIndex == -1)
            return true;
        return false;
    }

    //recursive function for inorder traversal
    public void traverseInOrder(int index) {
        if (index == -1)
            return;
        traverseInOrder(getLeftChild(index));
        Console.Write("{0} ", dataArray[index]);
        traverseInOrder(getRightChild(index));
    }

    //recursive function for preorder traversal
    public void traversePreOrder(int index) {
        if (index == -1)
            return;
        Console.Write("{0} ", dataArray[index]);
        traversePreOrder(getLeftChild(index));
        traversePreOrder(getRightChild(index));
    }

    //recursive function for postorder traversal
    public void traversePostOrder(int index) {
        if (index == -1)
            return;
        traversePostOrder(getLeftChild(index));
        traversePostOrder(getRightChild(index));
        Console.Write("{0} ", dataArray[index]);
    }

    //function to traverse the tree in level order
    public void traverseLevelOrder()
    {
        Console.WriteLine("\nPrinting Elements Of The Tree In Ascending Level Order\n");
        if (lastElementIndex == -1)
        {
            Console.WriteLine("Empty Tree!...press any key to return");
            Console.ReadKey();
            return;
        }
        for (int i = 0; i <= lastElementIndex; i++)
        {
            Console.Write("{0} ", dataArray[i]);
        }
        Console.WriteLine("\n");
    }


}

Answer 3

If I understand you correctly, you want to create a binary tree from an array

int[] values = new int[] {1, 2, 3, 4, 5};
BinaryTree tree = new BinaryTree(values);

this should prepopulate the binary tree with the values 1 - 5 as follows:

    1
   / \
  2   3
 / \
4   5

this can be done using the following class:

class BinaryTree
{
    int value;
    BinaryTree left;
    BinaryTree right;

    public BinaryTree(int[] values) : this(values, 0) {}

    BinaryTree(int[] values, int index)
    {
        Load(this, values, index);
    }

    void Load(BinaryTree tree, int[] values, int index)
    {
        this.value = values[index];
        if (index * 2 + 1 < values.Length)
        {
            this.left = new BinaryTree(values, index * 2 + 1);
        }
        if (index * 2 + 2 < values.Length)
        {
            this.right = new BinaryTree(values, index * 2 + 2);
        }
    }
}

Answer 4

If you're after source for a comprehensive BinaryTree implementation you can learn from have a look at The C5 Generic Collection Library.