Java超詳細講解排序二叉樹

Posted on by

排序二叉樹概念

  • 二叉排序樹（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;
}

添加節點

排序二叉樹添加節點的十分簡單，無論使用遞歸還是循環，思路都一樣，這裡我用遞歸的方式講解。

  1. 每次添加一個節點時，判斷value(添加節點的值)與root的值的大小關系： 若root.value < value， 說明該節點應該添加在root的右子樹上。如果右子樹為空，直接添加：root.right = new Node(value)；如果右子樹不為空，那麼遞歸進右子樹(令root.right為root)。
  2. 若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！

推薦閱讀：