0

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.

Improve this question
4
  • What do you mean with a "binary tree that contains two int values and one string"? Each node on the tree contains these 3 values? And if so, how do you want to sort them? Commented Jun 4, 2010 at 13:12
  • Do you want a sorted collection containing data objects like class Data { String s; int n1; int n2; }? Then I recommend creating your own class which I presented here, implement the Comparable interface and use a SortedSet to store the information. Commented Jun 4, 2010 at 13:16
  • Yes!! Each node should contain those 3 values and I need to sort by the string value which is the name in the lexicographic. I was trying to build them with the array list. I have to create reference based list as far as I know building a tree with array list is not a reference based if I'm correct. Commented Jun 4, 2010 at 13:22
  • You should mark an answer as accepted, provide your own answer or tell us more information so we can help you better. Now it is a bit unclear if you were able to solve your problem or not. Commented Jun 4, 2010 at 15:32

3 Answers 3

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Agreed. Use an array if you're doing something like a heap. If it's not a balanced binary tree, then arrays become a problem.
Thanx for your posting!! I'm trying to create a reference based sorted list from an unsorted array.
0

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.
Improve this answer

4 Comments

Thnx for ur posting. I've used a comparator for sorting the array list and It has been sorted, but I realised that I need to create a reference based one. According to my mere brain I'm not allowed to use an array list for a reference based list. Is it correct?? Correct me if I'm not. I'm still not familiar with java.......
Oh never mind what I've posted above lol so basically I need to create a reference based list from an unsorted array and sort that reference based list in the lexicographic.
I added some info in my answer, hopefully understood your question right.
Thank you for ur answer and sorry for being late. I think I misunderstood whole concept of this. First of all I have to create an array-based implementation of the ADT List and secondly I need to create a reference-based implementation of the ADT sorted list!!
0

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)].

Improve this answer

1 Comment

Thanks for your help but I have to create a renference based one so that array list will not do any good........ sigh :( so according to what youve posted I need to create a heap for sorting nodes in the lexicographic?? Is it correct??

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.