概述

在分析樹形結(jié)構(gòu)之前誊锭，先看一下樹形結(jié)構(gòu)在整個數(shù)據(jù)結(jié)構(gòu)中的位置

數(shù)據(jù)結(jié)構(gòu)

當(dāng)然恬口，沒有圖校读，現(xiàn)在還沒有足夠的水平去分析圖這種太復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，表數(shù)據(jù)結(jié)構(gòu)包含線性表跟鏈表祖能，也就是經(jīng)常說的數(shù)組歉秫，棧，隊列等养铸，在前面的Java容器類框架中已經(jīng)分析過了雁芙，上面任意一種數(shù)據(jù)結(jié)構(gòu)在java中都有對應(yīng)的實現(xiàn)，比如說ArrayList對應(yīng)數(shù)組钞螟，LinkedList對應(yīng)雙向鏈表兔甘，HashMap對應(yīng)了散列表，JDK1.8之后的HashMap采用的是紅黑樹實現(xiàn)鳞滨，下面單獨把二叉樹抽取出來：

二叉樹

由于樹的基本概念基本上大家都有所了解洞焙，現(xiàn)在重點介紹一下二叉樹

正文

二叉樹

二叉樹(binary tree)是一棵樹，其中每個節(jié)點都不能有多于兩個的兒子拯啦。

二叉樹

分類

• 滿二叉樹：若設(shè)二叉樹的高度為h澡匪，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)褒链，第h層有葉子結(jié)點唁情，并且葉子結(jié)點都是從左到右依次排布，這就是完全二叉樹甫匹。
• 完全二叉樹：除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹甸鸟。
• 平衡二叉樹：稱為AVL樹（區(qū)別于AVL算法），它是一棵二叉排序樹赛惩，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1哀墓，并且左右兩個子樹都是一棵平衡二叉樹。

對于完全二叉樹喷兼，若某個節(jié)點數(shù)為i，左子節(jié)點位2i+1后雷，右子節(jié)點為2i+2季惯。

實現(xiàn)

下面用代碼實現(xiàn)一個二叉樹

public class BinaryNode {
    Object data;
    BinaryNode left;
    BinaryNode right;
}

遍歷

二叉樹的遍歷有兩種：按照節(jié)點遍歷與層次遍歷

節(jié)點遍歷

• 前序遍歷：遍歷到一個節(jié)點后，即刻輸出該節(jié)點的值臀突，并繼續(xù)遍歷其左右子樹(根左右)勉抓。
• 中序遍歷：遍歷一個節(jié)點后，將其暫存候学，遍歷完左子樹后藕筋，再輸出該節(jié)點的值，然后遍歷右子樹(左根右)梳码。
• 后序遍歷：遍歷到一個節(jié)點后隐圾，將其暫存伍掀，遍歷完左右子樹后，再輸出該節(jié)點的值(左右根)暇藏。

構(gòu)造完全二叉樹

enter image description here

就以上圖的二叉樹為例蜜笤，首先用代碼構(gòu)造一棵完全二叉樹
節(jié)點類TreeNode

public class TreeNode {
    private int value;
    private TreeNode leftChild;
    private TreeNode rightChild;

    public TreeNode(int value) {
        super();
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public TreeNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(TreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(TreeNode rightChild) {
        this.rightChild = rightChild;
    }

}

生成完全二叉樹

 //數(shù)組
 private int[] saveValue = {0,1, 2, 3, 4, 5, 6};
  private ArrayList<TreeNode> list = new ArrayList<>();
   public TreeNode createTree() {
   //將所有的節(jié)點保存進(jìn)一個List集合里面
        for (int i = 0; i < saveValue.length; i++) {
            TreeNode treeNode = new TreeNode(saveValue[i]);
            list.add(treeNode);
        }
    //根據(jù)完全二叉樹的性質(zhì)，i節(jié)點的左子樹是2*i+1盐碱，右節(jié)點字?jǐn)?shù)是2*i+2
         for (int i = 0; i < list.size() / 2; i++) {
            TreeNode treeNode = list.get(i);
            //判斷左子樹是否越界
            if (i * 2 + 1 < list.size()) {
                TreeNode leftTreeNode = list.get(i * 2 + 1);
                treeNode.setLeftChild(leftTreeNode);
            }
            //判斷右子樹是否越界
            if (i * 2 + 2 < list.size()) {
                TreeNode rightTreeNode = list.get(i * 2 + 2);
                treeNode.setRightChild(rightTreeNode);
            }
        }
        return list.get(0);
    }

前序遍歷

   //前序遍歷
    public static void preOrder(TreeNode root) {
        if (root == null)
            return;
        System.out.print(root.value + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

遍歷結(jié)果: 0 1 3 4 2 5 6

中序遍歷

   //中序遍歷
    public static void midOrder(TreeNode root) {
        if (root == null)
            return;
        midOrder(root.left);
        System.out.print(root.value + " ");
        midOrder(root.right);
    }

遍歷結(jié)果：3 1 4 0 5 2 6

后序遍歷

  //后序遍歷
    public static void postOrder(TreeNode root) {
        if (root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value + " ");
    }

遍歷結(jié)果：3 4 1 5 6 2 0
上述三種方式都是采用遞歸的方式進(jìn)行遍歷的把兔，當(dāng)然也可以迭代，感覺迭代比較麻煩瓮顽，遞歸代碼比較簡潔县好，仔細(xì)觀察可以發(fā)現(xiàn)，實際上三種遍歷方式都是一樣的暖混，知識打印value的順序不一樣而已聘惦，是一種比較巧妙的方式。

層次遍歷

二叉樹的層次遍歷可以分為深度優(yōu)先遍歷跟廣度優(yōu)先遍歷

• 深度優(yōu)先遍歷：實際上就是上面的前序儒恋、中序和后序遍歷善绎，也就是盡可能去遍歷二叉樹的深度。
• 廣度優(yōu)先遍歷：實際上就是一層一層的遍歷诫尽，按照層次輸出二叉樹的各個節(jié)點禀酱。

深度優(yōu)先遍歷

由于上面的前序、中序和后續(xù)遍歷都是采用的遞歸的方式進(jìn)行遍歷牧嫉，下面就以前序遍歷為例剂跟，采用非遞歸的方式進(jìn)行遍歷

步驟

• 若二叉樹為空,返回：
• 用一個stack來保存二叉樹
• 然后遍歷節(jié)點的時候先讓右子樹入棧，再讓左子樹入棧酣藻，這樣右子樹就會比左子樹后出棧曹洽，從而實現(xiàn)先序遍歷

//2.前序遍歷（迭代）
   public static void preorderTraversal(TreeNode root) {  
       if(root == null){  
           return;  
       }  
       Stack<TreeNode> stack = new Stack<TreeNode>();  
       stack.push(root);  
       while( !stack.isEmpty() ){  
           TreeNode cur = stack.pop();     // 出棧棧頂元素  
           System.out.print(cur.data + " ");  
           //先壓右子樹入棧
           if(cur.right != null){  
               stack.push(cur.right);  
           }  
           //再壓左子樹入棧
           if(cur.left != null){  
               stack.push(cur.left);  
           }  
       }  
   }  

遍歷結(jié)果：0 1 3 4 2 5 6

廣度優(yōu)先遍歷

所謂廣度優(yōu)先遍歷就是一層一層的遍歷，所以只需要按照每層的左右順序拿到二叉樹的節(jié)點辽剧，再依次輸出就OK了

步驟

• 用一個LinkedList保留所有的根節(jié)點
• 依次輸出即可

  //分層遍歷
    public static void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(root);
        while (!queue.isEmpty()) {
            //打印linkedList的第一次元素
            TreeNode cur = queue.removeFirst();
            System.out.print(cur.value + " ");
            //依次添加每個節(jié)點的左節(jié)點
            if (cur.left != null) {
                queue.add(cur.left);
            }
            //依次添加每個節(jié)點的右節(jié)點
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

遍歷結(jié)果：0 1 2 3 4 5 6

二叉堆

二叉堆是一棵完全二叉樹或者是近似完全二叉樹送淆，同時二叉堆還滿足堆的特性：父節(jié)點的鍵值總是保持固定的序關(guān)系于任何一個子節(jié)點的鍵值，且每個節(jié)點的左子樹和右子樹都是一個二叉堆怕轿。

分類

• 最大堆：父節(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值

• 最小堆：父節(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值

  
  
  二叉堆的分類

由于二叉堆 的根節(jié)點總是存放著最大或者最小元素偷崩，所以經(jīng)常被用來構(gòu)造優(yōu)先隊列(Priority Queue),當(dāng)你需要找到隊列中最高優(yōu)先級或者最低優(yōu)先級的元素時，使用堆結(jié)構(gòu)可以幫助你快速的定位元素撞羽。

性質(zhì)

• 結(jié)構(gòu)性質(zhì)：堆是一棵被完全填滿的二叉樹阐斜，有可能的例外是在底層，底層上的元素從左到右填入诀紊。這樣的樹稱為完全二叉樹谒出。

  
  
  一棵完全二叉樹

實現(xiàn)

二叉堆可以用數(shù)組實現(xiàn)也可以用鏈表實現(xiàn)，觀察上述的完全二叉樹可以發(fā)現(xiàn)，是比較有規(guī)律的笤喳，所以完全可以使用一個數(shù)組而不需要使用鏈为居。下面用數(shù)組來表示上圖所對應(yīng)的堆結(jié)。

完全二叉樹的數(shù)組實現(xiàn)

對于數(shù)組中任意位置i的元素莉测，其左兒子在位置2i上颜骤，右兒子在左兒子后的單元(2i+1)中，它的父親則在位置[i/2上面]

public class MaxHeap<Item extends Comparable> {

    protected Item[] data;
    protected int count;
    protected int capacity;
    // 構(gòu)造函數(shù), 構(gòu)造一個空堆, 可容納capacity個元素
    public MaxHeap(int capacity) {
        data = (Item[]) new Comparable[capacity + 1];
        count = 0;
        this.capacity = capacity;
    }

    // 返回堆中的元素個數(shù)
    public int size() {
        return count;
    }

    // 返回一個布爾值, 表示堆中是否為空
    public boolean isEmpty() {
        return count == 0;
    }

    // 像最大堆中插入一個新的元素 item
    public void insert(Item item) {
        assert count + 1 <= capacity;
        data[count + 1] = item;
        count++;
        shiftUp(count);
    }

    // 交換堆中索引為i和j的兩個元素
    private void swap(int i, int j) {
        Item t = data[i];
        data[i] = data[j];
        data[j] = t;
    }
    //調(diào)整堆中的元素捣卤，使其成為一個最大堆
    private void shiftUp(int k) {
    // k/2表示k節(jié)點的父節(jié)點
        while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
        //子節(jié)點跟父節(jié)點進(jìn)行比較忍抽，如果父節(jié)點小于子節(jié)點則進(jìn)行交換
            swap(k, k / 2);
            k /= 2;
        }
    }

}

構(gòu)造一個二叉堆

  // 測試 MaxHeap
    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<>(100);
        int N = 50; // 堆中元素個數(shù)
        int M = 100; // 堆中元素取值范圍[0, M)
        for (int i = 0; i < N; i++)
            maxHeap.insert((int) (Math.random() * M));
        System.out.println(maxHeap.size());
    }

insert操作

    public void insert(Item item) {
        //從第1個元素開始賦值
        assert count + 1 <= capacity;
        data[count + 1] = item;
        count++;
        //上慮操作
        shiftUp(count);
    }

上慮操作

先將新插入的元素加到數(shù)組尾部，然后跟父節(jié)點進(jìn)行比較董朝，如果比父節(jié)點大就進(jìn)行交換

    private void shiftUp(int k) {
    // k/2表示k節(jié)點的父節(jié)點
        while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
        //子節(jié)點跟父節(jié)點進(jìn)行比較鸠项，如果父節(jié)點小于子節(jié)點則進(jìn)行交換
            swap(k, k / 2);
            k /= 2;
        }
    }

獲取最大元素

public Integer extractMax(){
        assert count > 0;
        Integer ret = data[1];
        swap( 1 , count );
        count --;
        //下慮操作
        shiftDown(1);
        return ret;
    }

下慮操作

先將根節(jié)點跟最后一個元素進(jìn)行交換，然后將count減1子姜，然后根節(jié)點再跟左子樹與右子樹之間的最大值進(jìn)行比較

 private void shiftDown(int k){
        while( 2*k <= count ){
            int j = 2*k; // 在此輪循環(huán)中,data[k]和data[j]交換位置
            if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
                j ++;
            // data[j] 是 data[2*k]和data[2*k+1]中的最大值
            if( data[k].compareTo(data[j]) >= 0 ) 
            //當(dāng)前節(jié)點比根節(jié)點大祟绊，中斷循環(huán)
            break;
            //交換節(jié)點跟子樹
            swap(k, j);
            k = j;
        }
    }

二叉查找樹

二叉查找樹：對于樹中的每個節(jié)點X，它的左子樹中所有項的值小于X中的項哥捕，而它的右子樹中的所有項的值大于X中的項牧抽。

兩棵二叉樹(只有左邊的樹是查找樹)

實現(xiàn)

public class BST<Key extends Comparable<Key>, Value> {
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;
        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
        public Node(Node node){
            this.key = node.key;
            this.value = node.value;
            this.left = node.left;
            this.right = node.right;
        }
    }
   // 構(gòu)造函數(shù), 默認(rèn)構(gòu)造一棵空二分搜索樹
    public BST() {
        root = null;
        count = 0;
    }

    // 返回二分搜索樹的節(jié)點個數(shù)
    public int size() {
        return count;
    }
    // 返回二分搜索樹是否為空
    public boolean isEmpty() {
        return count == 0;
    }
  
  

    }

contains方法

    // 調(diào)用contains (root,key)

    public boolean contain(Key key){
        return contain(root, key);
    }
  // 查看以node為根的二分搜索樹中是否包含鍵值為key的節(jié)點, 使用遞歸算法
    private boolean contain(Node node, Key key){
        if( node == null )
            return false;
            //根節(jié)點的key跟查詢的key相同，直接返回true
        if( key.compareTo(node.key) == 0 )
            return true;
            //key小的話遍歷左子樹
        else if( key.compareTo(node.key) < 0 )
            return contain( node.left , key );
            //key大的話遍歷右子樹
        else // key > node->key
            return contain( node.right , key );
    }

insert方法

     // 向二分搜索樹中插入一個新的(key, value)數(shù)據(jù)對
    public void insert(Key key, Value value){
        root = insert(root, key, value);
    }
    // 向以node為根的二分搜索樹中, 插入節(jié)點(key, value), 使用遞歸算法
    // 返回插入新節(jié)點后的二分搜索樹的根
    private Node insert(Node node, Key key, Value value){
        //空樹直接返回
        if( node == null ){
            count ++;
            return new Node(key, value);
        }
        //如果需要插入的key跟當(dāng)前的key相同遥赚，則將值替換成最新的值
        if( key.compareTo(node.key) == 0 )
            node.value = value;
         //如果需要插入的key小于當(dāng)前的key,從左子樹進(jìn)行插入
        else if( key.compareTo(node.key) < 0 )
            node.left = insert( node.left , key, value);
        else    
        //如果需要插入的key大于當(dāng)前的key,從右子樹進(jìn)行插入
            node.right = insert( node.right, key, value);
        return node;
    }

finMin方法

    // 尋找二分搜索樹的最小的鍵值
    public Key minimum(){
        assert count != 0;
        Node minNode = minimum( root );
        return minNode.key;
    }
    
    // 返回以node為根的二分搜索樹的最小鍵值所在的節(jié)點
    private Node minimum(Node node){
        //遞歸遍歷左子樹
        if( node.left == null )
            return node;
        return minimum(node.left);
    }

finMax方法

 // 尋找二分搜索樹的最大的鍵值
    public Key maximum(){
        assert count != 0;
        Node maxNode = maximum(root);
        return maxNode.key;
    }
    // 返回以node為根的二分搜索樹的最大鍵值所在的節(jié)點
    private Node maximum(Node node){
    //遞歸遍歷右子樹
        if( node.right == null )
            return node;
        return maximum(node.right);
    }

search方法

  // 在二分搜索樹中搜索鍵key所對應(yīng)的值扬舒。如果這個值不存在, 則返回null
    public Value search(Key key){
        return search( root , key );
    }
   
    // 在以node為根的二分搜索樹中查找key所對應(yīng)的value, 遞歸算法
    // 若value不存在, 則返回NULL
    private Value search(Node node, Key key){
        if( node == null )
            return null;
        if( key.compareTo(node.key) == 0 )
            return node.value;
        else if( key.compareTo(node.key) < 0 )
            return search( node.left , key );
        else // key > node->key
            return search( node.right, key );
    }

上面分析了三種比較特殊的樹形結(jié)構(gòu)，二叉樹凫佛，二叉堆以及二叉搜索樹讲坎，尤其是二叉堆跟二叉搜索樹，尤其是二叉堆主要用于優(yōu)先隊列愧薛，二叉搜索樹主要用來查找晨炕。