二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。
樹型結(jié)構(gòu)常被用于大量數(shù)據(jù)的運(yùn)行操作，處理效率大大高于線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)，
所以在數(shù)據(jù)結(jié)構(gòu)中占據(jù)著極其重要的地位

二叉樹

滿二叉樹

根節(jié)點(diǎn)：樹結(jié)構(gòu)的起始點(diǎn)

葉子節(jié)點(diǎn)：當(dāng)樹結(jié)構(gòu)左右節(jié)點(diǎn)孩子都為空時(shí)，稱為葉子節(jié)點(diǎn)

二叉樹每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子

二叉樹每個(gè)節(jié)點(diǎn)最多有一個(gè)父親

二叉樹同鏈表一樣，屬于動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)

靜態(tài)鏈表和動(dòng)態(tài)鏈表

1、靜態(tài)鏈表是用類似于數(shù)組方法實(shí)現(xiàn)的，是順序的存儲(chǔ)結(jié)構(gòu)，在物理地址上是連續(xù)的，而且需要預(yù)先分配地址空間大小。所以靜態(tài)鏈表的長(zhǎng)度是固定的，在做插入和刪除操作時(shí)不需要移動(dòng)元素，僅需修改指針。

2、動(dòng)態(tài)鏈表是用內(nèi)存申請(qǐng)函數(shù)動(dòng)態(tài)申請(qǐng)內(nèi)存的，所以在鏈表的長(zhǎng)度上沒有限制。動(dòng)態(tài)鏈表因?yàn)槭莿?dòng)態(tài)申請(qǐng)內(nèi)存的，所以每個(gè)節(jié)點(diǎn)的物理地址不連續(xù)，要通過節(jié)點(diǎn)創(chuàng)建next指針指向下一個(gè)節(jié)點(diǎn)。

二分搜索樹（排序樹）

二分搜索樹是二叉樹（存儲(chǔ)的元素具有可比較性，如：數(shù)字）
二分搜索樹的每個(gè)節(jié)點(diǎn)的值
[圖片上傳中...(image.png-ddd5c4-1564728631358-0)]

·大于它左子樹所有節(jié)點(diǎn)的值

·每一顆子樹也是二分搜索樹（樹型結(jié)構(gòu)的天然遞歸特征）

二分搜索樹實(shí)現(xiàn)

二分搜索樹創(chuàng)建邏輯

public class BST<E extends Comparable<E>>{
   //節(jié)點(diǎn)內(nèi)部類
   private class Node{
      public E e;
      public Node left,right;//左右孩子指針指向
      
      public Node(E e){
         this.e = e;
         left = null;
         right = null;
      }
   }

   private Node root;//根節(jié)點(diǎn)
   private int size;//樹中存儲(chǔ)元素?cái)?shù)量
   
   public BST(){
      root = null;
      size = 0;
   }

   public int size(){
      return size;
   }

   public boolean isEmpty(){
      return size == 0;
   }
}

添加新元素

這里不設(shè)計(jì)重復(fù)元素包含
若想實(shí)現(xiàn)包含需定義
左子樹＜=節(jié)點(diǎn)，右子樹＞=節(jié)點(diǎn)

public void add(E e){
   /*if(root == null){
      root = new Node(e);
      size ++;
   }
   else{
      add(root,e);
   }*/
   root = add(root ,e)
}
//向以node為根的二分搜索樹插入元素E,遞歸調(diào)用
//返回插入新節(jié)點(diǎn)后二分搜索樹的根
private Node add(Node node,E e){
   /**if(e.equals(node.e)){
      return;
   }
   else if(e.compareTo(node.e) < 0 && node.left == null){
      node.left = new Node(e);
      size++;
      return;
   }
   else if(e.compareTo(node.e) > 0 && node.right == null){
      node.right = new Node(e);
      size++;
      return;
   }*/

   //把null也當(dāng)成樹的一個(gè)節(jié)點(diǎn)
   if(node==null){
      size ++;
      return new Node(e)
   }
   //這里采用遞歸調(diào)用
   if(e.compareTo(node.e) < 0){
      node.left = add(node.left,e);
   }
   else if(e.compareTo(node.e) > 0){
      node.right = add(node.right,e);
   }

   return node;
}

查詢?cè)?/h6>

//看二分搜索樹中是否包含元素e
public boolean contains(E e){
   return contains(root,e)
}
private boolean contains(Node node,E e){
   if(node.e == null){
      return false;
   }
   if(e.compareTo(node.e) == 0){
      return true;
   }
   else if(e.compareTo(node.e) < 0){
      contain(node.left,e);
   }
   else if(e.compareTo(node.e) > 0){
      contain(node.right,e);
   }

   return false;
}

二分搜索樹的遍歷

遍歷就是把所有節(jié)點(diǎn)都訪問一遍

前序遍歷：根結(jié)點(diǎn) ---> 左子樹 ---> 右子樹

中序遍歷：左子樹 ---> 根結(jié)點(diǎn) ---> 右子樹

后序遍歷：左子樹 ---> 右子樹 ---> 根結(jié)點(diǎn)

前序遍歷(也可稱深度優(yōu)先遍歷)

public void preOrder(){
   preOrder(root)
}
//以node為根進(jìn)行前序遍歷
private void preOrder(Node node){
   if(node == null){
      return ;
   }
   System.out.println(node.e);
   preOrder(node.left);
   preOrder(node.right);
}

中序遍歷(二分搜索樹中序遍歷結(jié)果是順序的)

public void inOrder(){
   inOrder(root);
}
private void inOrder(Node node){
   if(node == null){
       return;
   }
   inOrder(node.left);
   System.out.println(node.e);
   inOrder(node.right);
}

后序遍歷

public void tailOrder(){
   tailOrder(root);
}
private void tailOrder(Node node){
   if(node == null){
       return;
   }
   tailOrder(node.left);
   tailOrder(node.right);
   System.out.println(node.e);
}

應(yīng)用：為二分搜索樹釋放資源

層序遍歷（廣度優(yōu)先遍歷）

利用隊(duì)列實(shí)現(xiàn)

public void levelOrder(){
   Queue<Node> q = new LinkedList<>();
   q.add(root);
   while(!q.isEmpty()){
      Node cur = q.remove();
      System.out.println(cur.e);
      
      if(cur.left != null)
         q.add(cur.left)
      if(cur.right != null)
         q.add(cur.right)
   }
}

廣度優(yōu)先遍歷的搜索效率更高效常用于算法設(shè)計(jì)中的最短路徑

刪除二分搜索樹最大以及最小值

//查詢最小值
public E minimum(){
  return minimum(root).e;
}
//以node為根進(jìn)行前序遍歷
private E minimum(Node node){
   if(node == null){
      return node;
   }
   minimum(node.left);
}


//查詢最大值
public E max(){
   return max(root).e;
}
//以node為根進(jìn)行前序遍歷
private E max(Node node){
   if(node == null){
      return node;
   }
   minimum(node.right);
}

//刪除最小值
public E removeMin(){
   E ret = minimum();
   root = removeMin(root);
   return ret;
}

private Node removeMin(Node node){
   if(node.left == null){
      Node rightNode = node.right;
      node.right = null;
      size--;
      return rightNode;
   }
   node.left = removeMin(node.left);
   return node;
}


//刪除最大值
public E removeMax(){
   E ret = max();
   root = removeMax(root);
   return ret;
}
private Node removeMax(Node node){
   if(node.right == null){
      Node leftNode = node.left;
      node.left= null;
      size--;
      return leftNode;
   }
   node.right = removeMax(node.right);
   return node;
}

刪除二分搜索樹任意元素

public void remove(E e){
   root = remove(root,e);
}

private Node remove(Node node,E e){
   if(node == null){
      return null;
   }

   if(e.compareTo(node.e) < 0){
      node.left = remove(node.left,e);
   }

   else if(e.compareTo(node.e) > 0){
      node.right = remove(node.right ,e);
   }

   else{ // e.compareTo(node.e) == 0
      //待刪除節(jié)點(diǎn)左子樹為空
      if(node.left == null){
         Node rightNode = node.right;
         node.right = null;
         size --;
         return rightNode;
      }
      //待刪除節(jié)點(diǎn)右子樹為空
      if(node.right == null){
         Node leftNode = node.left ;
         node.left = null;
         size --;
         return leftNode;
      }

      //待刪除節(jié)點(diǎn)左右子樹都不為空
      //找到比待刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn)，即右子樹的最小值
      //然后提取節(jié)點(diǎn)替代刪除節(jié)點(diǎn)
     Node successor = minimum(node.right);
     //是刪除了successor節(jié)點(diǎn)后的樹
     successor.right = removeMin(node.right);
     successor.left = node.left;

     node.left = node.right = null;

     return  successor;
   }
}

刪除節(jié)點(diǎn)可以選擇自己的前驅(qū)（左子樹的最大值）后繼（右子樹的最小值）

線段樹

常用于動(dòng)態(tài)變化更新的數(shù)據(jù)段：
1、區(qū)間染色

線段樹是平衡二叉樹

什么是平衡二叉樹？

一顆樹最大深度和最小深度之間的差最多為1
平衡二叉樹也是一顆完全二叉樹

基于數(shù)組的線段樹的實(shí)現(xiàn)

public class SegmentTree<E> {

    private E[] tree;//把線段樹看成滿二叉樹
    private E[] data;
    private Merger<E> merger;

    public SegmentTree(E[] arr, Merger<E> merger){
        //傳入用戶自己定義的融合器
        this.merger = merger;

        data = (E[])new Object[arr.length];

        for(int i = 0; i < arr.length; i ++){
            data[i] = arr[i];
        }

        //線段樹設(shè)為滿二叉樹，最壞情況需要4n的節(jié)點(diǎn)空間構(gòu)建成一棵樹
        tree = (E[])new Object[4 * arr.length];
        buildSegmentTree(0,0,data.length - 1);
    }

    //三個(gè)參數(shù)分別是根節(jié)點(diǎn)treeIndex，根節(jié)點(diǎn)所對(duì)應(yīng)的左區(qū)間l,以及右區(qū)間r
    //如節(jié)點(diǎn)為sum值，則sum(l,r)
    private void buildSegmentTree(int treeIndex, int l, int r){
        //已經(jīng)遍歷到最后節(jié)點(diǎn)，區(qū)間兩端點(diǎn)值相等
        if(l==r){
            tree[treeIndex] = data[l];
            return;
        }

        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);

        //左邊界+左右邊界距離除2
        //可以用(l + r) / 2,但為了防止數(shù)據(jù)溢出采用以下方法
        int mid = l + (r - l) / 2;

        buildSegmentTree(leftTreeIndex,l,mid);
        buildSegmentTree(rightTreeIndex,mid+1,r);

        //若線段樹業(yè)務(wù)為sum求和，則
        //這里使用融合接口，但未定義用戶實(shí)現(xiàn)，抽象地進(jìn)行了計(jì)算（重點(diǎn)）
        tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
    }

    public int getSize(){
        return data.length;
    }

    public E get(int index){
        return data[index];
    }

    //樹充當(dāng)成數(shù)組時(shí)左孩子添加的索引
    private int leftChild(int index){
        return 2*index + 1;
    }
    //樹充當(dāng)成數(shù)組時(shí)右孩子添加的索引
    private int rightChild(int index){
        return 2*index + 2;
    }
}

再定義一個(gè)融合接口merge
用于對(duì)區(qū)間進(jìn)行操作，類似Comparator

public interface Merger<E> {
    E merge(E a ,E b);
}

這樣就實(shí)現(xiàn)了一顆線段樹的結(jié)構(gòu)

線段樹的查詢

//線段樹的區(qū)間查詢
    public E query(int queryL, int queryR){
        if (queryL < 0 || queryL > data.length ||
                queryR < 0 || queryR > data.length || queryL >queryR){
            throw new IllegalArgumentException("Index is illegal" );
        }

        return query(0,0,data.length - 1,queryL,queryR);
    }

    private E query(int treeIndex, int l, int r, int queryL, int queryR){
      //若返回的左右區(qū)間點(diǎn)與用戶所需要的一致則返回該區(qū)間
        if(l == queryL && r = queryR){
            return tree[treeIndex];
        }
        int mid = l + (r - l) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
      //若mid+1值小于用戶查詢左區(qū)間，說明l值開始的子樹查詢不到所需的值，則直接從右子樹查詢
        if(queryL >= mid + 1){
            return query(rightTreeIndex, mid + 1 , r,queryL,queryR);
        }
      //若mid值大用戶查詢右區(qū)間，說明l值開始的子樹查詢不到所需的值，則直接從右子樹查詢
        else if(queryR <= mid){
            return query(leftTreeIndex,l,mid,queryL,queryR);
        }
      //這部分是對(duì)于值不完全包含在區(qū)間內(nèi)的遞歸
        E leftResult = query(leftTreeIndex,l,mid,queryL,mid);
        E rightResult = query(rightTreeIndex,mid+1,r,mid+1,queryR);

        return merger.merge(leftResult,rightResult);
    }

線段樹的更新

//線段樹的元素更新
    public void set(int index, E e){
        data[index] = e;
        set(0,0,data.length - 1, index, e);
    }

    private void set(int treeIndex, int l, int r, int index, E e){
        //找到需要更新的索引
        if(l == r){
            tree[treeIndex] = e;
            return;
        }

        int mid = l + (r - l) / 2;

        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
c
        if(index >= mid + 1){
            set(rightTreeIndex,mid+1,r,index,e);
        }
        else if(index <= mid){
            set(leftTreeIndex,l,mid,index,e);
        }

        tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
    }

線段樹利用其索引性質(zhì)來判斷查詢以及更新等操作

Trie字典樹（前綴樹）

適用于快速查詢，但也有占用空間問題的劣勢(shì)

構(gòu)建Tire字典樹

字典樹指向節(jié)點(diǎn)利用映射TreeMap來構(gòu)建
來表示每個(gè)字母對(duì)應(yīng)的下一個(gè)節(jié)點(diǎn)

import java.util.TreeMap;

public class Trie {

    private class Node{

        public boolean isWord;//當(dāng)訪問到當(dāng)前節(jié)點(diǎn)是是否已經(jīng)拼接成一個(gè)單詞
        public TreeMap<Character, Node> next;

        public Node(boolean isWord){
             this.isWord = isWord;
            next = new TreeMap<>();
        }

        public Node(){
            this(false);
        }
    }

    private Node root;
    private int size;

    public Trie(){
        root = new Node();
        size = 0;
    }

    public int getSize(){
        return size;
    }

    //向Trie添加一個(gè)新的單詞
    public void add(String word){

        Node cur = root;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(cur.next.get(c) == null)
                cur.next.put(c, new Node());
            cur = cur.next.get(c);
        }
        if(!cur.isWord){
            cur.isWord = true;
            size ++;
        }
    }

    //查詢單詞word是否存在
    public boolean contains(String word){
        Node cur = root;
        for (int i = 0;i < word.length(); i++){
            char c = word.charAt(i);
            if(cur.next.get(c) == null){
                return false;
            }
            cur = cur.next.get(c);
        }
        return cur.isWord;
    }
}

Trie的前綴查詢

//前綴查詢,prefix為前綴
    public boolean isPrefix(String prefix){
        Node cur = root;
        for (int i = 0;i < prefix.length(); i++){
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null){
                return false;
            }
            cur = cur.next.get(c);
        }
        return true;
    }

Trie實(shí)現(xiàn)簡(jiǎn)單的模式匹配

條件：當(dāng)搜索一個(gè)單詞時(shí)，.可以當(dāng)作是匹配任意字母

public boolean search(String word){
    return match(root, word, 0);
}

//index代表當(dāng)前索引的字母
private boolean match(Node node, String word, int index){
    if(index == word.length()){
        return  node.isWord;
    }
    char c = word.charAt(index);
    //當(dāng)匹配到的字符不是.的時(shí)候
    if(c != ' . '){
        if(node.next.get(c) == null){
            return false;
        }
        return match(node.next.get(c), word, index + 1);
    }
    else{
        //這里使用TreeMap的方法取出下一個(gè)節(jié)點(diǎn)所有的鍵
        for(char nextChar: node.next.keySet){
            if(match(node.next.get(nextChar), word, index + 1)){
                return true;
            }
            return false;
        }
    }
}

Trie與字符串映射的應(yīng)用

實(shí)現(xiàn)一個(gè) MapSum 類里的兩個(gè)方法，insert 和 sum。

對(duì)于方法 insert，你將得到一對(duì)（字符串，整數(shù)）的鍵值對(duì)。字符串表示鍵，整數(shù)表示值。如果鍵已經(jīng)存在，那么原來的鍵值對(duì)將被替代成新的鍵值對(duì)。

對(duì)于方法 sum，你將得到一個(gè)表示前綴的字符串，你需要返回所有以該前綴開頭的鍵的值的總和。

import java.util.TreeMap;

class MapSum {

    private class Node{

        public int value;
        public TreeMap<Character, Node> next;

        public Node(int value){
            this.value = value;
            next = new TreeMap<>();
        }

        public Node(){
            this(0);
        }
    }

    private Node root;

    public MapSum() {
        root = new Node();
    }

    public void insert(String word, int val) {
        Node cur = root;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(cur.next.get(c) == null)
                cur.next.put(c, new Node());
            cur = cur.next.get(c);
        }
        cur.value = val;
    }

    public int sum(String prefix) {

        Node cur = root;
        for(int i = 0; i < prefix.length(); i++){
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null){
                return 0;
            }
            cur = cur.next.get(c);
        }
        return sum(cur);
    }

    private int sum(Node node){

        //已經(jīng)遞歸到了葉子節(jié)點(diǎn)
        if(node.next.size() == 0){
            return node.value;
        }

        int res = node.value;
        //判斷是否存在孩子節(jié)點(diǎn)，若有繼續(xù)循環(huán)
        for (char c:node.next.keySet()){
            res += sum(node.next.get(c));
        }
        return res;
    }
}