Struct BinTree

pub struct BinTree {
    pub root: Node,
    pub left: Option<Box<BinTree>>,
    pub right: Option<Box<BinTree>>,
}

A Binary Tree has a root node, and possibly a left and right subtree. Option is used to allow the possibility that a left/right subtree is not defined. Box is used to control recursive errors: i.e. there is only a Box when there is a subtree

Fields

root: Node

Holds the Root Node of the tree

left: Option<Box<BinTree>>

The Possibility of a left subtree

right: Option<Box<BinTree>>

The Possibility of a right subtree

Implementations

impl BinTree

pub fn find(&self, key: i64) -> bool

Find is called by a tree and inputs a key. returns true if the key is in the node.

use unsafe_bst::*;
let mut tree = binary_tree::BinTree{..Default::default()};
tree.add_node(nodes::Node{val:14});
tree.add_node(nodes::Node{val:15});
tree.add_node(nodes::Node{val:13});
assert_eq!(tree.find(17),false);
assert!(tree.find(14));

pub fn add_node(&mut self, node: Node)

Add is called by a tree and inputs a Node. The node is added to the tree if it not already in the tree, following basic BST rules i.e. smaller values of root are to the left, larger values to the right.

use unsafe_bst::*;
let mut tree = binary_tree::BinTree{..Default::default()};
tree.add_node(nodes::Node{val:14});

pub fn print_def(&self)

pub fn print(&self, spacing: i64) -> String

Prints a tree in the following format:

     left-subtree
 root
     right-subtree
 

spacing should be 0, as 5 spaces are hardcoded into print for each non-root line.

use unsafe_bst::*;
let mut tree = binary_tree::BinTree{..Default::default()};
tree.add_node(nodes::Node{val:14});
tree.add_node(nodes::Node{val:15});
tree.add_node(nodes::Node{val:13});
tree.print(0);

pub fn print_2(&self, spacing: i64, spacing2: i64) -> String

Prints a tree in the following format:

  left-subtree
 root
  right-subtree
 

takes 2 params, spacing: how many spaces should the root have, and spacing2: how many spaces for each subtree call

use unsafe_bst::*;
let mut tree = binary_tree::BinTree{..Default::default()};
tree.add_node(nodes::Node{val:14});
tree.add_node(nodes::Node{val:15});
tree.add_node(nodes::Node{val:13});
tree.print(0);

pub fn delete(&mut self, node: i64)

Deletes an inputted value from the tree. Follows BST deletion rules:

1. Leaf node (no left/right-subtree): Node is ‘deleted’ (set to -1)
2. Single Child Node (either left or right-subtree): values of tree are shifted up
3. Two child nodes (left and right sub-tree): successor() is used to find the best replacement for the deleted node Library Creator Note: This function uses an enum and its types as a way to use GOTO functionality. This is to get around borrowing rules.

use unsafe_bst::*;
let mut tree = binary_tree::BinTree{..Default::default()};
tree.add_node(nodes::Node{val:14});
tree.add_node(nodes::Node{val: 3});
tree.delete(14);
//Tree now has root = 3
tree.print(0);

pub fn successor(&mut self) -> &mut BinTree

Successor returns a BinTree of the next largest value in the tree from the root (of self)

use unsafe_bst::*;
let mut tree = binary_tree::BinTree{..Default::default()};
tree.add_node(nodes::Node{val:14});
tree.add_node(nodes::Node{val:17});
tree.add_node(nodes::Node{val:15});
assert_eq!(15,tree.successor().root.val);

pub fn shift_left(&mut self) -> &mut BinTree

Shift Left returns the left-subtree of a tree

pub fn shift_right(&mut self) -> &mut BinTree

Shift Right returns the right-subtree of a tree

pub fn get_predecessor(&mut self) -> Node

Get Predecessor returns the Node with the next smallest value to root (self)

pub fn get_successor(&mut self) -> Node

Get Successor returns the Node with the next largest value to root (self)

pub fn balance(&mut self, s: &mut Stats) -> BinTree

Balance attempts to make a perfect BST when it can, else it makes a tree with minimum height

pub fn height(&mut self, i: i64, v: &mut Vec<i64>)

Trait Implementations

impl Clone for BinTree

fn clone(&self) -> BinTree

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BinTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for BinTree

fn default() -> Self

Returns the “default value” for a type.