Пример реализвации АТД дерево на языке С++

#include <algorithm>
#include <string>
#include <iostream>
#include "tree.hh"

using namespace std;

int main(int, char **)
   {
   tree<string> tr;
   tree<string>::iterator top, one, two, loc, banana;

   top=tr.begin();
   one=tr.insert(top, "one");
   two=tr.append_child(one, "two");
   tr.append_child(two, "apple");
   banana=tr.append_child(two, "banana");
   tr.append_child(banana,"cherry");
   tr.append_child(two, "peach");
   tr.append_child(one,"three");

   loc=find(tr.begin(), tr.end(), "two");
   if(loc!=tr.end()) {
   tree<string>::sibling_iterator sib=tr.begin(loc);
   while(sib!=tr.end(loc)) {
     cout << (*sib) << endl;
     ++sib;
     }
   cout << endl;
   tree<string>::iterator sib2=tr.begin(loc);
   tree<string>::iterator end2=tr.end(loc);
   while(sib2!=end2) {
     for(int i=0; i<tr.depth(sib2)-2; ++i)
        cout << " ";
     cout << (*sib2) << endl;
     ++sib2;
     }
   }
}



Пример реализвации АТД дерево на языке Python



>>> T = [["a", "b"], ["c"], ["d", ["e", "f"]]]
>>> T[0][1]
>>> T[2][1][0]
class Tree:
	def __init__(self, left, right):
		self.left = left
		self.right = right
>>> t = Tree(Tree("a", "b"), Tree("c", "d"))
>>> t.right.left
>>> t = Tree(Tree("a", Tree("b", Tree("c", Tree("d")))))
>>> t.kids.next.next.val



Пример реализвации АТД дерево на языке Java




public class BSTree<T1 extends Comparable<T1>, T2> {
        static class Node<T1, T2> {
                T1 key;
                T2 value;
                Node<T1, T2> left, right;

                Node(T1 key, T2 value) {
                        this.key = key;
                        this.value = value;
                }
        }
        private Node<T1, T2> root = null;

        public boolean containsKey(T1 k) {
                Node<T1, T2> x = root;
                while (x != null) {
                        int cmp = k.compareTo(x.key);
                        if (cmp == 0) {
                                return true;
                        }
                        if (cmp < 0) {
                                x = x.left;
                        } else {
                                x = x.right;
                        }
                }
                return false;
        }

        public T2 get(T1 k) {
                Node<T1, T2> x = root;
                while (x != null) {
                        int cmp = k.compareTo(x.key);
                        if (cmp == 0) {
                                return x.value;
                        }
                        if (cmp < 0) {
                                x = x.left;
                        } else {
                                x = x.right;
                        }
                }
                return null;
        }

        public void add(T1 k, T2 v) {
                Node<T1, T2> x = root, y = null;
                while (x != null) {
                        int cmp = k.compareTo(x.key);
                        if (cmp == 0) {
                                x.value = v;
                                return;
                        } else {
                                y = x;
                                if (cmp < 0) {
                                        x = x.left;
                                } else {
                                        x = x.right;
                                }
                        }
                }
                Node<T1, T2> newNode = new Node<T1, T2>(k, v);
                if (y == null) {
                        root = newNode;
                } else {
                        if (k.compareTo(y.key) < 0) {
                                y.left = newNode;
                        } else {
                                y.right = newNode;
                        }
                }
        }

        public void remove(T1 k) {
                Node<T1, T2> x = root, y = null;
                while (x != null) {
                        int cmp = k.compareTo(x.key);
                        if (cmp == 0) {
                                break;
                        } else {
                                y = x;
                                if (cmp < 0) {
                                        x = x.left;
                                } else {
                                        x = x.right;
                                }
                        }
                }
                if (x == null) {
                        return;
                }
                if (x.right == null) {
                        if (y == null) {
                                root = x.left;
                        } else {
                                if (x == y.left) {
                                        y.left = x.left;
                                } else {
                                        y.right = x.left;
                                }
                        }
                } else {
                        Node<T1, T2> leftMost = x.right;
                        y = null;
                        while (leftMost.left != null) {
                                y = leftMost;
                                leftMost = leftMost.left;
                        }
                        if (y != null) {
                                y.left = leftMost.right;
                        } else {
                                x.right = leftMost.right;
                        }
                        x.key = leftMost.key;
                        x.value = leftMost.value;
                }
        }
}




Пример реализвации АТД дерево на языке Haskell



data Ord key => BSTree key value = Leaf | Branch key value (BSTree key value) (BSTree key value)
                                   deriving (Show)

containsKey :: Ord key => BSTree key value -> key -> Bool
containsKey Leaf _ = False
containsKey (Branch key _ left right) k
    | k < key  = containsKey left k
    | k > key  = containsKey right k
    | k == key = True

get :: Ord key => BSTree key value -> key -> Maybe value
get Leaf _ = Nothing
get (Branch key value left right) k
    | k < key  = get left k
    | k > key  = get right k
    | k == key = Just value

add :: Ord key => BSTree key value -> key -> value -> BSTree key value
add Leaf k v = Branch k v Leaf Leaf
add (Branch key value left right) k v
    | k < key  = Branch key value (add left k v) right
    | k > key  = Branch key value left (add right k v)
    | k == key = Branch key value left right

remove :: Ord key => BSTree key value -> key -> BSTree key value
remove Leaf _ = Leaf
remove (Branch key value left right) k
    | k < key  = Branch key value (remove left k) right
    | k > key  = Branch key value left (remove right k)
    | k == key = if isLeaf right
                 then left
                 else Branch leftmostA leftmostB left right'
                     where
                       isLeaf Leaf = True
                       isLeaf _    = False
                       ((leftmostA, leftmostB), right') = deleteLeftmost right
                       deleteLeftmost (Branch key value Leaf right) = ((key, value), right)
                       deleteLeftmost (Branch key value left right) = (pair, Branch key value left' right)
                           where (pair, left') = deleteLeftmost left

fromList :: Ord key => [(key, value)] -> BSTree key value
fromList = foldr (\(key, value) tree -> add tree key value) Leaf

toList :: Ord key => BSTree key value -> [(key, value)]
toList tree = toList' tree []
    where
      toList' Leaf list = list
      toList' (Branch key value left right) list = toList' left ((key, value):(toList' left list))