Logo

Programming-Idioms

  • Go
  • C++

Idiom #17 Create a Tree data structure

The structure must be recursive. A node may have zero or more children. A node has access to its children nodes, but not to its parent.

type
  TTree = class
    Children: array of TTree;
    Data: TObject;
  end;     
type
generic
  TTree<_T> = class(TObject)
    Children: array of TObject;
    Data: _T;
  end;

type
  TStringTree = specialize TTree<String>;

This Example uses generics
type Tree[L any] struct {
	Label    L
	Children []*Tree[L]
}

The type parameter L is for arbitrary node label data.

A nil *Tree denotes the empty tree.
type Tree struct {
	Key keyType
	Deco valueType
	Children []*Tree
}

keyType should be easily comparable.
valueType is a type of value associated with current node.
Children is a slice of pointers.

Note that in Go you can call methods of pointer type *Tree even on a nil receiver (an empty tree).
#include <vector>
template<typename T>
struct Node{
  T value;
  std::vector<Node<T>> children;
};
typedef struct node_s
{
    int value;
    struct node_s *nextSibling;
    struct node_s *firstChild;
} node_t;
New implementation...
< > ⌨
programming-idioms.org 
type
  TTree = class
    Children: array of TTree;
    Data: TObject;
  end;     
type
generic
  TTree<_T> = class(TObject)
    Children: array of TObject;
    Data: _T;
  end;

type
  TStringTree = specialize TTree<String>;

type Tree[L any] struct {
	Label    L
	Children []*Tree[L]
}
type Tree struct {
	Key keyType
	Deco valueType
	Children []*Tree
}

template<typename T>
struct Node{
  T value;
  std::vector<Node<T>> children;
};
typedef struct node_s
{
    int value;
    struct node_s *nextSibling;
    struct node_s *firstChild;
} node_t;
type 'a Tree = {
	value: 'a;
	children: 'a tree list;
}
class Node<T>
{
 T value;
 List<Node<T>> childNodes;
}

struct Node(T){
    Node[] children;
    T data;
}

alias TreeOfIntegers = Node!(int);
class Node<T> {
  final T value;
  final List<Node<T>> children;
  Node(this.value, this.children);
}
  
-record( node,{
	value         :: any(),
	children = [] :: [node#{}]
}).
type node_t
  integer:: value
  type(node_t), pointer :: next_sibling;
  type(node_t), pointer :: first_child;
end type node_t
data Tree a = Node {
    value :: a,
    children :: [Tree a]
}
class Node {
  constructor (value, children = []) {
    this.value = value
    this.children = children
  }
}
class Tree<K,V> {
  K key;
  V deco;
  List<Tree<K,V>> children = new ArrayList<>();
}
local function Tree(v, c)
	return {
		val = v,
		children = c
	}
end
@interface Node:NSObject
@property id value; // id means any object value
@property NSMutableArray *children;
@end

// usage like
Node *n=[Node new];
n.value=@1;
[n.children addObject:otherNode];
[n.children removeLastObject];

// somewhere needed also
@implementation Node
-(instancetype)init {
  if (!(self=[super init])) return nil;
  _children=[NSMutableArray array];
  return self;
}
@end

final class Node {
    public function __construct(public array $children, public mixed $data) {}
}
class Tree
{
    public $children = [];
    public $data;
    
    public function __construct($data, $children)
    {
        $this->data = $data;
        $this->children = $children;
    }
}
my $tree = {
           'Root' => {
                 'Child1' => {
                       'GrandChild1' => {},
                       'GrandChild2' => {}
                 },
                 'Child2' => {}
           }
};
class Node:
    def __init__(self, value, *children):
        self.value = value
        self.children = list(children)
Node = Struct.new(:children)
parent = Node.new([])
parent.children << Node.new([])
struct Node<T> {
  value: T,
  children: Vec<Node<T>>,
}
case class Node[T](value: T, children: List[Node[T]] = Nil)
(define (make-tree value children)
  (cons value children))

(define (tree-value t) (car t))
(define (tree-first-child t) (cadr t))
(define (tree-rest-children t) (cddr t))