Java超詳細講解排序二叉樹
排序二叉樹概念
- 二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。是數據結構中的一類。
- 對於二叉排序樹的任何一個非葉子節點， 要求左子節點的值比當前節點的值小，右子節點的值比當前節點的值大。
- 對二叉排序樹進行中序遍歷，結果就是按從小到大排序的。
排序二叉樹類的定義
public class binarySortTree {
class Node{
int value;
Node left;
Node right;
public Node(int value){
this.value = value;
}
public void display(){
System.out.print(this.value + " ");
}
}
Node root;
}
添加節點
排序二叉樹添加節點的十分簡單，無論使用遞歸還是循環，思路都一樣，這裡我用遞歸的方式講解。
- 每次添加一個節點時，判斷value(添加節點的值)與root的值的大小關系： 若
root.value < value， 說明該節點應該添加在root的右子樹上。如果右子樹為空，直接添加：root.right = new Node(value)；如果右子樹不為空，那麼遞歸進右子樹(令root.right為root)。 - 若
root.value >= value， 說明該節點應該添加在root的左子樹上。如果左子樹為空，直接添加：root.left = new Node(value)；如果左子樹不為空，那麼遞歸進右子樹(令root.left為root)。
代碼如下：
//添加節點
//此方法可以類內部方法的調用
private void add(Node root,int value){
//添加節點的值大於根節點的值，該節點添加到根節點的右子樹上
if(value > root.value){
//根節點的右子樹為空，直接添加
if(root.right == null){
root.right = new Node(value);
}
//根節點右子樹不為空，遞歸往右子樹插
else{
add(root.right,value);
}
}
//添加節點的值小於或者等於根節點的值，該節點應該添加到左子樹
else{
//左子樹為空，直接添加
if(root.left == null){
root.left = new Node(value);
}
//左子樹不為空，遞歸往左子樹添加
else{
add(root.left, value);
}
}
}
//此方法在類內部和類外部都可以調用
public void add(int value){
//當前樹為空樹
if(root == null){
root = new Node(value);
return;
}
add(root, value);
}
中序遍歷
因為二叉排序樹中序遍歷的結果就是排序好的，所以這裡隻提供中序遍歷。
代碼如下：
//中序遍歷樹
private void inPrevOrder(Node root){
if(root == null) return;
inPrevOrder(root.left);
root.display();
inPrevOrder(root.right);
}
public void inPrevOrder(){
System.out.print("中序遍歷：");
inPrevOrder(root);
}
查找節點
該方法是查找value在二叉樹中對應的位置，是為刪除節點提供的方法。
/**
* 通過value查找二叉樹中的節點
* @param root 被查找樹的根節點
* @param value 要查找的值
* @return 返回查找到的節點
*/
private Node searchNode(Node root, int value){
//被查找樹為null，要查找節點不存在
if(root == null)
return null;
//找到瞭，返回節點
else if(root.value == value){
return root;
}
//該節點不是要查找節點，繼續查找
else{
//該節點的值大於value，往該節點的左子樹遞歸查找
if(root.value > value){
return searchNode(root.left, value);
}
//該節點的值小於value,往該節點的右子樹遞歸查找
else{
return searchNode(root.right, value);
}
}
}
查找某一節點的父節點
該方法是查找二叉樹中一個節點的父節點，也是為刪除節點提供的方法。
/**
* 查找某節點的父節點，並返回
* @param root 被查找樹的根節點
* @param node 要查找的節點
* @return 返回被查找節點的父節點
*/
private Node searchParentNode(Node root, Node node){
//被查找樹為null或者根節點就是要查找的節點，那麼要查找節點的父節點不存在
if(root == null || root == node){
return null;
}
else if(root.left != null && root.left == node || root.right != null && root.right == node){
return root;
}
else{
if(root.value > node.value){
return searchParentNode(root.left, node);
}
else{
return searchParentNode(root.right, node);
}
}
}
刪除節點
刪除節點是排序二叉樹中最麻煩的方法，因為它有很多種情況。
方法如下：
第一種情況：刪除的節點是葉子節點
(1)需求先去找到要刪除的結點targetNode(2)找到targetNode的父結點parent
(3)確定targetNode是parent的左子結點還是右子結點
3.1如果targetNode是parent的左子結點:parent.left = null;
3.2如果targetNode是parent的右子結點:parent.right = null;
第二種情況:刪除隻有一顆子樹的節點
(1)需求先去找到要刪除的結點targetNode(2)找到targetNode的父結點parent
(3)確定targetNode的子結點是左子結點還是右子結點
(4)確定targetNode是parent的左子結點還是右子結點
(5)如果targetNode有左子結點
5.1如果targetNode是parent的左子結點parent.left = targetNode.left;
5.2如果targetNode是parent的右子結點parent.right = targetNode.left;
(6)如果targetNode有右子結點
6.1如果targetNode是 parent 的左子結點parent.left = targetNode.right;
6.2如果targetNode是parent 的右子結點parent.right = targetNode.right
第三種情況：刪除的節點有左右兩個子樹
(1)需求先去找到要刪除的結點targetNode(2)在右子樹找到最小的節點，用一個temp保存這個節點的值，然後刪除這個最小節點(該最小節點一定是滿足第一種情況的)
(3)targetNode.value = temp
除瞭以上情況，還要考慮要刪除的節點就是根節點的情況(此時它的父節點為null)，下面會在代碼中展示，代碼如下：
public void remove(int vlaue){
//找到要刪除的節點
Node targetNode = searchNode(root,vlaue);
//要刪除節點不存在
if(targetNode == null) return;
//找到要刪除節點的父節點
Node targetNodeParent = searchParentNode(root,targetNode);
//要刪除節點為葉子節點
if(targetNode.left == null && targetNode.right == null){
//要刪除的節點就是根節點
if(targetNodeParent == null){
root = null;
}
else{
//要刪除節點是其父節點的左節點
if(targetNodeParent.left == targetNode){
targetNodeParent.left = null;
}
else{
targetNodeParent.right = null;
}
}
}
//要刪除節點隻有一個左子樹
else if(targetNode.left != null && targetNode.right == null){
//要刪除的節點就是根節點
if(targetNodeParent == null) {
root = root.left;
}
//要刪除節點是其父節點的左節點
else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){
targetNodeParent.left = targetNode.left;
}
//要刪除節點是其父節點的右節點
else{
targetNodeParent.right = targetNode.left;
}
}
//要刪除節點隻有一個右子樹
else if(targetNode.right != null && targetNode.left == null){
//要刪除的節點就是根節點
if(targetNodeParent == null) {
root = root.right;
return;
}
//要刪除節點是其父節點的左節點
else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){
targetNodeParent.left = targetNode.right;
}
//要刪除節點是其父節點的右節點
else{
targetNodeParent.right = targetNode.right;
}
}
//要刪除節點右左右都有節點
else{
//找到右子樹最小的節點
Node minNode = targetNode.right;
while(minNode.left != null){
minNode = minNode.left;
}
int temp = minNode.value;
//找到右子樹上最小節點的父節點
Node minNodeParent = searchParentNode(targetNode.right,minNode);
//右子樹根節點就是最小節點
if(minNodeParent == null){
targetNode.right = minNode.right;
}
else{
//要刪除節點是其父節點的左節點
minNodeParent.left = minNode.right;
}
targetNode.value = temp;
}
}
到此這篇關於Java超詳細講解排序二叉樹的文章就介紹到這瞭,更多相關Java排序二叉樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！