用java源代码学数据结构<七>: BST
/* * 以int类为例 * 其它的类必须能够比较 * *///二叉搜索树的节点点class BSTNode{int item;BSTNode lc;BSTNode rc;BSTNode p;public BSTNode(int item){this.item = item;}}public class BST{//BST的根transient BSTNode root;//树的大小transient int size = 0; public BST(){root = null;}public BST(int rootData){root = new BSTNode(rootData);size++;}//向二叉树搜索树中插入一个节点private void addNode(BSTNode z){if (root==null) {root = z;return;}BSTNode y = null;BSTNode x = root;while(x!=null){//用y来保存xy = x;//找到z应该放置的位置if(z.item < x.item)x = x.lc;else x = x.rc;}z.p = y;//如果y为null表示root为空if (y==null) {root = z;return;}else {//比较y和z,来设置y的lc和rcif (z.item < y.item) y.lc = z;else y.rc = z;}size++;}//找到BST中第一个元素为item的对象,从x节点开始找private BSTNode findNodeByitem(BSTNode x,int item){while (x!=null && x.item!=item) {if (item < x.item)x = x.lc;else x = x.rc;}return x;}private BSTNode minimum(BSTNode x){if (x==null) {return null;}while (x.lc!=null) {x = x.lc;}return x;}private BSTNode maximum(BSTNode x){if (x==null) {return null;}while (x.rc!=null) {x = x.rc;}return x;}private void transPlant(BSTNode u,BSTNode v){if (u.p==null) {root = v;}else {if (u==u.p.lc) {u.p.lc = v;}else {u.p.rc = v;}}if (v!=null) {v.p = u.p;}}//删除x节点private void removeNode(BSTNode z){if (z==null) {return;}if (z.lc==null) {transPlant(z, z.rc);}else {if (z.rc==null) {transPlant(z, z.lc);}else {BSTNode y = minimum(z.rc);if (y.p!=z) {transPlant(y, y.rc);y.rc = z.rc;y.rc.p = y;}transPlant(z, y);y.lc = z.lc;y.lc.p = y;}}size--;}private BSTNode getNodeByitem(int item){return findNodeByitem(root, item);}public void addItem(int item){BSTNode t = new BSTNode(item);addNode(t);}public void removeItem(int item){BSTNode tBstNode = findNodeByitem(root, item);removeNode(tBstNode);}public int getMax(){return maximum(root).item;}public int getMin(){return minimum(root).item;}private void print(BSTNode x){if (x==null) {return ;}print(x.lc);System.out.print("["+x.item+"]");print(x.rc);}public void printAll(){if (root==null) {return;}print(root);}public static void main(String[] args) {BST bst = new BST();bst.addItem(15);bst.addItem(6);bst.addItem(18);bst.addItem(3);bst.addItem(7);bst.addItem(17);bst.printAll();System.out.println();bst.removeItem(6);bst.printAll();System.out.println();bst.removeItem(10);bst.printAll();System.out.println();System.out.println("Max="+bst.getMax());System.out.println("Min="+bst.getMin());}}