資料結構算法---二叉樹

一、二叉樹

　　在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實作二叉查找樹和二叉堆。

　　一棵深度為k，且有2^k-1個結點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的結點數都是最大結點數。而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，并且或者最後一層是滿的，或者是在右邊缺少連續若幹結點，則此二叉樹為完全二叉樹。具有n個結點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個葉子結點，至多有2k-1個結點。

二、二叉樹特點

• 在非空二叉樹中,第i層的結點總數不超過 2^(i-1)個結點;
• 深度為h的二叉樹最多有2^h -1 個結點(h=1),最少有h個結點;
• 對于任意一棵二叉樹,如果其葉結點數為N0,而度數為2的結點總數為N2,則N0=N2+1;
• 具有n個節點的完全二叉樹的深度為[log2n]+1，其中[log2n]+1是向下取整

• 若對含 n 個結點的完全二叉樹從上到下且從左至右進行 1 至 n 的編号，則對完全二叉樹中任意一個編号為 i的結點：

  　　(1) 若 i=1，則該結點是二叉樹的根，無雙親, 否則，編号為 [i/2] 的結點為其雙親結點;

  　　(2) 若 2i>n，則該結點無左孩子， 否則，編号為 2i 的結點為其左孩子結點；

  　　(3) 若 2i+1>n，則該結點無右孩子結點， 否則，編号為2i+1 的結點為其右孩子結點。

  　　

  三、二叉樹的Java實作：

public class BinaryTree {
    private Node root;//根結點
    public BinaryTree() {
        this.root = null;
    }
    //插入
    public void insert(String data) {

        Node dataNode = new Node(data);
        //判斷根節點為kong就傳回
        if (root == null) {
            root = dataNode;
        } else {

            Node currentNode = root;
            while (true) {
                //如果大于根節點則放在根節點的右邊
                if (Integer.valueOf(dataNode.data) > Integer.valueOf(currentNode.data)) {
                    Node rightChild = currentNode.rightChild;
                    //如果右子節點為空則設定為右子節點并且傳回
                    if (rightChild == null) {
                        currentNode.rightChild = dataNode;
                        return;
                    }
                    //如果沒找到則繼續比較右子節點指派為目前節點重複操作
                    currentNode = currentNode.rightChild;
                    //如果小于根節點則放在根節點的右邊
                } else {
                    Node leftChild = currentNode.leftChild;
                    //如果右子節點為空則設定為左子節點
                    if (leftChild == null) {
                        currentNode.leftChild = dataNode;
                        return;
                    }
                    //如果沒找到則繼續比較左子節點指派為目前節點重複操作
                    currentNode = currentNode.leftChild;
                }
            }
        }


    }

    public Node find(String data) {
        if (root == null) {
            return null;
        }
        Node cur = root;

        //隻要目前節點的值和data不相等則繼續循環遞歸找
        while (!cur.data.equals(data)) {
            //大于則把目前的右子節點指派為目前節點
            if (Integer.valueOf(data) > Integer.valueOf(cur.data)) {
                cur = cur.rightChild;
                //否則把目前的左子節點指派為目前節點
            } else {
                cur = cur.leftChild;
            }
            //如果目前節點為空則沒有找到
            if (cur == null) {
                return null;
            }
        }
        return cur;
    }


    public boolean delete(String data) {
        //删除分3種情況，1.删除節點為葉子節點 2.删除的節點隻有一個節點 3.删除的有兩種節點
        //第三種情況需要尋找後繼節點，後繼節點就是比要删除的節點的關鍵值要大的節點集合中的最小值。（右子節點的左後代）

        if (root ==null){
            return false;
        }
        boolean isLeftChild = true;
        //首先需要找到是否存在這個節點不存在就直接傳回false,并且确定他是左子樹還是右子樹
        Node cur = root; //要删除的節點
        Node parent = null;//要删除節點的父節點
        while (!cur.data.equals(data)) {
             parent = cur;
            //大于則把目前的右子節點指派為目前節點
            if (Integer.valueOf(data) > Integer.valueOf(cur.data)) {
                cur = cur.rightChild;
                isLeftChild = false;
                //否則把目前的左子節點指派為目前節點
            } else {
                isLeftChild = true;
                cur = cur.leftChild;
            }
            //如果目前節點為空則沒有找到
            if (cur == null) {
                return false;
            }
        }

        //判斷葉子節點
        if (cur.leftChild==null && cur.rightChild==null){
                if (root.data.equals(cur.data)){
                    root = null;
                }else if (isLeftChild){
                    parent.leftChild = null;
                }else {
                    parent.rightChild = null;
                }

        //隻有一個右節點
        }else if (cur.leftChild==null){
            //如果是根節點直接删除，把目前的右節點指派給root
            if (root.data.equals(cur.data)){
                root = cur.rightChild;
             //如果目前需要删除的節點是左孩子則需要将目前節點的右子節點指派給目前節點父節點的左孩子節點
            }else if(isLeftChild){
                parent.leftChild = cur.rightChild;
            }else {
                //如果目前需要删除的節點是右孩子則需要将目前節點的右子節點指派給目前節點父節點的右孩子節點
                parent.rightChild = cur.rightChild;
            }


            //隻有一個左節點
        }else if (cur.rightChild == null){
            //如果是根節點直接删除，把目前的左節點指派給root
            if (root.data.equals(cur.data)){
                root = cur.leftChild;
                //如果目前需要删除的節點是左孩子則需要将目前節點的左子節點指派給目前節點父節點的左孩子節點
            }else if (isLeftChild){
                parent.leftChild = cur.leftChild;
            }else {
                //如果目前需要删除的節點是右孩子則需要将目前節點的左子節點指派給目前節點父節點的右孩子節點
                parent.rightChild = cur.leftChild;
            }
        }else {

            //删除節點有兩個孩子
            //找到目前節點的後繼節點
            Node successor = getSuccessor(cur);
            if(cur == root){
                root = successor;
            }else if(isLeftChild){
                parent.leftChild = successor;
            }else {
                parent.rightChild = successor;
            }
            successor.leftChild = cur.leftChild;

        }
        return true;

    }

    /**
     * 擷取要删除節點的中序後繼節點
     * @param delNode
     * @return
     */
    public Node getSuccessor(Node delNode) {
        Node successor = delNode;
        Node successorParent = delNode;
        Node curr = delNode.rightChild;
        while(curr != null){
            successorParent = successor;
            successor = curr;
            curr = curr.leftChild;
            //左子節點不為空則一直找下去
        }
        if(successor != delNode.rightChild){
            //後繼節點和删除的節點不相等
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
        }
        return successor;
    }


    //周遊分為前序周遊中序周遊後序周遊都是相對于根節點

    //前序周遊
    public void frontOrder(Node root){


        if (root!=null){
            //前序根節點的值在前面
            System.out.println(root.data+" ");
            frontOrder(root.leftChild);
            frontOrder(root.rightChild);
        }
    }



    //中序周遊
    public void middleOrder(Node root){
        if (root!=null) {
            middleOrder(root.leftChild);
            //中序根節點的值在中間
            System.out.println(root.data + " ");
            middleOrder(root.rightChild);
        }


    }



    //中序周遊
    public void lastOrder(Node root){

        if (root!=null) {
            middleOrder(root.leftChild);
            middleOrder(root.rightChild);
            //後序序根節點的值在後面
            System.out.println(root.data + " ");
        }


    }


    //節點
    static class Node {
        private String data;//結點值
        private Node leftChild; //左子結點
        private Node rightChild;//右子結點
        public Node(String data) {
            this.data = data;
        }
    }


    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.insert("1");
        binaryTree.insert("3");
        binaryTree.insert("5");
        binaryTree.insert("8");
        binaryTree.insert("10");
        binaryTree.insert("19");
        binaryTree.insert("12");
        binaryTree.insert("17");

        binaryTree.frontOrder(binaryTree.root);
        binaryTree.middleOrder(binaryTree.root);
        binaryTree.lastOrder(binaryTree.root);
    }
}