Little help with binary tree would be appreciated

Question

I'm trying to create binary tree that contains two int values and one string value sorted in the lexicographic, but I'm not sure what to do. I've created an array list, which has been already sorted, but the binary tree has to be a reference-based which is not sorted and I'm thinking about sorting the list while creating it. Can any one help with this? Any brief idea would be appreciated.

Answer 1

Binary tree is a recursive thing. Make a class called BinaryTree (i hope you are in C++, or .NET or JAVA) that has two references to two other BinaryTrees (null by default). Then make an insert function that is recursive.

I don't know what you are trying to accomplish, but when building a binary tree, arrays are usually nowhere to be found.

Answer 2

It sounds like you already have a data structure to store your two int values and a string (since you have them sorted in an array list). You can include this data structure in a "tree node". A node typically has a reference pointer to a parent node (unless it is the root node) and 2 child nodes.

Since you want the tree to be sorted what you're really after is a special form of binary tree called a heap. The link to the Binary Heap wikipedia page below has an algorithm to show how to sort a binary heap.

http://en.wikipedia.org/wiki/Binary_heap

Here's some more general information on heaps and trees.

http://en.wikipedia.org/wiki/Binary_tree

http://en.wikipedia.org/wiki/Heap_(data_structure)

EDIT: You don't have to use a literal tree structure to store the your data in a tree form. It is perfectly acceptable to build a tree using an array. Instead of using reference pointers (parent and 1 or 2 child nodes) you can compute an index into the array. Each set of children is considered a "row" in the tree. The root element is on the zero row. It's two children are on the first row. The children of the root's children are on the second row, and so on.

Using this pattern the children of any node can be found using array[2*n+1] and array[2*n+2] where n is the row of the parent node. The parent of any node can be found by using array[floor( (n-1)/2)].

Answer 3

You first should create a class to store your data and implement Comparable or use a Comparator.

public class Data { // Implement Comparable...
    private String s;
    private int n1;
    private int n2;

    // Implement constructors, getters, setters based on what you need...

    // Implement compareTo (+ equals + hashCode) unless your going with Comparator
}

Then use a Collection that implements SortedSet to store your data, TreeSet is a good choice. The objects in the SortedSet are stored by reference so if you modify a value set in a local variable it will be modified in the collection as well.

Edit: If I understood your question about reference based lists correctly the following is possible in Java.

List<Data> dataList = // Create list and add data into it.
Data data = dataList.get(4);
data.setS(103); // Modifies S in the local data-object and in dataList because they are reference based.