Struct BinaryTree 

pub struct BinaryTree<T>
where
    T: Hash,
{
    pub root: Option<NodeId>,
    /* private fields */
}

The most basic tree in woodland. All nodes stored in the tree are BinaryTreeNode<T>s.

NOTE: The TreeOperations::insert() definition for this tree will call std::unimplemented as there is no invariant to fall back on to determine where to insert the node.

Example usage:

use woodland::prelude::*;
use woodland::binary_tree::BinaryTree;

/* Tree looks like the following:
 *
 *              4
 *          /       \
 *         2         6
 *       /   \     /   \
 *      1     3   5     7
 */

let mut new_tree = BinaryTree::<u8>::new();
let left_left_id = new_tree.create_node(1);
let left_right_id = new_tree.create_node(3);
let left_id = new_tree.create_node(2);
let right_id = new_tree.create_node(6);
let right_left_id = new_tree.create_node(5);
let right_right_id = new_tree.create_node(7);
new_tree.root = Some(new_tree.create_node(4));

let root_ref = new_tree.get_node_mut(new_tree.root.unwrap()).unwrap();
root_ref.set_left(Some(left_id));
root_ref.set_right(Some(right_id));

let left_ref = new_tree.get_node_mut(left_id).unwrap();
left_ref.set_left(Some(left_left_id));
left_ref.set_right(Some(left_right_id));

let right_ref = new_tree.get_node_mut(right_id).unwrap();
right_ref.set_left(Some(right_left_id));
right_ref.set_right(Some(right_right_id));

Fields

root: Option<NodeId>

The root node’s NodeId.

Trait Implementations

impl<'a, T> IterativeTreeOperations<BinaryTreeNode<T>> for BinaryTree<T>

where T: Hash + Eq + PartialEq,

fn preorder_iter(&self) -> Box<dyn Iterator<Item = &BinaryTreeNode<T>> + '_>

Get a preorder traveral iterator.

fn inorder_iter(&self) -> Box<dyn Iterator<Item = &BinaryTreeNode<T>> + '_>

Get an inorder traversal iterator.

fn postorder_iter(&self) -> Box<dyn Iterator<Item = &BinaryTreeNode<T>> + '_>

Get a postorder traversal iterator.

impl<T> TreeOperations<BinaryTreeNode<T>> for BinaryTree<T>

where T: Hash + Eq + PartialEq,

fn new() -> Self

Create a new instance of the tree with an empty root.

fn create_node(&mut self, data: T) -> NodeId

Genereate a new mutable reference to a NodeType. You must call this function to get new references since we are allocating all references in the Arena.

fn count(&self) -> usize

Get the number of nodes in the tree.

fn is_empty(&self) -> bool

Returns true if there are no nodes in the tree, and returns false otherwise.

fn get_node(&self, node_id: NodeId) -> Option<&BinaryTreeNode<T>>

Get a refrence to a NodeType<T> from a given NodeId, if a node with the specified NodeId exists in the tree.

fn get_node_mut(&mut self, node_id: NodeId) -> Option<&mut BinaryTreeNode<T>>

Get a mutable reference to a NodeType<T> from a given NodeId, if a node with the specified NodeId exists in the tree.

fn search(&self, node_id: NodeId) -> bool

Search to see if a node is inside the tree.

fn insert(&mut self, _node: NodeId)

Insert a node into the tree.