手动实现二叉搜索树

前言

提前祝大家五一快乐~~，基础的数据结构接近尾声了，我模拟实现了一个 二叉搜索树，分享给大家，希望可以帮助到有需要的人。

思维导图(思路)

代码 

package demo1;public class BinarySearchTree {static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public TreeNode root ;//别忘记这个啦public void insert(int key) {if(root==null){root=new TreeNode(key);return;}TreeNode cur=root;TreeNode parent=null;TreeNode node=new TreeNode(key);while(cur!=null){if(cur.val>key){parent=cur;cur=cur.left;}else if(cur.val<key){parent=cur;cur=cur.right;}else{//因为不能插入相同的return;}}//走到这里，parent.val一定不会等于key的if(parent.val>key){parent.left=node;}else {parent.right=node;}}/*** 时间复杂度：*        最好情况： O(logN)*        最坏情况： O(N)* @param key* @return*/public TreeNode search(int key) {TreeNode cur=root;while(cur!=null){if(cur.val<key){cur=cur.right;}else if(cur.val>key){cur=cur.left;}else{return cur;}}return null;}public void remove(int key) {if(root==null){return;}TreeNode parent=null;TreeNode cur=root;while(cur!=null){if(cur.val>key){parent=cur;cur=cur.left;}else if(cur.val<key){parent=cur;cur=cur.right;}else{removeNode(parent,cur);//别搞忘写returnreturn;}}}private void removeNode(TreeNode parent, TreeNode cur) {if(cur.left==null){if(cur==root){root=cur.right;}else if(parent.right==cur){parent.right=cur.right;}else{parent.left=cur.right;}}else if(cur.right==null){if(cur==root){root=cur.left;}else if(parent.right==cur){parent.right=cur.left;}else{parent.left=cur.left;}}else{TreeNode tp=cur;TreeNode t=cur.right;while(t.left!=null){tp=t;t=t.left;}cur.val=t.val;if(tp.left==t){tp.left=t.right;}else{tp.right=t.right;}}}
}

结语 

下次见~~，祝大家五一快乐