dsa_rust/hierarchies/
traits.rs

1// Traits for to make-a da tree
2///////////////////////////////
3
4/** Defines the a basic Tree ADT where P is a position, and T is a type */
5pub trait Tree<T> {
6    type Position;
7
8    // Fundamental methods
9    //////////////////////
10
11    /** Returns an iterable collection over the node's children
12
13    NOTE: To make this iterable into an iterator simply call something like
14    self.children(node).into\_iter() */
15    fn children(&self, node: Self::Position) -> Option<Vec<Self::Position>>;
16
17    /** Returns an immutable reference to the node's data type */
18    fn get<'a>(&'a self, node: &'a Self::Position) -> Option<&'a T>;
19
20    /** Returns the position of a node's parent, if it exists */
21    fn parent(&self, node: Self::Position) -> Option<Self::Position>;
22
23    // Maybe?
24    //fn size(&self) -> usize;
25    //fn is_empty(&self) -> bool;
26
27    // Query methods
28    ////////////////
29
30    /** Returns true if the specified position is the tree's root */
31    fn is_root(&self, node: Self::Position) -> bool;
32
33    /** Returns true if the specified position is external */
34    fn is_leaf(&self, node: Self::Position) -> bool;
35
36    // Derived methods
37    //////////////////
38
39    fn depth(&self, node: Self::Position) -> Option<usize>;
40
41    //fn height(&self, node: &T) -> usize;
42    fn height(&self, node: Self::Position) -> Option<usize>;
43
44    //NOTE: Is this really needed?
45    /** Returns the immediate number of children for a given node */
46    fn num_children(&self, node: Self::Position) -> Option<usize>;
47
48    //fn validate(&self, node: &Self::Position) -> bool;
49}
50
51/** Abstract interface definition for a binary tree type */
52pub trait BinaryTree<T>
53where
54    T: Clone + std::cmp::PartialEq,
55{
56    type Position;
57
58    /** Returns the position of the left child of a given node */
59    fn left(&self, node: Self::Position) -> Option<Self::Position>;
60
61    /** Returns the position of the right child of a given node */
62    fn right(&self, node: Self::Position) -> Option<Self::Position>;
63
64    /** Returns the position of the sibling of a given node */
65    fn sibling(&self, node: Self::Position) -> Option<Self::Position>;
66
67    //TODO
68    //fn add_root(n)
69    //fn add_left(p, n)
70    //fn add_right(p, n)
71    //fn set(p, n)
72    //fn attach(p, t1, t2)
73    //fn remove(p)
74}
dsa_rust/hierarchies/traits.rs

dsa_rust/hierarchies/
traits.rs
