java 數據結構與演算法---二叉樹

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

原理來自百度百科推薦數據演示網址：https://www.cs.usfca.edu/~galles/visualization/BST.html

一、什麼是二叉樹

　　二叉樹的每個結點至多只有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的(i-1)次方個結點；深度為k的二叉樹至多有2的k次方然後減1個結點(次方不會敲所以用文字描述)；對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。

二、二叉樹的分類：

1、滿二叉樹：除葉子結點外的所有結點均有兩個子結點。

滿二叉樹的性質：
1) 一顆樹深度為h，最大層數為k，深度與最大層數相同，k=h;
2) 樹的第k層，則該層的葉子節點個數為2k;
3) 第k層的結點個數是2的(k-1)次方。
4) 總結點個數是2的k次方減1，且總節點個數一定是奇數。

2、完全二叉樹：若設二叉樹的深度為h，除第 h 層外，其它各層 (1～(h-1)層) 的結點數都達到最大個數，第h層所有的結點都連續集中在最左邊，這就是完全二叉樹。

完全二叉樹的特點是：
1）只允許最後一層有空缺結點且空缺在右邊，即葉子結點只能在層次最大的兩層上出現；
2）對任一結點，如果其右子樹的深度為j，則其左子樹的深度必為j或j+1。即度為1的點只有1個或0個。

滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。

三、二叉樹在數據結構中的實現

二叉樹在一般數據結構中是按照二叉排序樹進行實現、使用的。二叉排序樹（Binary Sort Tree）：又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。

二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於或等於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於或等於它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；

1、二叉排序樹節點的數據結構

private static class Node<E>{
        private E e;//當前節點的數據
        private Node<E> leftNode;//當前節點左子節點
        private Node<E> rightNode;//當前節點右子節點
        public Node(E e, Node<E> leftNode, Node<E> rightNode) {
            super();
            this.e = e;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
        }    
    }

2、插入節點

如果是空樹（不存在節點），則直接插入。
如果不是空樹，則從根節點開始查找相應的節點，即查找新節點的父節點，當父節點找到後，根據新節點的值來確定新節點是在左節點上，還是右節點上。

    public void insert(E e) {
        Node<E> node=new Node<E>(e,null,null);
        if(root==null) {
            root=node;
        }else {
            Node<E> fNode=root;
            Node<E> parentNode=root;//要找的父節點
            while(true) {
                parentNode=fNode;
                if(compareToE(e,fNode.e)) {
                    fNode=fNode.leftNode;
                    if(fNode==null) {
                        parentNode.leftNode=node;
                        break;
                    }
                }else {
                    fNode=fNode.rightNode;
                    if(fNode==null) {
                        parentNode.rightNode=node;
                        break;
                    }
                }
                
            }
        }
        size++;
    }
    //只是實現了數值比較
    private boolean compareToE(E a,E b) {
        Integer a1=(Integer) a;
        Integer b1=(Integer) b;
        return a1<b1;
    }

3、查找節點

從根節點開始查找，如果要查找的節點值比父節點值小，則查左子節點，否則查右子節點，直到查到為止，如果不存在就返回null

    public Node<E> find(E e){
        if(root.e==e) {
            return root;
        }
        Node<E> fNode=root;
        while(true) {
            if(compareToE(e,fNode.e)) {
                fNode=fNode.leftNode;
            }else {
                if(fNode.e.equals(e)) {
                    return fNode;
                }
                fNode=fNode.rightNode;
            }
            if(fNode==null) {
                return null;
            }
        }
    }

4、二叉樹的遍歷方式

A、先序遍歷遍歷規則訪問節點，訪問該節點的左子樹，訪問該節點的右子樹 23 ->20 ->24 （每一個節點都是該規則）

public void preTraversalTree(Node<E> node) {
        if(node!=null) {
            node.display();
            preTraversalTree(node.leftNode);
            preTraversalTree(node.rightNode);
        }
    }

結果： E:23 E:20 E:19 E:21 E:22 E:24 E:23 E:25 E:30

B、中序遍歷：遍歷規則先遍歷左子樹，然後該節點，最後遍歷該節點右子樹 20 ->23 ->24 （每一個節點都是該規則）

public void cenTraversalTree(Node<E> node) {
        if(node!=null) {
            cenTraversalTree(node.leftNode);
            node.display();
            cenTraversalTree(node.rightNode);
        }
    }

結果： E:19 E:20 E:21 E:22 E:23 E:23 E:24 E:25 E:30

C、後續遍歷遍歷規則先遍歷左子樹，然會遍歷該節點右子樹，最後該節點， 20 ->24 ->23 （每一個節點都是該規則）

public void aftTraversalTree(Node<E> node) {
        if(node!=null) {
            aftTraversalTree(node.leftNode);
            aftTraversalTree(node.rightNode);
            node.display();
            
        }
    }

結果： E:19 E:22 E:21 E:20 E:23 E:30 E:25 E:24 E:23

完整代碼

package com.jalja.org.algorithm;


public class MyTree<E> {
    private Node<E> root;//根節點
    private int size=0;//樹中節點的個數
    public MyTree() {
        
    }
    private static class Node<E>{
        private E e;//當前節點的數據
        private Node<E> leftNode;//當前節點左子節點
        private Node<E> rightNode;//當前節點右子節點
        public Node(E e, Node<E> leftNode, Node<E> rightNode) {
            super();
            this.e = e;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
        }
        public void display() {
            System.out.print(" E:"+e);
        }        
    }
    //如果是空樹（不存在節點），則直接插入。
    //如果不是空樹，則從根節點開始查找相應的節點，即查找新節點的父節點，當父節點找到後，根據新節點的值來確定新節點是在左節點上，還是右節點上。
    public void insert(E e) {
        Node<E> node=new Node<E>(e,null,null);
        if(root==null) {
            root=node;
        }else {
            Node<E> fNode=root;
            Node<E> parentNode=root;//要找的父節點
            while(true) {
                parentNode=fNode;
                if(compareToE(e,fNode.e)) {
                    fNode=fNode.leftNode;
                    if(fNode==null) {
                        parentNode.leftNode=node;
                        break;
                    }
                }else {
                    fNode=fNode.rightNode;
                    if(fNode==null) {
                        parentNode.rightNode=node;
                        break;
                    }
                }
                
            }
        }
        size++;
    }
    //只是實現了數值比較
    private boolean compareToE(E a,E b) {
        Integer a1=(Integer) a;
        Integer b1=(Integer) b;
        return a1<b1;
    }
    //從根節點開始查找，如果要查找的節點值比父節點值小，則查左子節點，否則查右子節點，直到查到為止，如果不存在就返回null
    public Node<E> find(E e){
        if(root.e==e) {
            return root;
        }
        Node<E> fNode=root;
        while(true) {
            if(compareToE(e,fNode.e)) {
                fNode=fNode.leftNode;
            }else {
                if(fNode.e.equals(e)) {
                    return fNode;
                }
                fNode=fNode.rightNode;
            }
            if(fNode==null) {
                return null;
            }
        }
    }
    public void preTraversalTree(Node<E> node) {
        if(node!=null) {
            node.display();
            preTraversalTree(node.leftNode);
            preTraversalTree(node.rightNode);
        }
    }
    
    public void cenTraversalTree(Node<E> node) {
        if(node!=null) {
            cenTraversalTree(node.leftNode);
            node.display();
            cenTraversalTree(node.rightNode);
        }
    }
    
    public void aftTraversalTree(Node<E> node) {
        if(node!=null) {
            aftTraversalTree(node.leftNode);
            aftTraversalTree(node.rightNode);
            node.display();
            
        }
    }
    
    
    public static void main(String[] args) {
        MyTree<Integer> myTree=new MyTree<Integer>();
        myTree.insert(23);
        myTree.insert(20);
        myTree.insert(24);
        myTree.insert(19);
        myTree.insert(21);
        myTree.insert(23);
        myTree.insert(25);
        myTree.insert(22);
        myTree.insert(30);
        myTree.aftTraversalTree(myTree.find(23));
    }
    
}

View Code