Idiom #9 Create a Binary Tree data structure
The structure must be recursive because left child and right child are binary trees too. A node has access to children nodes, but not to its parent.
- Ada
- Caml
- C++
- C#
- D
- Dart
- Elixir
- Erlang
- Fortran
- Go
- Go
- Groovy
- Haskell
- JS
- Java
- Java
- Kotlin
- Lisp
- Lua
- Obj-C
- PHP
- Pascal
- Perl
- Python
- Python
- Ruby
- Rust
- Scala
- Scala
- Scheme
- Smalltalk
type BinTree[L any] struct {
Label L
Left, Right *BinTree[L]
}
The type parameter L is for arbitrary node label data
class BinTree<T extends Comparable<T>>{
T value;
BinTree<T> left;
BinTree<T> right;
}
Note that with this design an empty tree is null, and thus is not an instance of BinTree.
interface Tree<T>{
boolean search(T x);
}
class Nil<T extends Comparable<? super T>> implements Tree<T>{
public boolean search(T x) { return false; }
}
class Node<T extends Comparable<? super T>> implements Tree<T> {
T item; Tree<T> left; Tree<T> right;
public Node(T i, Tree<T> l, Tree<T> r) {
item=i; left=l; right=r; }
public boolean search(T x) {
int cmp = x.compareTo(item);
return cmp==0 || (cmp<0 && left.search(x)) || (cmp>0 && right.search(x));
}
don't have room for more
(defclass node ()
((value
:initarg :value :initform nil
:accessor node-value)
(left-child
:initarg :left-child :initform nil
:accessor node-left-child)
(right-child
:initarg :right-child :initform nil
:accessor node-right-child)))
@interface Node:NSObject
@property id value; // id means any object value
@property Node *left,*right;
@end
// usage like
Node *n=[Node new];
n.value=@1;
n.left=otherNode;
n.right=anotherNode;
// somewhere needed also
@implementation Node @end
The plain C solution is available too; the object-oriented solution probably better for most cases
class BNode
{
public $data;
public $lNode;
public $rNode;
public function __construct($item)
{
$this->data = $item;
$this->lNode = null;
$this->rNode = null;
}
}
class Tree::Binary {
has 'left', is => 'ro', isa => Maybe[InstanceOf['Tree::Binary']];
has 'right', is => 'ro', isa => Maybe[InstanceOf['Tree::Binary']];
has 'val', is => 'ro', isa => Int;
}
my $t = Tree::Binary->new(
val => 42,
left => Tree::Binary->new(val => 23),
right => Tree::Binary->new(
val => 1729,
right => Tree::Binary->new(val => -1)
)
);
__END__
42
↙ ↘
23 1729
↙ ↘ ↙ ↘
∅ ∅ ∅ -1
sealed trait Tree[T <: Ordered[T]]:
def search(x: T): Boolean
final case class Nil[T <: Ordered[T]]() extends Tree[T]:
override def search(x: T): Boolean = false
final case class Node[T <: Ordered[T]](
item: T,
left: Tree[T],
right: Tree[T]
) extends Tree[T]:
override def search(other: T): Boolean =
item compare other match
case 0 => true
case n if n < 0 => left.search(other)
case n if n > 0 => right.search(other)
ADT style
programming-idioms.org