BST二叉搜索树节点定义:
1 /** 2 * BST树的节点类型 3 * @param <T> 4 */ 5 class BSTNode<T extends Comparable<T>>{ 6 private T data; // 数据域 7 private BSTNode<T> left; // 左孩子域 8 private BSTNode<T> right; // 右孩子域 9 10 public BSTNode(T data, BSTNode<T> left, BSTNode<T> right) { 11 this.data = data; 12 this.left = left; 13 this.right = right; 14 } 15 16 public T getData() { 17 return data; 18 } 19 20 public void setData(T data) { 21 this.data = data; 22 } 23 24 public BSTNode<T> getLeft() { 25 return left; 26 } 27 28 public void setLeft(BSTNode<T> left) { 29 this.left = left; 30 } 31 32 public BSTNode<T> getRight() { 33 return right; 34 } 35 36 public void setRight(BSTNode<T> right) { 37 this.right = right; 38 } 39 }
BST的实现:
1 /** 2 * BST树的实现 3 * @param <T> 4 */ 5 class BST<T extends Comparable<T>> { 6 public BSTNode<T> root; // 指向根节点 7 8 /** 9 * BST树的初始化 10 */ 11 public BST() { 12 this.root = null; 13 } 14 }
BST的插入操作:
/** * BST树的非递归插入操作 * * @param data */ public void non_insert(T data) { // 1.判断如果root是null,如果root是null,直接生成根节点,让root指向,结束 if (root == null) { this.root = new BSTNode<>(data, null, null); return; } // 2.如果root不为空,从根节点开始搜索一个合适的位置,放新节点 BSTNode<T> cur = this.root; BSTNode<T> parent = null; // this.root while (cur != null) { if (cur.getData().compareTo(data) > 0) { parent = cur; cur = cur.getLeft(); } else if (cur.getData().compareTo(data) < 0) { parent = cur; cur = cur.getRight(); } else { return; } } // 3.生成新节点,把节点的地址,写入父节点相应的地址域 if (parent.getData().compareTo(data) > 0) { parent.setLeft(new BSTNode<T>(data, null, null)); } else { parent.setRight(new BSTNode<T>(data, null, null)); } }
/** * 递归插入 * * @param data */ public void insert(T data) { this.root= insert(data, root); } private BSTNode<T> insert(T data, BSTNode<T> root) { if (root == null) { return new BSTNode<T>(data, null, null); } if (root.getData().compareTo(data) > 0) { root.setLeft(insert(data,root.getLeft())); } else if (root.getData().compareTo(data) < 0) { root.setRight(insert(data, root.getRight())); }else { ; } return root; }
删除操作:
/** * 非递归实现BST树的删除操作 * * @param data */ public void non_remove(T data) { if (this.root == null) { return; } // 1. 先搜索BST树,找到待删除的节点 BSTNode<T> cur = this.root; BSTNode<T> parent = null; while (cur != null) { if (cur.getData().compareTo(data) > 0) { parent = cur; cur = cur.getLeft(); } else if (cur.getData().compareTo(data) < 0) { parent = cur; cur = cur.getRight(); } else { break; } } if (cur == null) {// 表示BST树中没有值为data的节点 return; } // 2. 判断删除节点是否有两个孩子,如果有,用前驱的值代替,直接删除前驱 if (cur.getLeft() != null && cur.getRight() != null) { BSTNode<T> old = cur; parent = cur; cur = cur.getLeft(); while (cur != null) { parent = cur; cur = cur.getRight(); } old.setData(cur.getData());// 前驱节点的值代替待删节点的值 } // 3. 删除有一个孩子的节点,或者没有孩子的节点(看作有一个孩子,孩子是null) BSTNode<T> child = cur.getLeft(); if (child == null) { child = cur.getRight(); } if (parent == null) {// 删除的就是根节点 this.root = child; } else { if (parent.getLeft() == cur) { parent.setLeft(child); } else { parent.setRight(child); } } }
/** * 递归实现删除值val的节点 * * @param val */ public void remove(T val) { this.root = remove(val, root); } private BSTNode<T> remove(T val, BSTNode<T> root) { if(root==null){ return null; } if(root.getData().compareTo(val)>0){ root.setLeft(remove(val,root.getLeft())); }else if(root.getData().compareTo(val)>0){ root.setRight(remove(val,root.getRight())); }else { if(root.getLeft()!=null&&root.getRight()!=null){ BSTNode<T> old=root; root=root.getLeft(); while (root.getRight()!=null){ root=root.getRight(); } old.setData(root.getData()); old.setLeft(remove(root.getData(),root.getLeft())); }else if(root.getLeft()!=null){ return root.getLeft(); }else if(root.getRight()!=null){ return root.getRight(); }else { return null; } } return root; }
判断有无data值:
/** * 判断有无data值 * * @param data * @return */ public boolean non_query(T data) { BSTNode<T> cur = root; if (root == null) { return false; } while (cur != null) { if (cur.getData().compareTo(data) > 0) { cur = cur.getLeft(); } else if (cur.getData().compareTo(data) < 0) { cur = cur.getRight(); } else { return true; } } return false; }
/** * 递归实现判断有无data * @param data * @return */ public boolean query(T data){ return query(data,root); } private boolean query(T data, BSTNode<T> root) { if(root==null){ return false; } if(root.getData().compareTo(data)>0){ return query(data,root.getLeft()); } if(root.getData().compareTo(data)<0){ return query(data,root.getRight()); } else { return true; } }
前序遍历:
/** * 前序遍历BST树 */ public void preOrder() { System.out.print("前序遍历"); preOrder(this.root); } private void preOrder(BSTNode<T> root) { if (root != null) { System.out.print(root.getData() + " "); preOrder(root.getLeft()); preOrder(root.getRight()); } }
中序遍历:
/** * 中序遍历 */ public void inOrder() { System.out.println(); System.out.print("中序遍历"); inOrder(this.root); System.out.println(); } private void inOrder(BSTNode<T> root) { if (root != null) { inOrder(root.getLeft()); System.out.print(root.getData() + " "); inOrder(root.getRight()); } }
后序遍历:
/** * 后序遍历 */ public void postOrder() { System.out.println("后序遍历"); postOrder(this.root); System.out.println(); } private void postOrder(BSTNode<T> root) { if (root != null) { postOrder(root.getLeft()); postOrder(root.getRight()); System.out.print(root.getData() + " "); } }
层序遍历:
/** * BST的层序遍历 */ public void levelOrder() { System.out.println("递归层序遍历"); for (int i = 0; i < this.level(); i++) { levelOrder(this.root, i); } } /** * 层序遍历的递归实现 * * @param root * @param i */ private void levelOrder(BSTNode<T> root, int i) { if (root != null) { if (i == 0) { System.out.print(root.getData() + " "); return; } levelOrder(root.getLeft(), i - 1); levelOrder(root.getRight(), i - 1); } }
返回BST节点的个数:
/** * 返回BST树的所有节点个数的API * * @return */ public int number() { return number(root); } /** * 以root为根节点计算BST树的节点个数 * * @param root * @return */ private int number(BSTNode<T> root) { if (root == null) { return 0; } else { return number(root.getLeft()) + number(root.getRight()) + 1; } }
返回BST的高度:
/** * 返回BST树的高度的API * * @return */ public int level() { return level(this.root); } private int level(BSTNode<T> root) { if (root == null) { return 0; } else { int left = level(root.getLeft()); int right = level(root.getRight()); return left > right ? left + 1 : right + 1; } }
BST的镜像反转:
/** * 求BST树的镜像翻转API */ public void mirror() { mirror(this.root); } /** * 求BST镜像翻转的递归实现 * * @param root */ private void mirror(BSTNode<T> root) { if (root == null) { return; } BSTNode<T> tmp = root.getLeft(); root.setLeft(root.getRight()); root.setRight(tmp); mirror(root.getLeft()); mirror(root.getRight()); }
返回BST树第K小的元素:
/** * 返回中序遍历倒数第k个节点的值 * * @param k * @return */ public T getOrderValue(int k){ getOrderValue(this.root, k); return cur; } private int i=0; private T getOrderValue(BSTNode<T> root, int k) { if(root == null){ return null; } T val = getOrderValue(root.getLeft(), k); if(val != null){ return val; } if(i++ == k) { return root.getData(); } return getOrderValue(root.getRight(), k); }
根据前序和中序数组,重建搜索二叉树:
/** * 根据参数传入的pre和in数组,重建二叉树 * @param pre * @param in */ public void rebuild(T[]pre,T[]in){ this.root=rebuild(pre,0,pre.length-1,in,0,in.length-1); } private BSTNode<T> rebuild(T[] pre, int i, int j, T[] in, int m, int n) { if(i>j||m>n){ return null; } BSTNode<T> node=new BSTNode<T>(pre[i],null,null); for (int k=m;k<=n;k++){ if(pre[i].compareTo(in[k])==0){ node.setLeft(rebuild(pre,i+1,i+k-m, in,m,k-1)); node.setRight(rebuild(pre,i+(k-m)+1,j, in,k+1,n)); break; } } return node; }