1

If I have a node class(es) that can accept a generic type for it's key value:

class Node<K extends Comparable<K>> implements Comparable<Node<K> {
    ...
}

class KeyValueNode<K extends Comparable<K>, V> extends Node<K> {
    ...
}

Is it possible to declare a generic binary tree class that accepts a generic type of node, which can contain a generic type of key value? I thought it would look something like this....

class BinaryTree<N<K>> {
    N<K> root;
    BinaryTree<N<K>> left, right;
    ...
}

Apologies for any glaring misunderstandings, I'm still trying to get the hang of generics and the syntax in Java, would greatly appreciate any help or insights.

Thanks!

xlm
  • 6,854
  • 14
  • 53
  • 55

3 Answers3

1

A binary tree structure will essentially just hold a reference to the root node. So it should have the same type parameters as its nodes:

class BinaryTree<K extends Comparable<K>> {

    Node<K> root;
}

Or for the key-value design:

class KeyValueBinaryTree<K extends Comparable<K>, V> {

    KeyValueNode<K, V> root;
}

Note that it's debatable whether an enclosing tree class is necessary, since it's the nodes that are pointing to each other.

Paul Bellora
  • 54,340
  • 18
  • 130
  • 181
  • Thanks for the clear answer Paul. Is it possible though to make the node type generic? I got something like this: class BinaryTree, K extends Comparable> { That being said, it kinda fell through once I tried to specify the specific insert methods for different node types – xlm Apr 23 '12 at 07:30
0

You can say:

class BinaryTree<N extends Node<N>> {
  Node<N> root; 
  // or even better: N root;
  BinaryTree<N> left, right;
}

Having BinaryTree<Node<K>> is not parameterizing the class as is the purpose of defining a generic type.

nobeh
  • 9,784
  • 10
  • 49
  • 66
  • Not sure why `N` would be self referencing. – Paul Bellora Apr 23 '12 at 02:23
  • What place exactly? `BinaryTree` is parameterized on some `N` that should be an instance/extension of `Node` of `N`. – nobeh Apr 23 '12 at 08:56
  • Shouldn't the tree contain nodes of some `Comparable` type, rather than nodes of nodes of nodes...? – Paul Bellora Apr 23 '12 at 14:33
  • Since `Node` is `Comparable` so any `N extends Node` should also be. The original idea of self-referencing comes from the fact that author of the question indicated `BinaryTree>` which is wrong in Java. Other than that, it's not as recursive as you interpret; there are some samples on this; e.g. [Java Enums](http://stackoverflow.com/a/1331023/248082) and another random [sample](http://musingsofaprogrammingaddict.blogspot.com/2009/01/visitor-pattern-generic-and-still-type.html). Thanks for the discussion. – nobeh Apr 23 '12 at 17:20
0

This is how I would write a generic binary tree class

public class BinaryTree<N extends Node<K>, K extends Comparable> {
    N root;
    BinaryTree<N, K> left, right;
}

(Although I assume you would not really story the BinaryTree in a binary tree and that was just for your example to show how it could be declared)

Bruce Lowe
  • 6,063
  • 1
  • 36
  • 47
  • Why is it not a good idea to have a BinaryTree contain a Node and left and right BinaryTree? – xlm Apr 22 '12 at 07:56