二叉樹能夠提升查詢效率得益于其特殊的結構，而删除節點意味着其他節點也将受到影響，删除的節點的位置也決定了該次删除操作的複雜程度。本節将具體介紹二叉樹删除節點功能的實作。
【本節目标】
通過閱讀本節内容，你将通過具體的示例圖了解到二叉樹節點删除過程中遇到的難點問題，并了解删除時需要對其他節點做怎樣的調整，學會其代碼實作。
二叉樹資料删除
二叉樹之中的資料删除操作是非常複雜的，因為在進行資料删除的時候需要考慮的情況是比較多的：
情況1、如果待删除節點沒有子節點，那麼直接删掉即可：
資料的删除情況分析一
情況2、如果待删除節點隻有一個子節點，那麼直接删掉，并用其子節點去頂替它；
這個時候考慮兩種情況分析，隻有一個左子樹。
資料的删除情況分析二左子樹
隻有一個右子樹
資料的删除情況分析二右子樹
情況3、如果待删除節點有兩個子節點，這種情況比較複雜，首先找出它的後繼節點，然後處理“後繼節點”和“被删除節點的父節點”之間的關系，最後處理“後繼節點的子節點”和“被删除節點的子節點”之間的關系。
資料的删除情況分析三
下面通過具體的代碼實作操作功能。
import java.util.Arrays;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception{
BinaryTree<Person> tree=new BinaryTree<Person>();
tree.add(new Person("小強-80",80));
tree.add(new Person("小強-50",50));
tree.add(new Person("小強-60",60));
tree.add(new Person("小強-30",30));
tree.add(new Person("小強-90",90));
tree.add(new Person("小強-10",10));
tree.add(new Person("小強-55",55));
tree.add(new Person("小強-70",70));
tree.add(new Person("小強-85",85));
tree.add(new Person("小強-95",95));
tree.remove(new Person("小強-80",80));
System.out.println(Arrays.toString(tree.toArray()));
}
}
/**
* 實作二叉樹操作
* @param <T> 要進行二叉樹的實作
*/
class BinaryTree<T extends Comparable<T>>{
private class Node{
private Comparable<T> data; //存放Comparable,可以比較大小
private Node parent; //儲存父節點
private Node left; //儲存左子樹
private Node right; //儲存右子樹
public Node(Comparable<T> data){ //構造方法直接負責進行資料的存儲
this.data=data;
}
/**
* 實作節點資料的适當位置的存儲
* @param newNode 建立的新節點
* @throws IllegalArgumentException 儲存的資料已存在
*/
public void addNode(Node newNode) {
if(newNode.data.compareTo((T)this.data) <= 0){ //比目前節點資料小
if(this.left==null){ //沒有左子樹
//目前沒有左子樹
this.left=newNode; //儲存左子樹
newNode.parent=this; //儲存父節點
}else{ //需要向左邊繼續判斷
this.left.addNode(newNode); //繼續向下判斷
}
}else{ //比根節點的資料大
if(this.right==null){ //目前沒有右子樹
this.right=newNode; //儲存左子樹
newNode.parent=this; //儲存父節點
}else{
this.right.addNode(newNode); //繼續向下判斷
}
}
}
/**
* 實作所有資料的擷取處理，按照中序周遊的形式來完成
*/
public void toArrayNode() {
if(this.left!=null){ //有左子樹
this.left.toArrayNode(); //遞歸調用
}
BinaryTree.this.returnData[BinaryTree.this.foot++]=this.data;
if(this.right!=null){
this.right.toArrayNode();
}
}
/**
* 檢查是否包含此節點
* @param data 比較的對象
* @return 找到傳回true，找不到傳回false
*/
public boolean containsNode( Comparable<T> data) {
if (data.compareTo((T)this.data) ==0) {
return true ; //查找到了
} else if (data.compareTo((T)this.data) < 0){ //左邊有資料
if (this.left != null) {
return this.left.containsNode(data);
} else {
return false;
}
} else {
if (this.right != null) {
return this .right.containsNode(data);
} else {
return false;
}
}
}
/**
* 擷取要删除的節點對象
* @param data 比較的對象
* @return 要删除的節點對象，對象一定存在
*/
public Node getRemoveNode(Comparable<T> data) {
if(data.compareTo((T)this.data) ==0){
return this;//查找到了
}
if (data.compareTo((T)this.data) < 0) {
if (this.left != null) {
return this.left.getRemoveNode(data);
}
return null;
}
if (this.right != null) {
return this.right.getRemoveNode(data);
}
return null;
}
}
//-------------------以下為二叉樹的功能實作--------------
private Node root; //儲存根節點
private int count; //儲存資料個數
private Object[] returnData; //傳回的資料
private int foot=0; //腳标控制
/**
* 進行資料的儲存
* @param data 要儲存的資料内容
* @exception NullPointerException 儲存資料為空時抛出的異常
*/
public void add(Comparable<T> data){
if(data==null){
throw new NullPointerException("儲存的資料不允許為空！");
}
//所有的資料本身不具備節點關系的比對，那麼一定要将其包裝在Node類之中
Node newNode=new Node(data); //儲存節點
if(this.root==null){ //現在沒有根節點，則第一個節點作為根節點
this.root=newNode;
}else{ //需要為其儲存到一個合适的節點
this.root.addNode(newNode); //交由node類負責處理
}
this.count++;
}
/**
* 以對象數組的形式傳回全部資料，如果沒有資料傳回null
* @return 全部資料
*/
public Object[] toArray(){
if(this.count==0){
return null;
}
this.returnData=new Object[this.count];//儲存長度為數組長度
this.foot=0; //腳标清零
this.root.toArrayNode(); //直接通過Node類負責
return this.returnData; //傳回全部的資料
}
/**
* 進行資料的删除處理
* @param data 要删除的資料
*/
public void remove(Comparable<T> data){
if(this.root == null) { // 根節點不存在
return; // 結束調用
} else {
if(this.root.data.compareTo((T)data) == 0) { // 要删除的是根節點
Node moveNode = this.root.right; // 移動的節點
while(moveNode.left != null) { //現在還有左邊的節點
moveNode = moveNode.left; //一直向左找
} // 就可以确定删除節點的右節點的最小的子節點
moveNode.parent.left = null;
moveNode.right = this.root.right;
moveNode.left = this.root.left;
this.root = moveNode; // 改變根節點
} else {
Node removeNode = this.root.getRemoveNode(data);// 找到要删除的節點
if(removeNode != null) { //找到要删除的對象資訊
// 情況一：沒有任何的子節點
if(removeNode.left == null && removeNode.right == null) {
removeNode.parent.left = null;
removeNode.parent.right = null;
removeNode.parent = null; //父節點直接斷開引用
} else if(removeNode.left != null && removeNode.right == null) { //左邊不為空
removeNode.parent.left = removeNode.left;
removeNode.left.parent = removeNode.parent;
} else if(removeNode.left == null && removeNode.right != null) { //右邊不為空
removeNode.parent.left = removeNode.right;
removeNode.right.parent = removeNode.parent;
} else { //兩遍都有節點，則将右邊節點中最左邊的節點找到，改變其指向
Node moveNode = removeNode.right; // 移動的節點
while(moveNode.left != null) { //現在還有左邊的節點
moveNode = moveNode.left; //一直向左找
} // 就可以确定删除節點的右節點的最小的子節點
removeNode.parent.left = moveNode;
moveNode.parent.left = null; // 斷開原本的連接配接
moveNode.parent = removeNode.parent;
moveNode.right = removeNode.right; // 改變原始的右節點的指向
moveNode.left = removeNode.left;
}
}
}
this.count--;
}
}
}
class Person implements Comparable<Person>{
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "【Person類對象】姓名：" + this.name + "、年齡：" + this.age +"\n";
}
@Override
public int compareTo(Person person) {
return this.age-person.age;//升序
}
} 運作結果：
[【Person類對象】姓名：小強-10、年齡：10
, 【Person類對象】姓名：小強-30、年齡：30
, 【Person類對象】姓名：小強-50、年齡：50
, 【Person類對象】姓名：小強-55、年齡：55
, 【Person類對象】姓名：小強-60、年齡：60
, 【Person類對象】姓名：小強-70、年齡：70
, 【Person類對象】姓名：小強-85、年齡：85
, 【Person類對象】姓名：小強-90、年齡：90
, 【Person類對象】姓名：小強-95、年齡：95
]
可見，二叉樹資料結構删除操作是非常繁瑣的，是以如果不是必須的情況下，不建議進行删除操作。
想學習更多的Java的課程嗎？從小白到大神，從入門到精通，更多精彩不容錯過！免費為您提供更多的學習資源。
本内容視訊來源于
阿裡雲大學 下一篇：認識紅黑樹，解決二叉樹删除後遺症 | 帶你學《Java語言進階特性》之四十一 更多Java面向對象程式設計文章檢視此處