Logo

Programming-Idioms

  • Python
  • Obj-c

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. 

@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 Node:
	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None
class Node:
  def __init__(self, data, left_child, right_child):
    self.data = data
    self._left_child = left_child
    self._right_child = right_child
type Tree_Node;
type Tree_Node_Access is access Tree_Node;
type Tree_Node is record
   Value: Integer;
   Left, Right: Tree_Node_Access;
end record;
New implementation...
< > ⌨
programming-idioms.org 
@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

class Node:
	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None
class Node:
  def __init__(self, data, left_child, right_child):
    self.data = data
    self._left_child = left_child
    self._right_child = right_child
type Tree_Node;
type Tree_Node_Access is access Tree_Node;
type Tree_Node is record
   Value: Integer;
   Left, Right: Tree_Node_Access;
end record;
struct treenode{
  int value;
  struct treenode* left;
  struct treenode* right;
}
type treenode =
    Node of {
        value: int;
        left: treenode;
        right: treenode
    }
    | Leaf
struct binary_tree
{
 int data;
 binary_tree *left = nullptr, *right = nullptr;
};
class BinaryTree<T>:IComparable<T>
{
 T value;
 BinaryTree<T> leftChild;
 BinaryTree<T> rightChild;
}
struct BinaryTree(T)
{
	T data;
	BinaryTree* left;
	BinaryTree* right;
}
class Node<T> {
  final T value;
  Node<T> left, right;
  Node(this.value, {this.left, this.right});
}
defmodule BinaryTree do
	defstruct data: nil, left: nil, right: nil
end
-type binary_tree(T) ::
	#{ data := T
	 , left := binary_tree(T)
	 , right := binary_tree(T)
	 }.
type binary_tree
    integer :: value
    type(binary_tree), allocatable :: left
    type(binary_tree), allocatable :: right
end type binary_tree
type BinTree[L any] struct {
	Label       L
	Left, Right *BinTree[L]
}
type BinTree struct {
	Label       valueType
	Left, Right *BinTree
}

class BinTree<T extends Comparable<T>>{
   T value
   BinTree<T> left
   BinTree<T> right
}
data BT x = BEnd | BNode (BT x) x (BT x)

class Node {
  constructor (data) {
    this.data = data
    this.left = null
    this.right = null
  }
}
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));
 }
class BinTree<T extends Comparable<T>>{
   T value;
   BinTree<T> left;
   BinTree<T> right;
}

data class Node(
    val key: Int,
    val left: Node? = null,
    val right: Node? = null
)
(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)))

local function BinTree(v, l, r)
	return {
		val = v,
		left = l,
		right = r
	}
end
class BNode
{
    public $data;
    public $lNode;
    public $rNode;

    public function __construct($item)
    {
        $this->data = $item;
        $this->lNode = null;
        $this->rNode = null;
    }
}
type
  generic BinTree<T> = class
    Value: T;
    Left, Right: BinTree;
  end;   
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

Node = Struct.new(:left, :right, :value)
parent = Node.new(Node.new, Node.new)
struct BinTree<T> {
    value: T,
    left: Option<Box<BinTree<T>>>,
    right: Option<Box<BinTree<T>>>,
}
case class BinaryTree[T <: Ordered[T]](
	value: T,
	left: Option[BinaryTree[T]],
	right: Option[BinaryTree[T]]
)
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)
(define (make-btree value left right)
  (cons value (cons left right)))

(define (btree-value bt) (car bt))
(define (btree-left bt) (cadr bt))
(define (btree-right bt) (cddr bt))
Object subclass: #TreeNode 
    instanceVariableNames: 'left right'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'Trees'.