二叉排序树的插入删除和查找(数据结构实训)(难度系数100)
二叉排序树的插入删除和查找
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;//标记为true
break;
}
}
}
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();
}
}
}
}