[置顶] Java实现排序二叉树的操作

时间：2021-05-25 17:31:20

在写博客之前，一定要明确一个问题，就是Java方法传值的问题，如果是基本类型和String类型，调用了某个方法，在方法内部对其值进行了更改，但是方法调用完了其值保持不变，这是因为Java在传值的时候对这些类型的变量copy了一个副本。对于对象的引用也是如此，比喻a=new A();方法中更改a指向：a=new B();方法执行完毕a仍然指向A类型对象。

    排序二叉树：

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； （3）左、右子树也分别为二叉排序树； （4）没有键值相等的节点。 插入和创建过程比较简单，我就不说了，这里讨论下删除操作： 在二叉排序树删去一个结点，分三种情况讨论：
  1. 若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点。
  2. 若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉排序树的特性。
  3. 若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令*p的左子树为*f的左/右(依*p是*f的左子树还是右子树而定)子树，*s为*p左子树的最右下的结点，而*p的右子树为*s的右子树；其二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）－即让*f的左子树(如果有的话)成为*p左子树的最左下结点(如果有的话)，再让*f成为*p的左右结点的父结点。
这里对于情况3代码使用做法2：

   下面是Java操作排序二叉树，注意传值问题：

package data_structure;

public class BinarySortTree {

private BST root;
static class BST{
int data;
BST lchild;
BST rchild;

public BST(){}

public BST(int data,BST lchild,BST rchild) {
this.data=data;
this.lchild=lchild;
this.rchild=rchild;
}
}

public void createBST(int []d){
for(int i:d)
insertBST(i);
}

public  void insertBST(int d){
BST p=this.root,parent=this.root;
if(p==null){
this.root=new BST(d,null,null);
    return;
}
while(p!=null){
parent=p;
if(d<p.data){
p=p.lchild;
}
else if(d>p.data){
p=p.rchild;
}
}
if(d<parent.data){
parent.lchild=new BST(d,null,null);
}
else{
parent.rchild=new BST(d,null,null);
}
System.out.println("insert "+d+"  over");
}

public boolean searchBST(int key){
BST p=root;
if(p==null)
return false;
while(p!=null){
if(key==p.data)
return true;
else if(key<p.data)
p=p.lchild;
else if(key>p.data)
p=p.rchild;
}
return false;
}

@SuppressWarnings("unused")
public void deleteBST(int key){
BST p=this.root,parent=null;
if(p!=null){
//开始的时候想着调用方法findKey(key,p,parent)寻找p和parent的值，但是由于传值问题，方法调用完毕P和parent值不变，舍弃调用方法
//parent = findKey(key,p,parent);
//寻找待删除的节点和其父节点
while(p!=null&&p.data!=key){
parent=p;
if(p.data>key){
p=p.lchild;
}
else{
p=p.rchild;
}
}
//p==null 表示没有找到
if(p==null){
System.out.println("不存在待删除节点");
return;
}
//System.out.println("P:"+p.data+"  parent:"+parent.data);
//下面对树做删除操作，分成三种情况
//没有左孩子和右孩子
if(p.lchild==null&&p.rchild==null){
if(parent==null){
root=null;
}
else{
if(parent.data>p.data)
parent.lchild=null;
if(parent.data<p.data)
parent.rchild=null;
}
}
//有左孩子没有右孩子
if(p.lchild!=null&&p.rchild==null){
if(p==root){
root=p.lchild;
}
else if(parent.data>p.data){
parent.lchild=p.lchild;
}
else if(parent.data<p.data){
parent.rchild=p.lchild;
}
}
//没有左孩子只有右孩子
if(p.lchild==null&&p.rchild!=null){
if(p==root){
root=p.rchild;
}
else if(parent.data>p.data){
parent.lchild=p.rchild;
}
else if(parent.data<p.data){
parent.rchild=p.rchild;
}
}
//既有左孩子又有右孩子
if(p.lchild!=null&&p.rchild!=null){
BST pre=p,s=p.rchild;
while(s.lchild!=null){
pre=s;
s=s.lchild;
}
p.data=s.data;
if(pre==p){
p.rchild=s.rchild;
}
else{
pre.lchild=s.rchild;
}
}
}
}

public BST findKey(int key,BST p,BST parent){
while(p!=null&&p.data!=key){
parent=p;
if(p.data>key){
p=p.lchild;
}
else{
p=p.rchild;
}
}
System.out.println("P:"+p.data+"  parent:"+parent.data);
return parent;
}

public void printBST(BST p){
if(p==null)
return ;
printBST(p.lchild);
System.out.print(p.data+"  ");
printBST(p.rchild);
}

public static void main(String []args){
BinarySortTree bTree=new BinarySortTree();
int []d={2,6,8,4,12,45,25,14,28};
bTree.createBST(d);
bTree.printBST(bTree.root);
if(bTree.searchBST(45))
System.out.println("\nfind it!~~~");
bTree.deleteBST(2);
bTree.printBST(bTree.root);
}



}


标签：

相关文章