文章目录第10章树结构的实际应用二叉排序树二叉排序树(BST)的介绍二叉排序树(BST)创建和遍历二叉排序树删除结点思路图解二叉排序树删除叶子结点BST删除有一颗子树的结点BST删除有二颗子树的结点平衡二叉树(AVL树)平衡二叉树(AVL树)介绍AVL树左旋转思路图解AVL树高度求解AVL树左旋转代码实现AVL树右旋转图解和实现AVL树双旋转图解和实现本章思维导图
第10章树结构的实际应用本章源码：htts:github.comname365Java-Data-structu二叉排序树
二叉排序树(BST)的介绍先看一个需求：
给你一个数列(7,3,10,12,5,1,9)，要求能够高效的完成对数据的查询和添加。
解决方案分析：使用数组数组未排序，优点：直接在数组尾添加，速度快。缺点：查找速度慢.
数组排序，优点：可以使用二分查找，查找速度快，缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。使用链式存储-链表
不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。
使用二叉排序树
二叉排序树介绍：二叉排序树：BST:(BinarySort(Search)Te),对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点
比如针对前面的数据(7,3,10,12,5,1,9)，对应的二叉排序树为：二叉排序树(BST)创建和遍历一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如:数组为Array(7,3,10,12,5,1,9)，创建成对应的二叉排序树为:
ubcclassBinarySortTeTest{ ubcstaticvoidmain(String[]args){
intarr[]={7,3,10,12,5,1,9};
BinaryTete=newBinaryTe();
循环的添加结点到二叉排序树
for(inti=0;i<arr.length;i++){
te.add(newNode(arr[i]));
}
中序遍历二叉排序树
Syst.out.rintln("中序遍历此树:");
te.infixOrder(); 1,3,5,7,9,10,12
}}创建Node结点
classNode{
intvalue;
Nodeleft;
Noderight;
ubcNode(intvalue){
suer();
this.value=value;
}
@Override
ubcStringtoString(){
turn"Node[value="+value+"]";
} 添加节点的方法
递归的形式添加结点,注意需要满足二叉排序树的要求
ubcvoidadd(Nodenode){
if(node==nl){
turn;
}
判断传入的结点的值,和当前子树的根结点的值的关系
if(node.value<this.value){
if(this.left==nl){ 如果当前结点左子结点为nl
this.left=node;
}else{
递归的向左子树添加
this.left.add(node);
}
}else{ 添加的节点的值大于当前结点的值
if(this.right==nl){
this.right=node;
}else{
递归的向右子树添加
this.right.add(node);
}
}
}
中序遍历
ubcvoidinfixOrder(){
if(this.left!=nl){
this.left.infixOrder();
}
Syst.out.rintln(this);
if(this.right!=nl){
this.right.infixOrder();
}
}
}创建二叉排序树
classBinaryTe{
rivateNoderoot;
添加结点的方法
ubcvoidadd(Nodenode){
if(root==nl){
root=node; 如果root为空则直接让root指向node
}else{
root.add(node);
}
}
遍历方法
ubcvoidinfixOrder(){
if(root!=nl){
root.infixOrder();
}else{
Syst.out.rintln("二叉排序树为空！！！");
}
}
}二叉排序树删除结点思路图解二叉排序树的删除情况比较复杂，有下面三种情况需要考虑
1)删除叶子节点(比如：2,5,9,12)
2)删除只有一颗子树的节点(比如：1)
3)删除有两颗子树的节点.(比如：7,3，10)
二叉排序树删除叶子结点图解二叉排序树删除结点的三种情况第一种情况:删除叶子节点(比如：2,5,9,12)
思路
(1)需求先去找到要删除的结点targetNode
(2)找到targetNode的父结点ant
(3)确定targetNode是ant的左子结点还是右子结点
(4)根据前面的情况来对应删除
左子结点ant.left=nl
右子结点ant.right=nl;
代码实现如下:ubcclassBinarySortTeTest{ ubcstaticvoidmain(String[]args){
intarr[]={7,3,10,12,5,1,9};
BinaryTete=newBinaryTe();
循环的添加结点到二叉排序树
for(inti=0;i<arr.length;i++){
te.add(newNode(arr[i]));
}
中序遍历二叉排序树
Syst.out.rintln("中序遍历此树:");
te.infixOrder(); 1,3,5,7,9,10,12
测试一下删除叶子节点
te.delNode(2);
te.delNode(5);
te.delNode(9);
Syst.out.rintln("删除后的节点:");
te.infixOrder();
}}创建Node结点
classNode{
intvalue;
Nodeleft;
Noderight;
ubcNode(intvalue){
suer();
this.value=value;
}
@Override
ubcStringtoString(){
turn"Node[value="+value+"]";
} 添加节点的方法
递归的形式添加结点,注意需要满足二叉排序树的要求
ubcvoidadd(Nodenode){
if(node==nl){
turn;
}
判断传入的结点的值,和当前子树的根结点的值的关系
if(node.value<this.value){
if(this.left==nl){ 如果当前结点左子结点为nl
this.left=node;
}else{
递归的向左子树添加
this.left.add(node);
}
}else{ 添加的节点的值大于当前结点的值
if(this.right==nl){
this.right=node;
}else{
递归的向右子树添加
this.right.add(node);
}
}
}
中序遍历
ubcvoidinfixOrder(){
if(this.left!=nl){
this.left.infixOrder();
}
Syst.out.rintln(this);
if(this.right!=nl){
this.right.infixOrder();
}
}
查找要删除的节点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午8:43:01
*@aramvalue希望删除的结点的值
*@turn如果找到该值返回,未找到返回nl
*
ubcNodesearch(intvalue){
if(value==this.value){ 说明找到了
turnthis;
}elseif(value<this.value){ 查找的值小于当前结点的值,向左子树查找
if(this.left==nl){ 左子结点为空
turnnl;
}
turnthis.left.search(value);
}else{ 查找的值不小于当前结点的值,向右子树查找
if(this.right==nl){
turnnl;
}
turnthis.right.search(value);
}
}
查找要删除结点的父结点
**
*
*@aramvalue希望删除的结点的值
*@turn返回的是要删除的结点的父结点,如果没有就返回nl
*
ubcNodesearchP(intvalue){
如果当前结点是要删除的结点的父结点,如果没有就返回nl
if((this.left!=nl&am;&am;this.left.value==value)||
(this.right!=nl&am;&am;this.right.value==value)){
turnthis;
}else{
如果查找的值小于当前结点的值,且当前结点的左子结点不为空
if(value<this.value&am;&am;this.left!=nl){
turnthis.left.searchP(value); 向左子树查找
}elseif(value>=this.value&am;&am;this.right!=nl){
turnthis.right.searchP(value); 向右子树递归查找
}else{
turnnl; 未找到父结点
}
}
}
}创建二叉排序树
classBinaryTe{
rivateNoderoot;
添加结点的方法
ubcvoidadd(Nodenode){
if(root==nl){
root=node; 如果root为空则直接让root指向node
}else{
root.add(node);
}
}
遍历方法
ubcvoidinfixOrder(){
if(root!=nl){
root.infixOrder();
}else{
Syst.out.rintln("二叉排序树为空！！！");
}
}
查找要刪除的结点
ubcNodesearch(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.search(value);
}
}
查找要删除的节点的父节点
ubcNodesearchP(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.searchP(value);
}
}
删除节点
ubcvoiddelNode(intvalue){
if(root==nl){
turn;
}else{
1.需求先去找到要删除的结点targetNode
NodetargetNode=search(value);
如果没有找到要删除的结点
if(targetNode==nl){
turn;
}
如果我们发现当前这颗二叉排序树只有一个结点
if(root.left==nl&am;&am;root.right==nl){
root=nl;
turn;
}
去找到targetNode的父结点
Nodeant=searchP(value);
如果要删除的节点为叶子节点
if(targetNode.left==nl&am;&am;targetNode.right==nl){
判断targetNode是父节点的左子结点,还是右子节点
if(ant.left!=nl&am;&am;ant.left.value==value){ 左子节点
ant.left=nl;
}elseif(ant.right!=nl&am;&am;ant.right.value==value){ 右子节点
ant.right=nl;
}
}
}
}
}
BST删除有一颗子树的结点
第二种情况:删除只有一颗子树的节点比如1
思路
(1)需求先去找到要删除的结点targetNode
(2)找到targetNode的父结点ant
(3)确定targetNode的子结点是左子结点还是右子结点
(4)targetNode是ant的左子结点还是右子结点
(5)如果targetNode有左子结点
5.1如果targetNode是ant的左子结点
ant.left=targetNode.left;
5.2如果targetNode是ant的右子结点
ant.right=targetNode.left;
(6)如果targetNode有右子结点
6.1如果targetNode是ant的左子结点
ant.left=targetNode.right;
6.2如果targetNode是ant的右子结点
ant.right=targetNode.right
代码实现如下:ubcclassBinarySortTeTest{ ubcstaticvoidmain(String[]args){
intarr[]={7,3,10,12,5,1,9,0};
BinaryTete=newBinaryTe();
循环的添加结点到二叉排序树
for(inti=0;i<arr.length;i++){
te.add(newNode(arr[i]));
}
中序遍历二叉排序树
Syst.out.rintln("中序遍历此树:");
te.infixOrder(); 0,1,3,5,7,9,10,12
测试一下删除叶子节点
te.delNode(1);
Syst.out.rintln("删除后的节点:");
te.infixOrder(); 0,3,5,7,9,10,12
}}创建Node结点
classNode{
intvalue;
Nodeleft;
Noderight;
ubcNode(intvalue){
suer();
this.value=value;
}
@Override
ubcStringtoString(){
turn"Node[value="+value+"]";
} 添加节点的方法
递归的形式添加结点,注意需要满足二叉排序树的要求
ubcvoidadd(Nodenode){
if(node==nl){
turn;
}
判断传入的结点的值,和当前子树的根结点的值的关系
if(node.value<this.value){
if(this.left==nl){ 如果当前结点左子结点为nl
this.left=node;
}else{
递归的向左子树添加
this.left.add(node);
}
}else{ 添加的节点的值大于当前结点的值
if(this.right==nl){
this.right=node;
}else{
递归的向右子树添加
this.right.add(node);
}
}
}
中序遍历
ubcvoidinfixOrder(){
if(this.left!=nl){
this.left.infixOrder();
}
Syst.out.rintln(this);
if(this.right!=nl){
this.right.infixOrder();
}
}
查找要删除的节点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午8:43:01
*@aramvalue希望删除的结点的值
*@turn如果找到该值返回,未找到返回nl
*
ubcNodesearch(intvalue){
if(value==this.value){ 说明找到了
turnthis;
}elseif(value<this.value){ 查找的值小于当前结点的值,向左子树查找
if(this.left==nl){ 左子结点为空
turnnl;
}
turnthis.left.search(value);
}else{ 查找的值不小于当前结点的值,向右子树查找
if(this.right==nl){
turnnl;
}
turnthis.right.search(value);
}
}
查找要删除结点的父结点
**
*
*@aramvalue希望删除的结点的值
*@turn返回的是要删除的结点的父结点,如果没有就返回nl
*
ubcNodesearchP(intvalue){
如果当前结点是要删除的结点的父结点,如果没有就返回nl
if((this.left!=nl&am;&am;this.left.value==value)||
(this.right!=nl&am;&am;this.right.value==value)){
turnthis;
}else{
如果查找的值小于当前结点的值,且当前结点的左子结点不为空
if(value<this.value&am;&am;this.left!=nl){
turnthis.left.searchP(value); 向左子树查找
}elseif(value>=this.value&am;&am;this.right!=nl){
turnthis.right.searchP(value); 向右子树递归查找
}else{
turnnl; 未找到父结点
}
}
}
}创建二叉排序树
classBinaryTe{
rivateNoderoot;
添加结点的方法
ubcvoidadd(Nodenode){
if(root==nl){
root=node; 如果root为空则直接让root指向node
}else{
root.add(node);
}
}
遍历方法
ubcvoidinfixOrder(){
if(root!=nl){
root.infixOrder();
}else{
Syst.out.rintln("二叉排序树为空！！！");
}
}
查找要刪除的结点
ubcNodesearch(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.search(value);
}
}
查找要删除的节点的父节点
ubcNodesearchP(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.searchP(value);
}
}
删除节点
ubcvoiddelNode(intvalue){
if(root==nl){
turn;
}else{
1.需求先去找到要删除的结点targetNode
NodetargetNode=search(value);
如果没有找到要删除的结点
if(targetNode==nl){
turn;
}
如果我们发现当前这颗二叉排序树只有一个结点
if(root.left==nl&am;&am;root.right==nl){
root=nl;
turn;
}
去找到targetNode的父结点
Nodeant=searchP(value);
如果要删除的节点为叶子节点
if(targetNode.left==nl&am;&am;targetNode.right==nl){
判断targetNode是父节点的左子结点,还是右子节点
if(ant.left!=nl&am;&am;ant.left.value==value){ 左子节点
ant.left=nl;
}elseif(ant.right!=nl&am;&am;ant.right.value==value){ 右子节点
ant.right=nl;
}
}elseif(targetNode.left!=nl&am;&am;targetNode.right!=nl){ 删除有两颗子树的节点
}else{ 删除只有一个字树的节点
如果要删除的结点有左子结点
if(targetNode.left!=nl){
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.left;
}else{ targetNode是ant的右子结点
ant.right=targetNode.left;
}
}else{
root=targetNode.left;
}
}else{ 如果要删除的结点有右子结点
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.right;
}else{ 如果targetNode是ant的右子结点
ant.right=targetNode.right;
}
}else{
root=targetNode.right;
}
}
}
}
}
}
BST删除有二颗子树的结点
情况三:删除有两颗子树的节点.(比如：7,3，10)
思路
(1)需求先去找到要删除的结点targetNode
(2)找到targetNode的父结点ant
(3)从targetNode的右子树找到最小的结点
(4)用一个临时变量，将最小结点的值保存t=11
(5)删除该最小结点
(6)targetNode.value=t
代码实现如下:ubcclassBinarySortTeTest{ ubcstaticvoidmain(String[]args){
intarr[]={7,3,10,12,5,1,9,0};
BinaryTete=newBinaryTe();
循环的添加结点到二叉排序树
for(inti=0;i<arr.length;i++){
te.add(newNode(arr[i]));
}
中序遍历二叉排序树
Syst.out.rintln("中序遍历此树:");
te.infixOrder(); 0,1,3,5,7,9,10,12
测试一下删除叶子节点
te.delNode(7);
Syst.out.rintln("删除后的节点:");
te.infixOrder(); 0,1,3,5,9,10,12
}}创建Node结点
classNode{
intvalue;
Nodeleft;
Noderight;
ubcNode(intvalue){
suer();
this.value=value;
}
@Override
ubcStringtoString(){
turn"Node[value="+value+"]";
} 添加节点的方法
递归的形式添加结点,注意需要满足二叉排序树的要求
ubcvoidadd(Nodenode){
if(node==nl){
turn;
}
判断传入的结点的值,和当前子树的根结点的值的关系
if(node.value<this.value){
if(this.left==nl){ 如果当前结点左子结点为nl
this.left=node;
}else{
递归的向左子树添加
this.left.add(node);
}
}else{ 添加的节点的值大于当前结点的值
if(this.right==nl){
this.right=node;
}else{
递归的向右子树添加
this.right.add(node);
}
}
}
中序遍历
ubcvoidinfixOrder(){
if(this.left!=nl){
this.left.infixOrder();
}
Syst.out.rintln(this);
if(this.right!=nl){
this.right.infixOrder();
}
}
查找要删除的节点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午8:43:01
*@aramvalue希望删除的结点的值
*@turn如果找到该值返回,未找到返回nl
*
ubcNodesearch(intvalue){
if(value==this.value){ 说明找到了
turnthis;
}elseif(value<this.value){ 查找的值小于当前结点的值,向左子树查找
if(this.left==nl){ 左子结点为空
turnnl;
}
turnthis.left.search(value);
}else{ 查找的值不小于当前结点的值,向右子树查找
if(this.right==nl){
turnnl;
}
turnthis.right.search(value);
}
}
查找要删除结点的父结点
**
*
*@aramvalue希望删除的结点的值
*@turn返回的是要删除的结点的父结点,如果没有就返回nl
*
ubcNodesearchP(intvalue){
如果当前结点是要删除的结点的父结点,如果没有就返回nl
if((this.left!=nl&am;&am;this.left.value==value)||
(this.right!=nl&am;&am;this.right.value==value)){
turnthis;
}else{
如果查找的值小于当前结点的值,且当前结点的左子结点不为空
if(value<this.value&am;&am;this.left!=nl){
turnthis.left.searchP(value); 向左子树查找
}elseif(value>=this.value&am;&am;this.right!=nl){
turnthis.right.searchP(value); 向右子树递归查找
}else{
turnnl; 未找到父结点
}
}
}
}创建二叉排序树
classBinaryTe{
rivateNoderoot;
添加结点的方法
ubcvoidadd(Nodenode){
if(root==nl){
root=node; 如果root为空则直接让root指向node
}else{
root.add(node);
}
}
遍历方法
ubcvoidinfixOrder(){
if(root!=nl){
root.infixOrder();
}else{
Syst.out.rintln("二叉排序树为空！！！");
}
}
查找要刪除的结点
ubcNodesearch(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.search(value);
}
}
查找要删除的节点的父节点
ubcNodesearchP(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.searchP(value);
}
}
删除节点
ubcvoiddelNode(intvalue){
if(root==nl){
turn;
}else{
1.需求先去找到要删除的结点targetNode
NodetargetNode=search(value);
如果没有找到要删除的结点
if(targetNode==nl){
turn;
}
如果我们发现当前这颗二叉排序树只有一个结点
if(root.left==nl&am;&am;root.right==nl){
root=nl;
turn;
}
去找到targetNode的父结点
Nodeant=searchP(value);
如果要删除的节点为叶子节点
if(targetNode.left==nl&am;&am;targetNode.right==nl){
判断targetNode是父节点的左子结点,还是右子节点
if(ant.left!=nl&am;&am;ant.left.value==value){ 左子节点
ant.left=nl;
}elseif(ant.right!=nl&am;&am;ant.right.value==value){ 右子节点
ant.right=nl;
}
}elseif(targetNode.left!=nl&am;&am;targetNode.right!=nl){ 删除有两颗子树的节点
intminVa=delRightT(targetNode.right);
targetNode.value=minVa;
}else{ 删除只有一个字树的节点
如果要删除的结点有左子结点
if(targetNode.left!=nl){
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.left;
}else{ targetNode是ant的右子结点
ant.right=targetNode.left;
}
}else{
root=targetNode.left;
}
}else{ 如果要删除的结点有右子结点
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.right;
}else{ 如果targetNode是ant的右子结点
ant.right=targetNode.right;
}
}else{
root=targetNode.right;
}
}
}
}
}
编写方法
1.返回的以node为根结点的二叉排序树的最小结点的值
2.删除node为根结点的二叉排序树的最小结点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午10:44:31
*@aramnode传入的结点(为二叉排序树的根结点)
*@turn返回的以node为根结点的二叉排序树的最小结点的值
*
ubcintdelRightT(Nodenode){
Nodetar=node;
循环的查找左子节点，就会找到最小值
while(tar.left!=nl){
tar=tar.left;
}
这时target就指向了最小结点
删除最小结点
delNode(tar.value);
turntar.value;
}
}从左子树找到最大的结点，然后删除节点思路
看过上面的或者已经有相关数据结构的道友就会了解，实现起来异常简单。
1.最小值就是二叉树最左边的叶子节点；
2.而最大值就是二叉树最左边的叶子节点。ubcclassBinarySortTeTest{ ubcstaticvoidmain(String[]args){
intarr[]={7,3,10,12,5,1,9,2};
BinaryTete=newBinaryTe();
循环的添加结点到二叉排序树
for(inti=0;i<arr.length;i++){
te.add(newNode(arr[i]));
}
中序遍历二叉排序树
Syst.out.rintln("中序遍历此树:");
te.infixOrder(); 1,2,3,5,7,9,10,12
测试一下删除叶子节点
te.delNode(10);
Syst.out.rintln("删除后的节点:");
te.infixOrder(); 1,2,3,5,7,9,10,12
}}创建Node结点
classNode{
intvalue;
Nodeleft;
Noderight;
ubcNode(intvalue){
suer();
this.value=value;
}
@Override
ubcStringtoString(){
turn"Node[value="+value+"]";
} 添加节点的方法
递归的形式添加结点,注意需要满足二叉排序树的要求
ubcvoidadd(Nodenode){
if(node==nl){
turn;
}
判断传入的结点的值,和当前子树的根结点的值的关系
if(node.value<this.value){
if(this.left==nl){ 如果当前结点左子结点为nl
this.left=node;
}else{
递归的向左子树添加
this.left.add(node);
}
}else{ 添加的节点的值大于当前结点的值
if(this.right==nl){
this.right=node;
}else{
递归的向右子树添加
this.right.add(node);
}
}
}
中序遍历
ubcvoidinfixOrder(){
if(this.left!=nl){
this.left.infixOrder();
}
Syst.out.rintln(this);
if(this.right!=nl){
this.right.infixOrder();
}
}
查找要删除的节点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午8:43:01
*@aramvalue希望删除的结点的值
*@turn如果找到该值返回,未找到返回nl
*
ubcNodesearch(intvalue){
if(value==this.value){ 说明找到了
turnthis;
}elseif(value<this.value){ 查找的值小于当前结点的值,向左子树查找
if(this.left==nl){ 左子结点为空
turnnl;
}
turnthis.left.search(value);
}else{ 查找的值不小于当前结点的值,向右子树查找
if(this.right==nl){
turnnl;
}
turnthis.right.search(value);
}
}
查找要删除结点的父结点
**
*
*@aramvalue希望删除的结点的值
*@turn返回的是要删除的结点的父结点,如果没有就返回nl
*
ubcNodesearchP(intvalue){
如果当前结点是要删除的结点的父结点,如果没有就返回nl
if((this.left!=nl&am;&am;this.left.value==value)||
(this.right!=nl&am;&am;this.right.value==value)){
turnthis;
}else{
如果查找的值小于当前结点的值,且当前结点的左子结点不为空
if(value<this.value&am;&am;this.left!=nl){
turnthis.left.searchP(value); 向左子树查找
}elseif(value>=this.value&am;&am;this.right!=nl){
turnthis.right.searchP(value); 向右子树递归查找
}else{
turnnl; 未找到父结点
}
}
}
}创建二叉排序树
classBinaryTe{
rivateNoderoot;
添加结点的方法
ubcvoidadd(Nodenode){
if(root==nl){
root=node; 如果root为空则直接让root指向node
}else{
root.add(node);
}
}
遍历方法
ubcvoidinfixOrder(){
if(root!=nl){
root.infixOrder();
}else{
Syst.out.rintln("二叉排序树为空！！！");
}
}
查找要刪除的结点
ubcNodesearch(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.search(value);
}
}
查找要删除的节点的父节点
ubcNodesearchP(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.searchP(value);
}
}
删除节点
ubcvoiddelNode(intvalue){
if(root==nl){
turn;
}else{
1.需求先去找到要删除的结点targetNode
NodetargetNode=search(value);
如果没有找到要删除的结点
if(targetNode==nl){
turn;
}
如果我们发现当前这颗二叉排序树只有一个结点
if(root.left==nl&am;&am;root.right==nl){
root=nl;
turn;
}
去找到targetNode的父结点
Nodeant=searchP(value);
如果要删除的节点为叶子节点
if(targetNode.left==nl&am;&am;targetNode.right==nl){
判断targetNode是父节点的左子结点,还是右子节点
if(ant.left!=nl&am;&am;ant.left.value==value){ 左子节点
ant.left=nl;
}elseif(ant.right!=nl&am;&am;ant.right.value==value){ 右子节点
ant.right=nl;
}
}elseif(targetNode.left!=nl&am;&am;targetNode.right!=nl){ 删除有两颗子树的节点
intmaxVa=delRightT(targetNode.right);
targetNode.value=maxVa;
}else{ 删除只有一个字树的节点
如果要删除的结点有左子结点
if(targetNode.left!=nl){
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.left;
}else{ targetNode是ant的右子结点
ant.right=targetNode.left;
}
}else{
root=targetNode.left;
}
}else{ 如果要删除的结点有右子结点
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.right;
}else{ 如果targetNode是ant的右子结点
ant.right=targetNode.right;
}
}else{
root=targetNode.right;
}
}
}
}
}
编写方法
1.返回的以node为根结点的二叉排序树的最小结点的值
2.删除node为根结点的二叉排序树的最小结点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午10:44:31
*@aramnode传入的结点(为二叉排序树的根结点)
*@turn返回的以node为根结点的二叉排序树的最小结点的值
*
ubcintdelRightT(Nodenode){
Nodetar=node;
循环的查找左子节点，就会找到最大值
while(tar.right!=nl){
tar=tar.right;
}
这时target就指向了最大结点
删除最大结点
delNode(tar.value);
Syst.out.rintln("子树最大:"+tar.value);
turntar.value;
}
}平衡二叉树(AVL树)
平衡二叉树(AVL树)介绍看一个案例(说明二叉排序树可能的问题)
给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST),并分析问题所在。左边BST存在的问题分析:左子树全部为空，从形式上看，更像一个单链表.
插入速度没有影响
查询速度明显降低(因为需要依次比较),不能发挥BST
的优势，因为每次还需要比较左子树，其查询速度比
单链表还慢
解决方案——》平衡二叉树(AVL)基本介绍
平衡二叉树也叫平衡二叉搜索树（Self-balancingbinarysearchte）又被称为AVL树，可以保证查询效率较高。
具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Ta、伸展树等。
举例说明,看看下面哪些AVL树,为什么?
AVL树左旋转思路图解应用案例-单旋转(左旋转)
1.要求:给你一个数列，创建出对应的平衡二叉树.数列{4,3,6,5,7,8}
2.思路分析(示意图)问题：当插入8时
rightHeight()-leftHeight()>1成立，此时，不再是一颗avl树了.
怎么处理才能保证为AVL树-->进行左旋转.具体步骤图解:1.创建一个新的节点newNode(以4这个值创建),创建一个新的节点，值等于当前根节点的值.把新节点的左子树设置了当前节点的左子树
2.newNode.left=left
把新节点的右子树设置为当前节点的右子树的左子树
3.newNode.right=right.left;
把当前节点的值换为右子节点的值
4.value=right.value;
把当前节点的右子树设置成右子树的右子树
5.right=right.right;
把当前节点的左子树设置为新节点
6.left=newLeft;源自网络的动图:
AVL树高度求解
ubcclassAVLTeTest{ ubcstaticvoidmain(String[]args){
int[]arr={4,3,6,5,7,8};
创建一个AVLTe对象
AVLTeavlTe=newAVLTe();
添加结点
for(inti=0;i<arr.length;i++){
avlTe.add(newNode(arr[i]));
}
中序遍历
Syst.out.rintln("中序遍历:");
avlTe.infixOrder(); 3,4,5,6,7,8
Syst.out.rintln("未经过平衡处理的树:");
Syst.out.rintln("树的高度:"+avlTe.getRoot().height()); 4
Syst.out.rintln("树的左子树高度:"+avlTe.getRoot().leftHeight());1
Syst.out.rintln("树的右子树高度:"+avlTe.getRoot().rightHeight());3
}}
创建Node结点
classNode{
intvalue;
Nodeleft;
Noderight;
ubcNode(intvalue){
suer();
this.value=value;
}
@Override
ubcStringtoString(){
turn"Node[value="+value+"]";
} 添加节点的方法
递归的形式添加结点,注意需要满足二叉排序树的要求
ubcvoidadd(Nodenode){
if(node==nl){
turn;
}
判断传入的结点的值,和当前子树的根结点的值的关系
if(node.value<this.value){
if(this.left==nl){ 如果当前结点左子结点为nl
this.left=node;
}else{
递归的向左子树添加
this.left.add(node);
}
}else{ 添加的节点的值大于当前结点的值
if(this.right==nl){
this.right=node;
}else{
递归的向右子树添加
this.right.add(node);
}
}
}
中序遍历
ubcvoidinfixOrder(){
if(this.left!=nl){
this.left.infixOrder();
}
Syst.out.rintln(this);
if(this.right!=nl){
this.right.infixOrder();
}
}
查找要删除的节点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午8:43:01
*@aramvalue希望删除的结点的值
*@turn如果找到该值返回,未找到返回nl
*
ubcNodesearch(intvalue){
if(value==this.value){ 说明找到了
turnthis;
}elseif(value<this.value){ 查找的值小于当前结点的值,向左子树查找
if(this.left==nl){ 左子结点为空
turnnl;
}
turnthis.left.search(value);
}else{ 查找的值不小于当前结点的值,向右子树查找
if(this.right==nl){
turnnl;
}
turnthis.right.search(value);
}
}
查找要删除结点的父结点
**
*
*@aramvalue希望删除的结点的值
*@turn返回的是要删除的结点的父结点,如果没有就返回nl
*
ubcNodesearchP(intvalue){
如果当前结点是要删除的结点的父结点,如果没有就返回nl
if((this.left!=nl&am;&am;this.left.value==value)||
(this.right!=nl&am;&am;this.right.value==value)){
turnthis;
}else{
如果查找的值小于当前结点的值,且当前结点的左子结点不为空
if(value<this.value&am;&am;this.left!=nl){
turnthis.left.searchP(value); 向左子树查找
}elseif(value>=this.value&am;&am;this.right!=nl){
turnthis.right.searchP(value); 向右子树递归查找
}else{
turnnl; 未找到父结点
}
}
}
返回以该结点为根结点的树的高度
ubcintheight(){
turnMath.max(left==nl?0:left.height(),right==nl?0:right.height())+1;
}
返回左子树的高度
ubcintleftHeight(){
if(left==nl){
turn0;
}
turnleft.height();
}
返回右子树的高度
ubcintrightHeight(){
if(right==nl){
turn0;
}
turnright.height();
}
}创建AVL树
classAVLTe{
rivateNoderoot;
ubcNodegetRoot(){
turnroot;
}
添加结点的方法
ubcvoidadd(Nodenode){
if(root==nl){
root=node; 如果root为空则直接让root指向node
}else{
root.add(node);
}
}
遍历方法
ubcvoidinfixOrder(){
if(root!=nl){
root.infixOrder();
}else{
Syst.out.rintln("二叉排序树为空！！！");
}
}
查找要刪除的结点
ubcNodesearch(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.search(value);
}
}
查找要删除的节点的父节点
ubcNodesearchP(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.searchP(value);
}
}
删除节点
ubcvoiddelNode(intvalue){
if(root==nl){
turn;
}else{
1.需求先去找到要删除的结点targetNode
NodetargetNode=search(value);
如果没有找到要删除的结点
if(targetNode==nl){
turn;
}
如果我们发现当前这颗二叉排序树只有一个结点
if(root.left==nl&am;&am;root.right==nl){
root=nl;
turn;
}
去找到targetNode的父结点
Nodeant=searchP(value);
如果要删除的节点为叶子节点
if(targetNode.left==nl&am;&am;targetNode.right==nl){
判断targetNode是父节点的左子结点,还是右子节点
if(ant.left!=nl&am;&am;ant.left.value==value){ 左子节点
ant.left=nl;
}elseif(ant.right!=nl&am;&am;ant.right.value==value){ 右子节点
ant.right=nl;
}
}elseif(targetNode.left!=nl&am;&am;targetNode.right!=nl){ 删除有两颗子树的节点
intminVa=delRightT(targetNode.right);
targetNode.value=minVa;
}else{ 删除只有一个字树的节点
如果要删除的结点有左子结点
if(targetNode.left!=nl){
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.left;
}else{ targetNode是ant的右子结点
ant.right=targetNode.left;
}
}else{
root=targetNode.left;
}
}else{ 如果要删除的结点有右子结点
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.right;
}else{ 如果targetNode是ant的右子结点
ant.right=targetNode.right;
}
}else{
root=targetNode.right;
}
}
}
}
}
编写方法
1.返回的以node为根结点的二叉排序树的最小结点的值
2.删除node为根结点的二叉排序树的最小结点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午10:44:31
*@aramnode传入的结点(为二叉排序树的根结点)
*@turn返回的以node为根结点的二叉排序树的最小结点的值
*
ubcintdelRightT(Nodenode){
Nodetar=node;
循环的查找左子节点，就会找到最小值
while(tar.left!=nl){
tar=tar.left;
}
这时target就指向了最小结点
删除最小结点
delNode(tar.value);
turntar.value;
}
}AVL树左旋转代码实现
ubcclassAVLTeTest{ ubcstaticvoidmain(String[]args){
int[]arr={4,3,6,5,7,8};
创建一个AVLTe对象
AVLTeavlTe=newAVLTe(); 添加结点
for(inti=0;i<arr.length;i++){
avlTe.add(newNode(arr[i]));
} 中序遍历
Syst.out.rintln("中序遍历:");
avlTe.infixOrder();3,4,5,6,7,8 Syst.out.rintln("经过平衡处理的树:");
Syst.out.rintln("树的高度:"+avlTe.getRoot().height());3
Syst.out.rintln("树的左子树高度:"+avlTe.getRoot().leftHeight());2
Syst.out.rintln("树的右子树高度:"+avlTe.getRoot().rightHeight());2
}}创建Node结点
classNode{
intvalue;
Nodeleft;
Noderight; ubcNode(intvalue){
suer();
this.value=value;
} @Override
ubcStringtoString(){
turn"Node[value="+value+"]";
} 添加节点的方法
递归的形式添加结点,注意需要满足二叉排序树的要求
ubcvoidadd(Nodenode){
if(node==nl){
turn;
} 判断传入的结点的值,和当前子树的根结点的值的关系
if(node.value<this.value){
if(this.left==nl){如果当前结点左子结点为nl
this.left=node;
}else{
递归的向左子树添加
this.left.add(node);
}
}else{添加的节点的值大于当前结点的值
if(this.right==nl){
this.right=node;
}else{
递归的向右子树添加
this.right.add(node);
}
}
当添加完一个结点后，如果:(右子树的高度-左子树的高度)>1,左旋转
if(rightHeight()-leftHeight()>1){
leftRate();左旋转
}
} 中序遍历
ubcvoidinfixOrder(){
if(this.left!=nl){
this.left.infixOrder();
}
Syst.out.rintln(this);
if(this.right!=nl){
this.right.infixOrder();
}
} 查找要删除的节点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午8:43:01
*@aramvalue
*希望删除的结点的值
*@turn如果找到该值返回,未找到返回nl
*
ubcNodesearch(intvalue){
if(value==this.value){说明找到了
turnthis;
}elseif(value<this.value){查找的值小于当前结点的值,向左子树查找
if(this.left==nl){左子结点为空
turnnl;
}
turnthis.left.search(value);
}else{查找的值不小于当前结点的值,向右子树查找
if(this.right==nl){
turnnl;
}
turnthis.right.search(value);
}
} 查找要删除结点的父结点
**
*
*@aramvalue
*希望删除的结点的值
*@turn返回的是要删除的结点的父结点,如果没有就返回nl
*
ubcNodesearchP(intvalue){
如果当前结点是要删除的结点的父结点,如果没有就返回nl
if((this.left!=nl&am;&am;this.left.value==value)||(this.right!=nl&am;&am;this.right.value==value)){
turnthis;
}else{
如果查找的值小于当前结点的值,且当前结点的左子结点不为空
if(value<this.value&am;&am;this.left!=nl){
turnthis.left.searchP(value);向左子树查找
}elseif(value>=this.value&am;&am;this.right!=nl){
turnthis.right.searchP(value);向右子树递归查找
}else{
turnnl;未找到父结点
}
}
} 返回以该结点为根结点的树的高度
ubcintheight(){
turnMath.max(left==nl?0:left.height(),right==nl?0:right.height())+1;
} 返回左子树的高度
ubcintleftHeight(){
if(left==nl){
turn0;
}
turnleft.height();
} 返回右子树的高度
ubcintrightHeight(){
if(right==nl){
turn0;
}
turnright.height();
} 左旋转方法
ubcvoidleftRate(){
创建新的结点，以当前根结点的值
NodenewNode=newNode(value);
把新的结点的左子树设置成当前结点的左子树
newNode.left=left;
把新的结点的右子树设置成带你过去结点的右子树的左子树
newNode.right=right.left;
把当前结点的值替换成右子结点的值
value=right.value;
把当前结点的右子树设置成当前结点右子树的右子树
right=right.right;
把当前结点的左子树(左子结点)设置成新的结点
left=newNode;
}}创建AVL树
classAVLTe{
rivateNoderoot; ubcNodegetRoot(){
turnroot;
} 添加结点的方法
ubcvoidadd(Nodenode){
if(root==nl){
root=node;如果root为空则直接让root指向node
}else{
root.add(node);
}
} 遍历方法
ubcvoidinfixOrder(){
if(root!=nl){
root.infixOrder();
}else{
Syst.out.rintln("二叉排序树为空！！！");
}
} 查找要刪除的结点
ubcNodesearch(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.search(value);
}
} 查找要删除的节点的父节点
ubcNodesearchP(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.searchP(value);
}
} 删除节点
ubcvoiddelNode(intvalue){
if(root==nl){
turn;
}else{
1.需求先去找到要删除的结点targetNode
NodetargetNode=search(value);
如果没有找到要删除的结点
if(targetNode==nl){
turn;
}
如果我们发现当前这颗二叉排序树只有一个结点
if(root.left==nl&am;&am;root.right==nl){
root=nl;
turn;
}
去找到targetNode的父结点
Nodeant=searchP(value);
如果要删除的节点为叶子节点
if(targetNode.left==nl&am;&am;targetNode.right==nl){
判断targetNode是父节点的左子结点,还是右子节点
if(ant.left!=nl&am;&am;ant.left.value==value){左子节点
ant.left=nl;
}elseif(ant.right!=nl&am;&am;ant.right.value==value){右子节点
ant.right=nl;
}
}elseif(targetNode.left!=nl&am;&am;targetNode.right!=nl){删除有两颗子树的节点
intminVa=delRightT(targetNode.right);
targetNode.value=minVa;
}else{删除只有一个字树的节点
如果要删除的结点有左子结点
if(targetNode.left!=nl){
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.left;
}else{targetNode是ant的右子结点
ant.right=targetNode.left;
}
}else{
root=targetNode.left;
}
}else{如果要删除的结点有右子结点
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.right;
}else{如果targetNode是ant的右子结点
ant.right=targetNode.right;
}
}else{
root=targetNode.right;
}
}
}
}
} 编写方法
1.返回的以node为根结点的二叉排序树的最小结点的值
2.删除node为根结点的二叉排序树的最小结点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午10:44:31
*@aramnode
*传入的结点(为二叉排序树的根结点)
*@turn返回的以node为根结点的二叉排序树的最小结点的值
*
ubcintdelRightT(Nodenode){
Nodetar=node;
循环的查找左子节点，就会找到最小值
while(tar.left!=nl){
tar=tar.left;
}
这时target就指向了最小结点
删除最小结点
delNode(tar.value);
turntar.value;
}
}
上面的左旋转，仅仅是左旋转，考虑并不完全，完整的旋转代码，参考下方的双旋转！！！AVL树右旋转图解和实现应用案例-单旋转(右旋转)
1.要求:给你一个数列，创建出对应的平衡二叉树.数列{10,12,8,9,7,6}
2.思路分析(示意图)问题：当插入6时
leftHeight()-rightHeight()>1成立，此时，不再是一颗avl树了.怎么处理-->进行右旋转.[就是降低左子树的高度],这里是将9这个节点，通过右旋转，到右子树
1.创建一个新的节点newNode(以10这个值创建),创建一个新的节点，值等于当前根节点的值把新节点的右子树设置了当前节点的右子树
2.newNode.right=right
把新节点的左子树设置为当前节点的左子树的右子树
3.newNode.left=left.right;
把当前节点的值换为左子节点的值
4.value=left.value;
把当前节点的左子树设置成左子树的左子树
5.left=left.left;
把当前节点的右子树设置为新节点
6.right=newLeft;源自网络的动图:代码实现如下：ubcclassAVLTeTest{ ubcstaticvoidmain(String[]args){
int[]arr={4,3,6,5,7,8};
intarr[]={10,12,8,9,7,6};
创建一个AVLTe对象
AVLTeavlTe=newAVLTe(); 添加结点
for(inti=0;i<arr.length;i++){
avlTe.add(newNode(arr[i]));
} 中序遍历
Syst.out.rintln("中序遍历:");
avlTe.infixOrder();3,4,5,6,7,8 Syst.out.rintln("经过平衡处理的树:");
Syst.out.rintln("树的高度:"+avlTe.getRoot().height());3
Syst.out.rintln("树的左子树高度:"+avlTe.getRoot().leftHeight());2
Syst.out.rintln("树的右子树高度:"+avlTe.getRoot().rightHeight());2
Syst.out.rintln("当前的根节点:"+avlTe.getRoot());
}}创建Node结点
classNode{
intvalue;
Nodeleft;
Noderight; ubcNode(intvalue){
suer();
this.value=value;
} @Override
ubcStringtoString(){
turn"Node[value="+value+"]";
} 添加节点的方法
递归的形式添加结点,注意需要满足二叉排序树的要求
ubcvoidadd(Nodenode){
if(node==nl){
turn;
} 判断传入的结点的值,和当前子树的根结点的值的关系
if(node.value<this.value){
if(this.left==nl){如果当前结点左子结点为nl
this.left=node;
}else{
递归的向左子树添加
this.left.add(node);
}
}else{添加的节点的值大于当前结点的值
if(this.right==nl){
this.right=node;
}else{
递归的向右子树添加
this.right.add(node);
}
}
当添加完一个结点后，如果:(右子树的高度-左子树的高度)>1,左旋转
if(rightHeight()-leftHeight()>1){
leftRate();左旋转
}
当添加完一个结点后，如果(左子树的高度-右子树的高度)>1,右旋转
if(leftHeight()-rightHeight()>1){
rightRotate();右旋转
}
} 中序遍历
ubcvoidinfixOrder(){
if(this.left!=nl){
this.left.infixOrder();
}
Syst.out.rintln(this);
if(this.right!=nl){
this.right.infixOrder();
}
} 查找要删除的节点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午8:43:01
*@aramvalue
*希望删除的结点的值
*@turn如果找到该值返回,未找到返回nl
*
ubcNodesearch(intvalue){
if(value==this.value){说明找到了
turnthis;
}elseif(value<this.value){查找的值小于当前结点的值,向左子树查找
if(this.left==nl){左子结点为空
turnnl;
}
turnthis.left.search(value);
}else{查找的值不小于当前结点的值,向右子树查找
if(this.right==nl){
turnnl;
}
turnthis.right.search(value);
}
} 查找要删除结点的父结点
**
*
*@aramvalue
*希望删除的结点的值
*@turn返回的是要删除的结点的父结点,如果没有就返回nl
*
ubcNodesearchP(intvalue){
如果当前结点是要删除的结点的父结点,如果没有就返回nl
if((this.left!=nl&am;&am;this.left.value==value)||(this.right!=nl&am;&am;this.right.value==value)){
turnthis;
}else{
如果查找的值小于当前结点的值,且当前结点的左子结点不为空
if(value<this.value&am;&am;this.left!=nl){
turnthis.left.searchP(value);向左子树查找
}elseif(value>=this.value&am;&am;this.right!=nl){
turnthis.right.searchP(value);向右子树递归查找
}else{
turnnl;未找到父结点
}
}
} 返回以该结点为根结点的树的高度
ubcintheight(){
turnMath.max(left==nl?0:left.height(),right==nl?0:right.height())+1;
} 返回左子树的高度
ubcintleftHeight(){
if(left==nl){
turn0;
}
turnleft.height();
} 返回右子树的高度
ubcintrightHeight(){
if(right==nl){
turn0;
}
turnright.height();
} 左旋转方法
ubcvoidleftRate(){
创建新的结点，以当前根结点的值
NodenewNode=newNode(value);
把新的结点的左子树设置成当前结点的左子树
newNode.left=left;
把新的结点的右子树设置成带你过去结点的右子树的左子树
newNode.right=right.left;
把当前结点的值替换成右子结点的值
value=right.value;
把当前结点的右子树设置成当前结点右子树的右子树
right=right.right;
把当前结点的左子树(左子结点)设置成新的结点
left=newNode;
} 右旋转
ubcvoidrightRotate(){
NodenewNode=newNode(value);
newNode.right=right;
newNode.left=left.right;
value=left.value;
left=left.left;
right=newNode;
}
}创建AVL树
classAVLTe{
rivateNoderoot; ubcNodegetRoot(){
turnroot;
} 添加结点的方法
ubcvoidadd(Nodenode){
if(root==nl){
root=node;如果root为空则直接让root指向node
}else{
root.add(node);
}
} 遍历方法
ubcvoidinfixOrder(){
if(root!=nl){
root.infixOrder();
}else{
Syst.out.rintln("二叉排序树为空！！！");
}
} 查找要刪除的结点
ubcNodesearch(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.search(value);
}
} 查找要删除的节点的父节点
ubcNodesearchP(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.searchP(value);
}
} 删除节点
ubcvoiddelNode(intvalue){
if(root==nl){
turn;
}else{
1.需求先去找到要删除的结点targetNode
NodetargetNode=search(value);
如果没有找到要删除的结点
if(targetNode==nl){
turn;
}
如果我们发现当前这颗二叉排序树只有一个结点
if(root.left==nl&am;&am;root.right==nl){
root=nl;
turn;
}
去找到targetNode的父结点
Nodeant=searchP(value);
如果要删除的节点为叶子节点
if(targetNode.left==nl&am;&am;targetNode.right==nl){
判断targetNode是父节点的左子结点,还是右子节点
if(ant.left!=nl&am;&am;ant.left.value==value){左子节点
ant.left=nl;
}elseif(ant.right!=nl&am;&am;ant.right.value==value){右子节点
ant.right=nl;
}
}elseif(targetNode.left!=nl&am;&am;targetNode.right!=nl){删除有两颗子树的节点
intminVa=delRightT(targetNode.right);
targetNode.value=minVa;
}else{删除只有一个字树的节点
如果要删除的结点有左子结点
if(targetNode.left!=nl){
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.left;
}else{targetNode是ant的右子结点
ant.right=targetNode.left;
}
}else{
root=targetNode.left;
}
}else{如果要删除的结点有右子结点
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.right;
}else{如果targetNode是ant的右子结点
ant.right=targetNode.right;
}
}else{
root=targetNode.right;
}
}
}
}
} 编写方法
1.返回的以node为根结点的二叉排序树的最小结点的值
2.删除node为根结点的二叉排序树的最小结点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午10:44:31
*@aramnode
*传入的结点(为二叉排序树的根结点)
*@turn返回的以node为根结点的二叉排序树的最小结点的值
*
ubcintdelRightT(Nodenode){
Nodetar=node;
循环的查找左子节点，就会找到最小值
while(tar.left!=nl){
tar=tar.left;
}
这时target就指向了最小结点
删除最小结点
delNode(tar.value);
turntar.value;
}
}
上面的右旋转，仅仅是右旋转，考虑并不完全，完整的旋转代码，参考下方的双旋转！！！AVL树双旋转图解和实现应用案例-双旋转
前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列
int[]arr={10,11,7,6,8,9};运行原来的代码可以看到，并没有转成AVL树.
int[]arr={2,1,6,5,7,3};运行原来的代码可以看到，并没有转成AVL树
问题分析:
在满足右旋转条件时，要判断:
(1)如果是左子树的右子树高度大于左子树的左子树时：
(2)就是对当前根节点的左子树，先进行左旋转，
(3)然后，再对当前根节点进行右旋转即可否则，直接对当前节点（根节点）进行右旋转.即可.先对当前节点的左子树，进行左旋转
再对当前节点，进行右旋转
具体代码分析:ubcclassAVLTeTest{ ubcstaticvoidmain(String[]args){
int[]arr={4,3,6,5,7,8};
intarr[]={10,12,8,9,7,6};
创建一个AVLTe对象
AVLTeavlTe=newAVLTe(); 添加结点
for(inti=0;i<arr.length;i++){
avlTe.add(newNode(arr[i]));
} 中序遍历
Syst.out.rintln("中序遍历:");
avlTe.infixOrder();3,4,5,6,7,8 Syst.out.rintln("经过平衡处理的树:");
Syst.out.rintln("树的高度:"+avlTe.getRoot().height());3
Syst.out.rintln("树的左子树高度:"+avlTe.getRoot().leftHeight());2
Syst.out.rintln("树的右子树高度:"+avlTe.getRoot().rightHeight());2
Syst.out.rintln("当前的根节点:"+avlTe.getRoot());
}}创建Node结点
classNode{
intvalue;
Nodeleft;
Noderight; ubcNode(intvalue){
suer();
this.value=value;
} @Override
ubcStringtoString(){
turn"Node[value="+value+"]";
} 添加节点的方法
递归的形式添加结点,注意需要满足二叉排序树的要求
ubcvoidadd(Nodenode){
if(node==nl){
turn;
} 判断传入的结点的值,和当前子树的根结点的值的关系
if(node.value<this.value){
if(this.left==nl){如果当前结点左子结点为nl
this.left=node;
}else{
递归的向左子树添加
this.left.add(node);
}
}else{添加的节点的值大于当前结点的值
if(this.right==nl){
this.right=node;
}else{
递归的向右子树添加
this.right.add(node);
}
}
当添加完一个结点后，如果:(右子树的高度-左子树的高度)>1,左旋转
if(rightHeight()-leftHeight()>1){
如果它的右子树的左子树的高度大于它的右子树的右子树的高度
if(right!=nl&am;&am;right.leftHeight()>right.rightHeight()){
先对右子结点进行右旋转
right.rightRotate();
然后在对当前结点进行左旋转
leftRate();左旋转
}else{
直接进行左旋转即可
leftRate();
}
turn;重要!!!
}
当添加完一个结点后，如果(左子树的高度-右子树的高度)>1,右旋转
if(leftHeight()-rightHeight()>1){
如果它的左子树的右子树高度大于它的左子树的高度
if(left!=nl&am;&am;left.rightHeight()>left.leftHeight()){
先对当前结点的左结点(左子树)->左旋转
left.leftRate();
再对当前结点进行右旋转
rightRotate();
}else{
直接进行右旋转即可
rightRotate();
}
}
} 中序遍历
ubcvoidinfixOrder(){
if(this.left!=nl){
this.left.infixOrder();
}
Syst.out.rintln(this);
if(this.right!=nl){
this.right.infixOrder();
}
} 查找要删除的节点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午8:43:01
*@aramvalue
*希望删除的结点的值
*@turn如果找到该值返回,未找到返回nl
*
ubcNodesearch(intvalue){
if(value==this.value){说明找到了
turnthis;
}elseif(value<this.value){查找的值小于当前结点的值,向左子树查找
if(this.left==nl){左子结点为空
turnnl;
}
turnthis.left.search(value);
}else{查找的值不小于当前结点的值,向右子树查找
if(this.right==nl){
turnnl;
}
turnthis.right.search(value);
}
} 查找要删除结点的父结点
**
*
*@aramvalue
*希望删除的结点的值
*@turn返回的是要删除的结点的父结点,如果没有就返回nl
*
ubcNodesearchP(intvalue){
如果当前结点是要删除的结点的父结点,如果没有就返回nl
if((this.left!=nl&am;&am;this.left.value==value)||(this.right!=nl&am;&am;this.right.value==value)){
turnthis;
}else{
如果查找的值小于当前结点的值,且当前结点的左子结点不为空
if(value<this.value&am;&am;this.left!=nl){
turnthis.left.searchP(value);向左子树查找
}elseif(value>=this.value&am;&am;this.right!=nl){
turnthis.right.searchP(value);向右子树递归查找
}else{
turnnl;未找到父结点
}
}
} 返回以该结点为根结点的树的高度
ubcintheight(){
turnMath.max(left==nl?0:left.height(),right==nl?0:right.height())+1;
} 返回左子树的高度
ubcintleftHeight(){
if(left==nl){
turn0;
}
turnleft.height();
} 返回右子树的高度
ubcintrightHeight(){
if(right==nl){
turn0;
}
turnright.height();
} 左旋转方法
ubcvoidleftRate(){
创建新的结点，以当前根结点的值
NodenewNode=newNode(value);
把新的结点的左子树设置成当前结点的左子树
newNode.left=left;
把新的结点的右子树设置成带你过去结点的右子树的左子树
newNode.right=right.left;
把当前结点的值替换成右子结点的值
value=right.value;
把当前结点的右子树设置成当前结点右子树的右子树
right=right.right;
把当前结点的左子树(左子结点)设置成新的结点
left=newNode;
} 右旋转
ubcvoidrightRotate(){
NodenewNode=newNode(value);
newNode.right=right;
newNode.left=left.right;
value=left.value;
left=left.left;
right=newNode;
}
}创建AVL树
classAVLTe{
rivateNoderoot; ubcNodegetRoot(){
turnroot;
} 添加结点的方法
ubcvoidadd(Nodenode){
if(root==nl){
root=node;如果root为空则直接让root指向node
}else{
root.add(node);
}
} 遍历方法
ubcvoidinfixOrder(){
if(root!=nl){
root.infixOrder();
}else{
Syst.out.rintln("二叉排序树为空！！！");
}
} 查找要刪除的结点
ubcNodesearch(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.search(value);
}
} 查找要删除的节点的父节点
ubcNodesearchP(intvalue){
if(root==nl){
turnnl;
}else{
turnroot.searchP(value);
}
} 删除节点
ubcvoiddelNode(intvalue){
if(root==nl){
turn;
}else{
1.需求先去找到要删除的结点targetNode
NodetargetNode=search(value);
如果没有找到要删除的结点
if(targetNode==nl){
turn;
}
如果我们发现当前这颗二叉排序树只有一个结点
if(root.left==nl&am;&am;root.right==nl){
root=nl;
turn;
}
去找到targetNode的父结点
Nodeant=searchP(value);
如果要删除的节点为叶子节点
if(targetNode.left==nl&am;&am;targetNode.right==nl){
判断targetNode是父节点的左子结点,还是右子节点
if(ant.left!=nl&am;&am;ant.left.value==value){左子节点
ant.left=nl;
}elseif(ant.right!=nl&am;&am;ant.right.value==value){右子节点
ant.right=nl;
}
}elseif(targetNode.left!=nl&am;&am;targetNode.right!=nl){删除有两颗子树的节点
intminVa=delRightT(targetNode.right);
targetNode.value=minVa;
}else{删除只有一个字树的节点
如果要删除的结点有左子结点
if(targetNode.left!=nl){
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.left;
}else{targetNode是ant的右子结点
ant.right=targetNode.left;
}
}else{
root=targetNode.left;
}
}else{如果要删除的结点有右子结点
if(ant!=nl){
如果targetNode是ant的左子结点
if(ant.left.value==value){
ant.left=targetNode.right;
}else{如果targetNode是ant的右子结点
ant.right=targetNode.right;
}
}else{
root=targetNode.right;
}
}
}
}
} 编写方法
1.返回的以node为根结点的二叉排序树的最小结点的值
2.删除node为根结点的二叉排序树的最小结点
**
*
*@Descrition
*@authorsubei
*@date2020年6月13日上午10:44:31
*@aramnode
*传入的结点(为二叉排序树的根结点)
*@turn返回的以node为根结点的二叉排序树的最小结点的值
*
ubcintdelRightT(Nodenode){
Nodetar=node;
循环的查找左子节点，就会找到最小值
while(tar.left!=nl){
tar=tar.left;
}
这时target就指向了最小结点
删除最小结点
delNode(tar.value);
turntar.value;
}
}
下一篇 String还有这么多窍门