个人中心
gpt4 book ai didi

Java创建二叉搜索树,实现搜索,插入,删除的操作实例

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Java创建二叉搜索树,实现搜索,插入,删除的操作实例由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

Java实现的二叉搜索树，并实现对该树的搜索，插入，删除操作（合并删除，复制删除） 。

首先我们要有一个编码的思路，大致如下:

1、查找：根据二叉搜索树的数据特点，我们可以根据节点的值得比较来实现查找，查找值大于当前节点时向右走，反之向左走！ 。

2、插入：我们应该知道，插入的全部都是叶子节点，所以我们就需要找到要进行插入的叶子节点的位置，插入的思路与查找的思路一致.

3、删除:

1）合并删除：一般来说会遇到以下几种情况，被删节点有左子树没右子树，此时要让当前节点的父节点指向当前节点的左子树；当被删节点有右子树没有左子树，此时要让当前节点的父节点指向该右子树；当被删节点即有左子树又有右子树时，我们可以找到被删节点的左子树的最右端的节点，然后让这个节点的右或者左“指针”指向被删节点的右子树 。

2）复制删除：复制删除相对而言是比较简单的删除操作，也是最为常用的删除操作。大致也有以下三种情况：当前节点无左子树有右子树时，让当前右子树的根节点替换被删节点；当前节点无右子树有左子树时，让当前左子树的根节点替换被删除节点；当前被删节点既有左子树又有右子树时，我们就要找到被删节点的替身，可以在被删节点的左子树中找到其最右端的节点，并让这个节点的值赋给被删节点，然后别忘了让此替身节点的父节点指向替身的“指针”为空，（其实在Java中无关紧要了，有垃圾处理机制自动进行处理）。你也可以在当前被删节点的右子树的最左端的节点作为替身节点来实现这一过程.

接下来就上代码吧.

首先是## 二叉搜索树节点类 ## 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package SearchBinaryTree;
 
public class SearchBinaryTreeNode< T > {
   T data;
   public SearchBinaryTreeNode< T > leftChild;
   public SearchBinaryTreeNode< T > rightChild;
 
   public SearchBinaryTreeNode(){
     this.data=null;
     this.leftChild=this.rightChild=null;
   }
 
   public SearchBinaryTreeNode(T da){
     this.data=da;
     this.leftChild=this.rightChild=null;
   }
 
   public SearchBinaryTreeNode(T da,SearchBinaryTreeNode< T > left,SearchBinaryTreeNode< T >right){
     this.data=da;
     this.leftChild=left;
     this.rightChild=right;
   }
 
   public T getData() {
     return data;
   }
   public void setData(T data) {
     this.data = data;
   }
   public SearchBinaryTreeNode< T > getLeftChild() {
     return leftChild;
   }
   public void setLeftChild(SearchBinaryTreeNode< T > leftChild) {
     this.leftChild = leftChild;
   }
   public SearchBinaryTreeNode< T > getRightChild() {
     return rightChild;
   }
   public void setRightChild(SearchBinaryTreeNode< T > rightChild) {
     this.rightChild = rightChild;
   }
 
   public boolean isLeaf(){
     if(this.leftChild==null&&this.rightChild==null){
       return true;
     }
     return false;
   }
 
 
}

实现二叉搜索树 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
package SearchBinaryTree;
 
 
public class SearchBinaryTree< T > {
   SearchBinaryTreeNode< T > root;
 
   public boolean isEmpty(){
     if(root==null){
       return true;
     }
     return false;
   }
 
   public void Visit(SearchBinaryTreeNode< T > root){
     if(root==null){
       System.out.println("this tree is empty!");
     }
     System.out.println(root.getData());
   }
 
   public SearchBinaryTreeNode< T > getRoot(){
     if(root==null){
       root=new SearchBinaryTreeNode< T >();
     }
     return root;
   }
 
   public SearchBinaryTree(){
     this.root=null;
   }
 
   /*
    * 创造一颗二叉树
    */
   public void CreateTree(SearchBinaryTreeNode< T > node, T data) {
     if (root == null) {
       root = new SearchBinaryTreeNode< T >();
     } else {
       if (Math.random() > 0.5) {          //采用随机方式创建二叉树
         if (node.leftChild == null) {
           node.leftChild = new SearchBinaryTreeNode< T >(data);
         } else {
           CreateTree(node.leftChild, data);
         }
       } else {
         if (node.rightChild == null) {
           node.rightChild = new SearchBinaryTreeNode< T >(data);
         } else {
           CreateTree(node.rightChild, data);
         }
       }
     }
   }
 
   /*
    * 在二查搜索树中进行搜索
    */
   public SearchBinaryTreeNode< T > search(SearchBinaryTreeNode< T > root,T value){
     SearchBinaryTreeNode< T > current=root;
     while((root!=null)&&(current.getData()!=value)){
       //需要注意的是java中泛型无法比较大小，在实际的使用时我们可以使用常见的数据类型来替代这个泛型，这样就不会出错了
       current=(value< current.getData ()?search(current.leftChild,value):search(current.rightChild,value));
     }
     return current;
   }
 
   public SearchBinaryTreeNode<T> insertNode( T value){
     SearchBinaryTreeNode< T > p=root,pre=null;
     while(p!=null){
       pre=p;
       //需要注意的是java中泛型无法比较大小，在实际的使用时我们可以使用常见的数据类型来替代这个泛型，这样就不会出错了
       if(p.getData()< value ){
         p =p.rightChild;
       }else{
         p =p.leftChild;
       }
     }
     if(root==null){
       root = new SearchBinaryTreeNode<T>(value);
     }else if(pre.getData()< value ){
       pre.rightChild = new SearchBinaryTreeNode<T>(value);
     }else{
       pre.leftChild=new SearchBinaryTreeNode< T >(value);
     }
   }
 
   /*
    * 合并删除
    */
   public void deleteByMerging(SearchBinaryTreeNode< T > node){
     SearchBinaryTreeNode< T > temp=node;
     if(node!=null){
       //若被删除节点没有右子树,用其左子树的根节点来代替被删除节点
       if(node.rightChild!=null){
         node=node.leftChild;
       }else if(node.leftChild==null){
         //若被删节点没有左子树，用其有字数的最左端的节点代替被删除的节点
         node=node.rightChild;
       }else{
         //如果被删节点左右子树均存在
         temp=node.leftChild;
         while(temp.rightChild!=null){
           temp=temp.rightChild;   //一直查找到左子树的右节点
         }
 
         //将查找到的节点的右指针赋值为被删除节点的右子树的根
         temp.rightChild=node.rightChild;
         temp=node;
         node=node.leftChild;
       }
       temp=null;
     }
   }
 
   /*
    * 复制删除
    */
   public void deleteByCoping(SearchBinaryTreeNode< T > node){
     SearchBinaryTreeNode< T > pre=null;
     SearchBinaryTreeNode< T > temp=node;
     //如果被删节点没有右子树，用其左子树的根节点来代替被删除节点
     if(node.rightChild==null){
       node=node.leftChild;
     }else if(node.leftChild==null){
       node=node.rightChild;
     }else{
       //如果被删节点的左右子树都存在
       temp=node.leftChild;
       pre=node;
       while(temp.rightChild!=null){
         pre=temp;
         temp=temp.rightChild;   //遍历查找到左子树的最右端的节点
       }
       node.data=temp.data;      //进行赋值操作
       if(pre==node){
         pre.leftChild=node.leftChild;
       }else{
         pre.rightChild=node.rightChild;
       }
     }
     temp=null;
   }
 
}

测试类 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package SearchBinaryTree;
 
public class SearchBinaryTreeTest {
 
   public static void main(String []args){
     SearchBinaryTree< Integer > tree=new SearchBinaryTree< Integer >();
     for(int i=1;i< 10 ;i++){
       tree.CreateTree(new SearchBinaryTreeNode<Integer>(), i);
     }
 
     //搜索
     tree.search(tree.root, 7);
 
     //合并删除
     tree.deleteByMerging(new SearchBinaryTreeNode< Integer >(8));
 
     //复制删除
     tree.deleteByCoping(new SearchBinaryTreeNode< Integer >(6));
   }
 
}

好了，就是这样！ 。

以上这篇Java创建二叉搜索树,实现搜索,插入,删除的操作实例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我.

原文链接：http://blog.csdn.net/Marksinoberg/article/details/49951313 。

最后此篇关于Java创建二叉搜索树,实现搜索,插入,删除的操作实例的文章就讲到这里了,如果你想了解更多关于Java创建二叉搜索树,实现搜索,插入,删除的操作实例的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

26 4 0
文章推荐： C++编写生成不重复的随机数代码
文章推荐： C字符串操作函数实现方法小结
文章推荐： Sprint Boot 集成MongoDB的操作方法
文章推荐： java实现堆的操作方法(建堆,插入,删除)
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com