binary_sort_tree/
lib.rs

1//! 二叉排序树
2
3use std::fmt;
4
5pub struct Tnode{
6	data:isize,
7	lchild:Option<Box<Tnode>>,
8	rchild:Option<Box<Tnode>>,
9}
10
11impl fmt::Display for Tnode{
12	fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{
13		write!(f,"[{}",self.data)?;
14		match &self.lchild{
15			Some(c)=>c.fmt(f)?,
16			None=>(),
17		}
18		match &self.rchild{
19			Some(c)=>c.fmt(f)?,
20			None=>(),
21		}		
22		write!(f,"]")
23	}
24}
25
26impl Tnode{
27	pub fn new(data:isize,lchild:Option<Tnode>,rchild:Option<Tnode>)->Tnode{
28		let l = match lchild{
29			Some(t)=>Some(Box::new(t)),
30			None=>None,
31		};
32		let r = match rchild{
33			Some(t)=>Some(Box::new(t)),
34			None=>None,
35		};
36		Tnode{
37			data,
38			lchild:l,
39			rchild:r,
40		}
41	}
42	
43	pub fn search(&self,key:isize)->Option<&Tnode>{
44		let mut p = self;
45		while p.data !=key{
46			if key < p.data{
47				match &p.lchild{
48					Some(pl)=>p = &pl,
49					None=>return None,
50				}
51			}else {
52				match &p.rchild{
53					Some(pr)=>p = &pr,
54					None=>return None,				
55				}
56			}
57		}
58		Some(p)
59	}
60	
61	pub fn insert(&mut self,key:isize)->OptionResult{
62		let n = Tnode::new(key,None,None);
63		let mut p = self;
64		while p.data !=key{
65			if key < p.data{
66				match p.lchild.as_mut(){
67					Some(pl)=>{
68						return pl.insert(key);
69					},
70					None=>{
71						p.lchild = Some(Box::new(n));
72						return OptionResult::Success;
73					},
74				}
75			}else {
76				match p.rchild.as_mut(){
77					Some(pr)=>{
78						return pr.insert(key);
79					},
80					None=>{
81						p.rchild = Some(Box::new(n));
82						return OptionResult::Success;
83					},		
84				}
85			}
86		}
87		OptionResult::IsThere
88	}
89	
90	/// 第一种删除节点的方法
91	pub fn del(mut self,key:isize)->Option<Box<Self>>{
92		if key < self.data{
93			self.lchild=match self.lchild{
94				Some(c)=>{
95					c.del(key)
96				},
97				None=>{
98					None
99				}
100			};
101		}else if key > self.data{
102			self.rchild=match self.rchild{
103				Some(c)=>{
104					c.del(key)
105				},
106				None=>{
107					None
108				}
109			};			
110		}else{
111			let lchild = self.lchild;
112			let rchild = self.rchild;
113			
114			match lchild{
115				Some(lc)=>{
116					match rchild{
117						Some(rc)=>{
118							//2个孩子
119							self = *lc;
120							if let None = &self.rchild{
121								self.rchild=Some(rc);
122							}else{
123								let mut r_d = &mut self;
124								while let Some(c) = r_d.rchild.as_mut(){
125									if let None = c.rchild{
126										c.rchild = Some(rc);
127										break;
128									}
129									r_d = c;
130								}
131							}
132							return Some(Box::new(self));
133						},
134						None=>{
135							//有左没右
136							return Some(lc);
137						},
138					}
139				},
140				None=>{
141					match rchild{
142						Some(rc)=>{
143							//没左有右
144							return Some(rc);
145						},
146						None=>{
147							//0个孩子
148							return None;
149						},
150					}					
151				},
152			}
153		}
154		Some(Box::new(self))
155	}
156
157	/// 第二种删除节点的方法
158	pub fn del2(mut self,key:isize)->Option<Box<Self>>{
159		if key < self.data{
160			self.lchild=match self.lchild{
161				Some(c)=>{
162					c.del2(key)
163				},
164				None=>{
165					None
166				}
167			};
168		}else if key > self.data{
169			self.rchild=match self.rchild{
170				Some(c)=>{
171					c.del2(key)
172				},
173				None=>{
174					None
175				}
176			};			
177		}else{
178			let lchild = self.lchild;
179			let rchild = self.rchild;
180			match lchild{
181				Some(lc)=>{
182					match rchild{
183						Some(rc)=>{
184							//2个孩子
185							let (n,d) = del_r_d(*lc);
186							self.lchild = n;
187							self.rchild = Some(rc);
188							self.data = d;
189							return Some(Box::new(self));
190						},
191						None=>{
192							//有左没右
193							return Some(lc);
194						},
195					}
196				},
197				None=>{
198					match rchild{
199						Some(rc)=>{
200							//没左有右
201							return Some(rc);
202						},
203						None=>{
204							//0个孩子
205							return None;
206						},
207					}					
208				},
209			}
210		}
211		Some(Box::new(self))
212	}
213	
214}
215
216/// 删除右下
217fn del_r_d(mut node:Tnode)->(Option<Box<Tnode>>,isize){
218	let n_res;
219	let data;
220	match node.rchild{
221		Some(c)=>{
222			let (n,d) = del_r_d(*c);
223			node.rchild = n;
224			n_res=Some(Box::new(node));
225			data = d;
226		},
227		None=>{
228			data = node.data;
229			n_res = match node.lchild{
230				Some(l)=>Some(l),
231				None=>None,
232			};
233		},
234	}
235	(n_res,data)
236}
237
238pub enum OptionResult{
239	Success,
240	Fail,
241	IsThere,
242}
243
244#[cfg(test)]
245mod tests {
246    #[test]
247    fn it_works() {
248        assert_eq!(2 + 2, 4);
249    }
250}
binary_sort_tree/lib.rs

binary_sort_tree/
lib.rs
