CODEWITHSUNDEEP
javabinary-tree
Nyx
Nyx

Reputation: 1374

What should a Tree class contain?

My class is currently doing Binary Trees as part of our data structures unit. I understand that the Node class must have 3 parameters (value, left node, right node) in its constructor. As part of a requirement, we must have a Tree class. What is the purpose of a tree class? Is it for managing the entire set of Nodes? Does it simply contain the functions necessary to insert, remove and search for specific Nodes?

Thank you in advance.

My Node class:

class Node {
protected int data;
protected leftNode;
protected rightNode;

Node (int data, Node leftNode, Node rightNode){
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
}

Upvotes: 1

Views: 571

Answers (5)

Luis Casillas
Luis Casillas

Reputation: 30227

The assumption is, as you suspect, a little bit flawed. The Node type that you have defined is a perfectly fine instance of a binary tree.

Jack mentions that you want to have a Tree type around the whole set of nodes in order to provide operations like getRoot, inserts, deletes and so on. This is of course not a bad idea, but it is by no means a requirement. Many of these operations could go on Node itself, and you don't necessarily have to have all of these operations; for example, there are arguments both for and against having a getRoot operation. An argument against it is that if you have an algorithm that at one point only needs a subtree, then the Tree object that holds on to the root Node prevents garbage collection of Nodes that your algorithm no longer needs.

But more generally, the real question that needs to be asked here is this: which of the things you're dealing are interface, and which are implementation? Because it's one thing if you want to expose binary trees as an interface to callers, and another if you want to provide some sort of finite map as the interface, and the binary tree is just an implementation detail. In the former case, the client would "know" that a tree is either null or a Node with a value and branches, and would be allowed to, for example, recurse on the structure of the tree; in the latter case, all that the client would "know" is that your class supports some form of put, get and delete operations, but it's not allowed to rely on the fact that this is stored as a search tree. In many variants of the latter case you indeed would use a Tree type as a front end to hide the nodes from the clients. (For example, Java's built-in java.util.TreeMap class does this.)

So the shortest answer is, really, it depends. The slightly longer answer is it depends on what the contract is between the binary tree implementation and its users; what things are the callers allowed to assume about the trees, what details of the binary tree are things that the author expects to be able to change in the future, etc.

Upvotes: 0

duffymo
duffymo

Reputation: 308743

The purpose of any data structure is to give you a way to hold onto collections of related values and manipulate them in meaningful ways.

A tree is a special kind of data structure. It's a good choice for data that is hierarchical: those with natural parent-child relationships. A binary tree has, at most, two children for every parent node.

One other feature of trees that deserves special mention is the fact that it's self-similar: every Node in a tree is itself the root of a sub-tree. Recursion exploits this fact.

Yes, those are good methods to start with. You might want to have a look at the java.util.Map interface for others that might be useful.

Upvotes: 1

Óscar López
Óscar López

Reputation: 235984

As I see it, a Tree class should hold a reference to the root node of the tree, and to methods and attributes that operate on the tree as a whole, as opposed to methods that belong to each node, like getLeft(), getValue().

For example, I'd define a size attribute in the Tree class, and the methods that add or remove nodes to the tree (which also happen to be in this class) would be responsible for keeping the size up to date.

Upvotes: 1

Jack
Jack

Reputation: 133557

Yes, it is supposed to give the functional interface of a Tree by encapsulating all the behavior and algorithms related to the internal structure.

Why this is good? Because you will define something that just provide some functionality and that works in a stand-alone way so that everyone should be able to use your tree class without caring about nodes, algorithms and whatever.

Ideally the class should be parametric so that you'll have Tree<T> and you'll be able to have generic methods for example

T getRoot()

Basically you'll have to project it so that it will allow you to

  • insert values
  • delete values
  • search values
  • visit the whole tree
  • whatever

Upvotes: 2

Matthias
Matthias

Reputation: 8180

"Is it for managing the entire set of Nodes?"

Yes.

"Does it simply contain the functions necessary to insert, remove and search for specific Nodes?"

Basically, yes. For that reason, it should contain at least a reference to the root node.

Upvotes: 0

Related Questions