simple_binary_tree/
lib.rs

1#![allow(unused)]
2
3use std::{cell::RefCell, fmt::Display, rc::Rc};
4
5#[cfg(feature = "Btree")]
6
7#[derive(Debug, PartialEq, Eq)]
8pub struct Node<T> {
9    pub value: T,
10    pub left: Option<Rc<RefCell<Node<T>>>>,
11    pub right: Option<Rc<RefCell<Node<T>>>>,
12}
13
14#[derive(Debug, PartialEq, Eq)]
15pub struct Tree<T> {
16    pub root: Option<Rc<RefCell<Node<T>>>>
17}
18
19impl<T> Tree<T>
20where 
21    T: PartialOrd + Clone + Display
22{
23    pub fn new(val: T) -> Self {
24        let node = Rc::new(RefCell::new(Node {
25            value: val,
26            left: None,
27            right: None,
28        }));
29
30        Tree {
31            root: Some(Rc::clone(&node))
32        }
33    }
34
35    pub fn print(&self) {
36        if let Some(ref node) = self.root {
37            Tree::tree_view(node, 0);
38        }               
39    }
40
41    fn tree_view(node: &Rc<RefCell<Node<T>>>, depth: usize) {
42        let node_borrow = node.borrow();
43
44        if let Some(ref right) = node_borrow.right {
45            Tree::tree_view(right, depth + 1);
46        }
47
48        println!("{:space$}{}", " ", node_borrow.value, space = depth * 5);
49        
50        if let Some(ref left) = node_borrow.left {
51            Tree::tree_view(left, depth + 1);
52        }
53    }
54
55    pub fn insert(&self, item: T) {
56       if let Some(ref root) = self.root {
57        Self::insert_node(Rc::clone(root), item);
58       }        
59    }
60
61    fn insert_node(node: Rc<RefCell<Node<T>>>, item: T) {        
62        let mut borrow_node = node.borrow_mut();
63        if borrow_node.value > item {
64            match borrow_node.left {
65                Some(ref t) => Tree::insert_node(Rc::clone(t), item),
66                None => {
67                    let new_node = Rc::new(RefCell::new(
68                        Node {
69                            value: item,
70                            left: None,
71                            right: None,
72                        }
73                    ));
74                    borrow_node.left = Some(new_node);
75                }
76            }
77        } 
78        else if borrow_node.value < item {
79            match borrow_node.right {
80                Some(ref t) => Tree::insert_node(Rc::clone(t), item),
81                None => {
82                    let new_node = Rc::new(RefCell::new(
83                        Node {
84                            value: item,
85                            left: None,
86                            right: None,
87                        }
88                    ));
89                    borrow_node.right = Some(new_node);
90                }
91            }  
92        }
93        
94    }
95}
96
97pub fn run(list: &Vec<i32>) {
98
99    let tree = Tree::new(list[0]);
100    for (index, &elem) in list.iter().enumerate() {
101        if index > 0 {
102            tree.insert(elem);        
103        }
104    }
105
106    tree.print();
107}
108
109
110