feat: level order recursive implementationHEADmaster

4 files changed, 68 insertions, 11 deletions

diff --git a/Cargo.lock b/Cargo.lock
index de963e3..d6a4e4a 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3,5 +3,5 @@
 version = 3
 
 [[package]]
-name = "tree-rs"
-version = "0.1.0"
+name = "tree"
+version = "0.0.3"
diff --git a/Cargo.toml b/Cargo.toml
index 09c5232..9ac4409 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -1,6 +1,6 @@
 [package]
 name = "tree"
-version = "0.0.1"
+version = "0.0.3"
 edition = "2021"
 authors = ["Zhongheng Liu <z.liu@outlook.com.gr>"]
 description = "Rust implementation of a binary tree data structure. Unstable and a work in progress."
diff --git a/src/tests.rs b/src/tests.rs
index 3c029b9..7b377d3 100644
--- a/src/tests.rs
+++ b/src/tests.rs
@@ -1,15 +1,32 @@
-use crate::tree;
-
+use crate::tree::{self, InsertDirection};
+fn ascending_predicate(l: i32, r: i32) -> InsertDirection {
+        if l >= r {
+            return InsertDirection::Right;
+        } else {
+            return InsertDirection::Left;
+        }
+    }
 #[test]
 pub fn test_tree_init() {
     let _ = tree::Tree::new(1);
 }
-
+#[test]
+pub fn test_tree_level_order_print() {
+    let mut t = tree::Tree::new(1);
+    let arr = vec![12, 567, 45, 56, 77, 293, 10, 2];
+    for i in arr {
+        t.insert(i, ascending_predicate);
+    }
+    t.level_order();
+}
 #[test]
 pub fn test_tree_insert() {
     let mut t = tree::Tree::new(1);
-    t.insert_left(12);
-    t.insert_right(13);
-    t.insert_left(15);
+    
+    let arr = vec![12, 567, 45, 56, 77, 293, 10, 2];
+    for i in arr {
+        t.insert(i, ascending_predicate);
+    }
     println!("{}", t);
+
 }
diff --git a/src/tree.rs b/src/tree.rs
index e217b37..134b614 100644
--- a/src/tree.rs
+++ b/src/tree.rs
@@ -7,7 +7,11 @@ use std::fmt::Display;
 pub struct Tree<T: Copy> {
     pub root_node: TreeNode<T>,
 }
-impl<T: Copy> Tree<T> {
+pub enum InsertDirection {
+    Left,
+    Right,
+}
+impl<T: Copy + Display> Tree<T> {
     /// Takes reducer function input with following signature.
     ///
     /// The caller should ensure that reducer function returns same type as
@@ -40,6 +44,17 @@ impl<T: Copy> Tree<T> {
     pub fn insert_right(&mut self, v: T) {
         self.root_node.insert_right(v);
     }
+    pub fn insert(&mut self, v: T, predicate: fn(T, T) -> InsertDirection) {
+        self.root_node.insert(v, predicate);
+    }
+    pub fn level_order(&self) {
+        let mut a: Vec<T> = vec![];
+        self.root_node.level_order_rec(0, &mut a);
+        for elem in a {
+            print!("{},", elem);
+        }
+        println!();
+    }
 }
 impl<T: Display + Copy> Display for Tree<T> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
@@ -77,7 +92,6 @@ impl<T: Copy + Display> Display for TreeNode<T> {
     }
 }
 impl<T: Copy> TreeNode<T> {
-
     /// Initialises a new node for a Tree.
     pub fn new(v: T) -> TreeNode<T> {
         TreeNode {
@@ -119,4 +133,30 @@ impl<T: Copy> TreeNode<T> {
         }
         self.right = Some(Box::new(TreeNode::new(value)))
     }
+    pub fn insert(&mut self, item: T, predicate: fn(T, T) -> InsertDirection) {
+        match predicate(item, self.value) {
+            InsertDirection::Left => {
+                if let Some(node) = &mut self.left {
+                    node.insert(item, predicate);
+                } else {
+                    self.left = Some(Box::new(TreeNode::new(item)))
+                }
+            }
+            InsertDirection::Right => {
+                if let Some(node) = &mut self.right {
+                    node.insert(item, predicate);
+                } else {
+                    self.right = Some(Box::new(TreeNode::new(item)))
+                }
+            }
+        }
+    }
+    pub fn level_order_rec(&self, level: usize, arr: &mut Vec<T>) {
+        if arr.len() < level {
+            arr.push(self.value);
+        }
+        arr.insert(level, self.value);
+        if let Some(node) = &self.left { node.level_order_rec(level + 1, arr);}
+        if let Some(node) = &self.right { node.level_order_rec(level + 1, arr);}
+    }
 }