Java實現二叉查找樹的增刪查詳解
定義
二叉查找樹（ADT）是一個具有對於樹種的某個節點X,它的左節點都比X小，它的右節點都比X大的二叉樹。如下就是一個符合
要求的二叉查找樹：
增加節點
1.定義節點類:
class Node{
int val;
Node left;
Node right;
public Node(int val){
this.val=val;
}
}
2.插入元素
我們采用遞歸的方法：
1.判斷與根節點是否相同，相同無需操作
2.比根元素小往左邊查找，左節點不存在的話則作為左節點插入即可
3.比根元素大往右邊查找，右節點不存在的話則作為右節點插入即可
代碼實現如下：
Node root;
/**
* 添加元素
* @param val
*/
public void add(int val){
if(root==null){
root=new Node(val);
return;
}
addNode(val,root);
}
private void addNode(int val,Node root){
if(root==null || root.val==val){
return;
}
if(root.val>val){
if(root.left==null){
root.left=new Node(val);
}else {
addNode(val,root.left);
}
}else {
if(root.right==null){
root.right=new Node(val);
}else {
addNode(val,root.right);
}
}
}
查詢節點
我們采用遞歸的方法：
1.判斷與根節點是否相同，相同則返回true
2.比根元素小往左邊查找，左節點為null則返回false表示不存在
3.比根元素大往右邊查找，右節點為null則返回false表示不存在
代碼實現如下:
/**
* 判斷指定值是否存在
* @param val 指定值
* @return true--存在 false--不存在
*/
public boolean findVale(int val){
return isExit(root,val);
}
private boolean isExit(Node node,int val){
if(node==null){
return false;
}
if(node.val==val){
return true;
}else if(node.val>val){
return isExit(node.left,val);
}else {
return isExit(node.right,val);
}
}
刪除節點
刪除元素時要判斷元素的情況：
1.刪除的元素沒有葉子節點，直接刪除，如刪除值為1的節點，雖然平衡性不是太好，但是還是符合二叉查找樹的特性
2.刪除的元素隻有一個節點，刪除元素並將指針指向其子節點 ，如刪除值為4的節點:
3.刪除的元素有左右兩個節點，從右節點中找出大於該節點的最小節點，作為新的節點A,如刪除節點值為2的節點:
代碼實現如下:
/**
* 刪除元素
* 1.刪除的元素沒有葉子節點，直接刪除
* 2.刪除的元素隻有一個節點，刪除元素並將指針指向其子節點
* 3.刪除的元素有兩個節點，從右節點中找出大於該元素的最小值，作為新的節點
* @param val
*/
public void deleteElement(int val){
deleteElement(null,root,val,true);
}
/**
* 刪除元素
* @param prev 父節點
* @param root 當前節點
* @param val 刪除值
* @param isright 是否是右節點
*/
private void deleteElement(Node prev,Node root,int val,boolean isright){
if(root.val==val){
//刪除的元素沒有葉子節點，直接刪除
if(root.left==null && root.right==null){
changeValue(prev,null,isright);
}else if(root.left!=null && root.right!=null){
//3.刪除的元素有兩個節點，從右節點中找出大於該元素的最小值，作為新的節點
changeValue(prev,new Node(findMinGt(root,root.right,true)),isright);
if(prev==null){
//對於頭結點的刪除特殊處理
prev=this.root;
prev.left=root.left;
prev.right=root.right;
return;
}
if(isright){
prev.right.right=root.right;
prev.right.left=root.left;
}else {
prev.left.right=root.right;
prev.left.left=root.left;
}
}//刪除的元素隻有一個節點，刪除元素並將指針指向其子節點
else if(root.left!=null){
changeValue(prev,root.left,isright);
}else {
changeValue(prev,root.right,isright);
}
return;
}
if(root.val>val){
deleteElement(root,root.left,val,false);
}else{
deleteElement(root,root.right,val,true);
}
}
//改變元素值
private void changeValue(Node prev,Node value,boolean isright){
if(prev==null){
root=value;
return;
}
if(isright){
prev.right=value;
}else {
prev.left=value;
}
}
//尋找大於根節點的最小值
private int findMinGt(Node prev,Node root,boolean isRight){
if(root.left==null && root.right==null){
changeValue(prev,null,isRight);
return root.val;
}
if(root.left==null){
changeValue(prev,null,isRight);
return root.val;
}
return findMinGt(root,root.left,false);
}
到此這篇關於Java實現二叉查找樹的增刪查詳解的文章就介紹到這瞭,更多相關Java二叉查找樹增刪查內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！