二叉排序树的插入删除和查找

pre: 前序遍历
in: 中序遍历
post：后序遍历
insert: 插入，本题中不会出现相同的元素
delete: 删除，删除成功输出TRUE,没有该元素则输出FALSE，删除的方法是如果有左子树，以左子树中最大值作为新的树根，否则，以右子树最小值作为树根。
search： 查找，存在该元素输出YES， 否则输出NO
exit:退出
输入：
输入的第一行为整数 N
接下来一行为N个整数，你需要把这N个整数构建出相应的二叉排序树
之后是一组指令。

输出：
根据相应的指令进行输出。说明：遍历各元素之间用一个空格隔开。

样例输入：
10
31 15 9 5 4 7 8 50 42 2
pre
in
post
delete
15
delete
88
in
search
8
search
222
insert
15
pre
in
post
exit

样例输出：

31 15 9 5 4 2 7 8 50 42
2 4 5 7 8 9 15 31 42 50
2 4 8 7 5 9 15 42 50 31
TRUE
FALSE
2 4 5 7 8 9 31 42 50
YES
NO
31 9 5 4 2 7 8 15 50 42
2 4 5 7 8 9 15 31 42 50
2 4 8 7 5 15 9 42 50 31

注意：在样例中，我先把15删除掉了，然后再插入15，观察最开始的三个遍历，和最后的三次遍历，遍历结果是有区别的。

import java.util.*;public class Xingyuxingxi {static TreeNode root;static boolean pd;//定义全局变量，就无需导入到方法里面public static class TreeNode{TreeNode lc;TreeNode rc;int item;public TreeNode(int item) {this.item=item;}}public static TreeNode insert(TreeNode root,int item) {if(root==null) {//如果要插入的位置为空，则直接加入新结点root=new TreeNode(item);}else if(item > root.item) {//如果插入的数大该结点的数则进该结点的右子树找位置root.rc=insert(root.rc,item);}else if(item< root.item) {//如果插入的数小于该结点的数则进该结点的左子树找位置root.lc=insert(root.lc,item);}return root;}public static TreeNode delete(TreeNode root,int item){if(root==null){return null;}if(root.item==item) {pd=true;if (root.lc == null && root.rc == null) {//如果删除的结点左子树和右子树都为空root = null;//则直接删除该结点} else if (root.lc != null) {//如果删除结点的左子树不为空，应该在左子树中找到最大的结点TreeNode node1 = root.lc;//储存该结点的左子树结点TreeNode node2 = root.lc;//储存该结点的左子树结点while (node1.rc != null) {//最大的值肯定在左子树结点的右子树上，如果没有则该结点就是最大值，因为二叉搜索树要求左子树小于前结点，右子树大于前结点node2 = node1;node1 = node1.rc;}//如果进了循环，则node1和node2不相等if (node1 != node2) {//如果不相等表示，则node2储存的将会是node1的父亲结点，node1储存的是node2的右子树结点node2.rc = node1.lc;//让node2右子树结点连接node1的左子树结点，此时node1已经是最大的，所以没有右子树root.item = node1.item;//删除结点用删除结点左子树的最大值替换} else {//如果两个储存的结点相等，则该结点无右结点，只需要将删除结点替换为该结点并且连接其原本的左子树结点即可root.item = node1.item;root.lc = node1.lc;}} else {//如果删除结点的右子树不为空，应该在右子树中找到最小的结点TreeNode node1 = root.rc;//储存该结点的左子树结点TreeNode node2 = root.rc;//储存该结点的左子树结点while (node1.lc != null) {//最小的值肯定在右子树结点的左子树上，如果没有则该结点就是最小值，因为二叉搜索树要求左子树小于前结点，右子树大于前结点node2 = node1;node1 = node1.lc;}//如果进了循环，则node1和node2不相等if (node2 != node1) {//如果不相等表示，则node2储存的将会是node1的父亲结点，node1储存的是node2的左子树结点node2.lc = node1.rc;//让node2左子树结点连接node1的右子树结点，此时node1已经是最小的，所以没有左子树root.item = node1.item;//删除结点用删除结点左子树的最大值替换} else {//如果两个储存的结点相等，则该结点无左结点，只需要将删除结点替换为该结点并且连接其原本的右子树结点即可root.item = node1.item;root.rc = node1.rc;}}}else if(item<root.item){//如果删除的结点比该结点小，进左子树找root.lc=delete(root.lc,item);}else {//如果大则进右子树找root.rc=delete(root.rc,item);}return root;}public static void search(int item) {TreeNode node = root;while(node!=null) {if(item<node.item){//如果小于该结点则进左边找node=node.lc;} else if (item>node.item){//大于则进右边找node=node.rc;}else {//找到了就退出pd=true;//标记为truebreak;}}}public static void pre(TreeNode root) {//先序遍历递归顺序，中左右if(root==null) {//如果根结点为空则返回return;}System.out.print(root.item+" ");//中pre(root.lc);//左pre(root.rc);//右}public static void in(TreeNode root) {//中序遍历递归顺序，左中右if(root==null) {//如果根结点为空则返回return;}in(root.lc);//左System.out.print(root.item+" ");//中in(root.rc);//右}public static void post(TreeNode root) {//后序遍历递归顺序，左右中if(root==null) {//如果根结点为空则返回return;}post(root.lc);//左post(root.rc);//右System.out.print(root.item+" ");//中}public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();root=null;//初始化for (int i = 0; i < n; i++) {int item=sc.nextInt();root=insert(root,item);//就是插入操作}String str;while(sc.hasNext()) {str=sc.next();if(str.equals("exit")) {//退出break;} else if(str.equals("insert")) {//插入int item=sc.nextInt();root=insert(root,item);} else if(str.equals("delete")) {//删除int item=sc.nextInt();pd=false;root=delete(root,item);if(pd){//如果成功删除"TRUE"System.out.println("TRUE");}else {//否则"FALSE",实际上只有没有要删除的数才为"FALSE"System.out.println("FALSE");}} else if(str.equals("search")) {//查找int item= sc.nextInt();pd=false;search(item);if(pd){//找到则为"YES"System.out.println("YES");} else {//否则为"NO"System.out.println("NO");}} else if(str.equals("pre")) {//先序遍历pre(root);System.out.println();} else if(str.equals("in")) {//中序遍历in(root);System.out.println();} else if(str.equals("post")) {//后序遍历post(root);System.out.println();}}}
}