publicclassTest{publicstaticvoid main(String[] args){int[] r =newint[]{5,1,3,4,6,7,2,8,9,0};BST binarySearchTree =new BST(r);binarySearchTree.inOrder();System.out.println();binarySearchTree.searchBST(6);//查找成功System.out.println();binarySearchTree.searchBST(10);//查找失败->插入System.out.println();}}
publicclass BST {//二叉树结点publicclassBiNode{int data;BiNode left;BiNode right;BiNode(int data,BiNode left,BiNode right){this.data = data;this.left = left;this.right = right;}}privateBiNode root = null;BST(int[] r){for(int i =0; i < r.length; i++){BiNode s =newBiNode(r[i],null,null);root = insertBST(root, s);// insertBST1(s);}}//插入（递归）publicBiNode insertBST(BiNode head,BiNode s){if(head == null){head = s;return head;}if(s.data < head.data)head.left = insertBST(head.left, s);elsehead.right = insertBST(head.right,s);return head;}//插入（非递归：循环、用临时变量保存过程）publicvoid insertBST1(BiNode s){if(root == null){root = s;return;}BiNode temp = root;//需要临时结点记录while(true){if(s.data < temp.data){if(temp.left == null){temp.left = s;return;}temp = temp.left;}else{if(temp.right == null){temp.right = s;return;}temp = temp.right;}}}//查找：成功->返回；失败：插入publicBiNode searchBST(int a){BiNode s1 = searchBST(root,a);if(s1 == null){BiNode s2 =newBiNode(a,null,null);insertBST1(s2);System.out.println("search fail ; insert success: "+ s2.data);inOrder();return s2;}else{System.out.println("search success: "+ s1.data);return s1;}}//查找privateBiNode searchBST(BiNode head,int a){if(head == null)return null;if(a < head.data)return searchBST(head.left, a);elseif(a > head.data)return searchBST(head.right, a);elsereturn head;}// 删除// 删除f的孩子ppublicvoid deleteLeftBST(BiNode f,BiNode p){if(p.left == null && p.right == null) //p为叶子{f.left = null;p = null;}elseif(p.right == null) //p只有左子树{f.left = p.left;p = null;}elseif(p.left == null) //p只有右子树{f.left = p.right;p = null;}else //p的左右子树均不空{BiNode par = p, s = par.right; //用par s 去查找p的右子树的最左下结点while(s.left != null){par = s;s = par.left;}p.data = s.data; //交换最左下结点s与p结点数据//剪枝（删除s结点）if(par == p) //处理特殊情况{par.right = s.right;s = null;}else //处理一般情况{par.left = s.right;s = null;}}}//先序遍历publicvoid preOrder(){System.out.print("preOrder traversal with recursion:");preOrder(root);System.out.println();}//递归privatevoid preOrder(BiNode root){if(root == null)return;System.out.print(root.data); //访问结点preOrder(root.left);preOrder(root.right);}//中序遍历publicvoid inOrder(){System.out.print("inOrder traversal with recursion:");inOrder(root);System.out.println();}//递归privatevoid inOrder(BiNode root){if(root == null)//访问结点return;inOrder(root.left);System.out.print(root.data); //访问结点inOrder(root.right);}//后序遍历publicvoid postOrder(){System.out.print("postOrder traversal with recursion:");postOrder(root);System.out.println();}//递归privatevoid postOrder(BiNode root){if(root == null)return;postOrder(root.left);postOrder(root.right);System.out.print(root.data); //访问结点}}
输出：
inOrder traversal with recursion:0123456789search success:6search fail ; insert success:10inOrder traversal with recursion:012345678910