二叉樹與優先級隊列

1.樹

樹是由n個數據構成的非線性結構，它是根朝上，葉朝下。

注意：樹形結構之中，子樹之間不能連接，不然就不構成樹形結構

1.子樹之間沒有交集

2.除了根節點以外，每一個節點有且只有一個父親節點

3.一個n個節點的樹，有n-1條邊

1.1樹的一些概念

結點的度：一個結點含有子樹的個數稱為該結點的度；如上圖：A的度為6

樹的度：一棵樹中，所有結點度的最大值稱為樹的度；如上圖：樹的度為6

葉子結點或終端結點：度為0的結點稱為葉結點；如上圖：B、C、H、I...等節點為葉結點雙親結點或父結點：若一個結點含有子結點，則這個結點稱為其子結點的父結點；如上圖：A是B的父結點

孩子結點或子結點：一個結點含有的子樹的根結點稱為該結點的子結點；如上圖：B是A的孩子結點

根結點：一棵樹中，沒有雙親結點的結點；如上圖：A?

結點的層次：從根開始定義起，根為第1層，根的子結點為第2層，以此類推

樹的高度或深度：樹中結點的最大層次；如上圖：樹的高度為4 樹的以下概念只需了解，

非終端結點或分支結點：度不為0的結點；如上圖：D、E、F、G...等節點為分支結點

兄弟結點：具有相同父結點的結點互稱為兄弟結點；如上圖：B、C是兄弟結點

堂兄弟結點：雙親在同一層的結點互為堂兄弟；如上圖：H、I互為兄弟結點

結點的祖先：從根到該結點所經分支上的所有結點；如上圖：A是所有結點的祖先

子孫：以某結點為根的子樹中任一結點都稱為該結點的子孫。如上圖：所有結點都是A的子孫

森林：由m（m>=0）棵互不相交的樹組成的集合稱為森林

2.二叉樹

2.1概念

一棵二叉樹的節點是有限集合

對于任意的二叉樹，都是由下列情況組合而成

2.2兩種特殊的二叉樹

1.滿二叉樹：一棵二叉樹樹，每一層的節點數都到達了最大值，那么這就是滿二叉樹。也就是說如果一棵二叉樹是k層，那么這棵樹的節點樹，且結點總數是 $2^{k}$ -1，則它就是滿二叉樹。

2.完全二叉樹：完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n 個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從0至n-1的結點一一對應時稱之為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。

2.3二叉樹的性質

1. 若規定根結點的層數為1，則一棵非空二叉樹的第i層上最多有(i>0)個結點

2. 若規定只有根結點的二叉樹的深度為1，則深度為K的二叉樹的最大結點數是 $2^{k}$ -1(k>=0)

3. 對任何一棵二叉樹, 如果其葉結點個數為 n0, 度為2的非葉結點個數為 n2,則有n0＝n2＋1

4. 具有n個結點的完全二叉樹的深度k為 $\log_{2}n+1$ 上取整

5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的順序對所有節點從0開始編號，則對于序號為i 的結點有：

? ? ? ? ? ? ? ??若i>0，雙親序號：(i-1)/2；i=0，i為根結點編號，無雙親結點

? ? ? ? ? ? ? 若2i+1<n? 左孩子序號：2i+1，否則沒有左孩子

? ? ? ? ? ? ? 若2i+2<n? 右孩子序號：2i+1，否則沒有右孩子

2.4二叉樹的存儲

二叉樹的存儲結構分為：順序存儲和類似于鏈表的鏈式存儲。

二叉樹的鏈式存儲是通過一個一個的節點引用起來的，常見的表示方式有二叉和三叉表示方式，具體如下

//孩子表示法
class Node {int val;  //用于儲存數據Node left; //表示左孩子，通常為以左子樹為根節點的二叉樹Node right;  //表示右孩子，通常為右子樹為根節點的二叉樹
}
// 孩子雙親表示法
class Node {int val;        // 數據域Node left;      // 左孩子的引用，常常代表左孩子為根的整棵左子樹Node right;     // 右孩子的引用，常常代表右孩子為根的整棵右子樹Node parent;    // 當前節點的根節點
}

2.2二叉樹的基本操作

存儲方式是孩子表示方法

BinaryTree類

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class BinaryTree {public static class TreeNode {public int val;public TreeNode left;//儲存左子樹public TreeNode rigth;//儲存右子樹public TreeNode(int val) {this.val = val;}@Overridepublic String toString() {return "TreeNode{" +"val=" + val +'}';}}//創建一個二叉樹public TreeNode createbinarytree() {TreeNode A = new TreeNode(1);TreeNode B = new TreeNode(2);TreeNode C = new TreeNode(3);TreeNode D = new TreeNode(4);TreeNode E = new TreeNode(5);TreeNode F = new TreeNode(6);TreeNode G = new TreeNode(7);TreeNode H = new TreeNode(8);//連接數的結構A.left = B;A.rigth = C;B.left = D;B.rigth = E;C.left = F;C.rigth = G;E.rigth = H;return A;}//先實現三種遍歷方法// 前序遍歷public void preOrder(TreeNode root) {//NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點--->根的左子樹--->根的右子樹。//遞歸的結束條件if (root == null) {return;}System.out.print(" " + root.val);preOrder(root.left);preOrder(root.rigth);//走到結尾這個循環結束}//不使用遞歸的的方法實現前序遍歷public void preOrder1(TreeNode root){//借用棧來實現if(root==null){return ;}Stack<TreeNode> stack=new Stack<>();TreeNode cur=root;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);System.out.print(cur.val+" ");cur=cur.left;}TreeNode top=stack.pop();cur=top.rigth;}}// 中序遍歷public void inOrder(TreeNode root) {//LNR：中序遍歷(Inorder Traversal)——根的左子樹--->根節點--->根的右子樹。if (root == null) {return;}inOrder(root.left);System.out.print(" " + root.val);inOrder(root.rigth);}//不使用遞歸的的方法實現中序遍歷public void inOrder1(TreeNode root){//借用棧來實現iif(root==null){return ;}Stack<TreeNode> stack=new Stack<>();TreeNode cur=root;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur=cur.left;}TreeNode top=stack.pop();System.out.print(top.val+" ");cur=top.rigth;}}// 后序遍歷public void postOrder(TreeNode root) {//LRN：后序遍歷(Postorder Traversal)——根的左子樹--->根的右子樹--->根節點。if (root == null) {return;}postOrder(root.left);postOrder(root.rigth);System.out.print(" " + root.val);}//使用不遞歸的方法使用后序遍歷public void postOrder1(TreeNode root){//借用棧來實現if(root==null){return ;}Stack<TreeNode> stack=new Stack<>();TreeNode cur=root;TreeNode prve=null;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur=cur.left;}TreeNode top=stack.peek();if(top==null||top.rigth==prve){System.out.println(top.val+" ");prve= stack.pop();}else{cur=top.rigth;}}}//獲取數中節點個數public int nodesize;//第一種遍歷式獲取public void Nodesize1(TreeNode root) {//采用前序遍歷if (root == null) {return;}//遇見節點將打印改成nodesize++nodesize++;Nodesize1(root.left);Nodesize1(root.rigth);}//第二種獲取節點個數方法//左子樹節點個數+右子樹節點個數+根節點個數public int Nodesize2(TreeNode root) {if (root == null) {return 0;}return Nodesize2(root.left) + Nodesize2(root.rigth) + 1;}// 獲取葉子節點的個數//依舊兩種方法//第一遍種歷二叉樹public int getLeafNodeCount;public void getLeafNodeCount1(TreeNode root) {if (root == null) {return;}if (root.left == null && root.rigth == null) {getLeafNodeCount++;}getLeafNodeCount1(root.left);getLeafNodeCount1(root.rigth);}//第二種獲取葉子節點個數//左子樹葉子+右子樹葉子節點個數public int getGetLeafNodeCount2(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.rigth == null) {return 1;}return getGetLeafNodeCount2(root.left) + getGetLeafNodeCount2(root.rigth);}// 獲取第K層節點的個數public int getKLevelNodeCount(TreeNode root, int k) {//統計k層的節點個數，先找到第k-1層if (k == 1) {if (root == null) {return 0;} else {return 1;}}return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.rigth, k - 1);}// 獲取二叉樹的高度public int getHeight(TreeNode root) {//二叉樹的高度等于左子樹高度和右子樹高度的最大值if(root==null) {return 0;}return getHeight(root.left)>getHeight(root.rigth)?getHeight(root.left)+1:getHeight(root.rigth)+1;}// 檢測值為value的元素是否存在public TreeNode find(TreeNode root, int val){if(root.val==val){return root;}if(root.left!=null){TreeNode leftT=find(root.left,val);if(leftT!=null){return leftT;}}if(root.rigth!=null){TreeNode rigthT =find(root.rigth,val);if(rigthT!=null){return rigthT;}}return null;}//層序遍歷public void levelOrder(TreeNode root){if(root==null){return;}//創建一個隊列Queue<TreeNode> queue=new LinkedList<>();queue.offer(root);TreeNode cur=root;while(!queue.isEmpty()){//先將隊列元素彈出cur=queue.poll();System.out.print(cur.val+" ");if(cur.left!=null){queue.offer(cur.left);}if(cur.rigth!=null){queue.offer(cur.rigth);}}System.out.println();}// 判斷一棵樹是不是完全二叉樹public  boolean isCompleteTree(TreeNode root){//完全二叉樹從左到右依次填滿Queue<TreeNode> queue=new LinkedList<>();TreeNode cur=root;queue.offer(cur);while(queue.peek()!=null){cur=queue.poll();queue.offer(cur.left);queue.offer(cur.rigth);}while(!queue.isEmpty()){if(queue.poll()!=null){return false;}}return true;}public static void main(String[] args) {}
}

Test類

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class Test {public static void main(String[] args) {//調用創建二叉樹BinaryTree binaryTree=new BinaryTree();//調用類中2的成員變量BinaryTree.TreeNode root=binaryTree.createbinarytree();//測試前序遍歷打印binaryTree.preOrder(root);System.out.println();//  //測試前序遍歷打印1binaryTree.preOrder1(root);System.out.println();System.out.println("==============================");System.out.println();//測試中序遍歷binaryTree.inOrder(root);System.out.println();//測試中序遍歷的非遞歸方法binaryTree.inOrder1(root);System.out.println("===============================");System.out.println();//測試后序遍歷binaryTree.postOrder(root);System.out.println();//測試后續遍歷的非遞歸方法binaryTree.postOrder1(root);System.out.println("=========================");System.out.println();//打印節點個數binaryTree.Nodesize1(root);System.out.println("二叉樹結點個數:"+binaryTree.nodesize);//測試第二種打印節點個數方法System.out.println("二叉樹結點個數:"+binaryTree.Nodesize2(root));//測試第一種葉子節點個數binaryTree.getLeafNodeCount1(root);System.out.println("二叉樹葉子節點個數:"+binaryTree.getLeafNodeCount);//測試第二種葉子節點個數System.out.println("二叉樹葉子節點個數:"+binaryTree.getGetLeafNodeCount2(root));//測試統計第k層的節點個數System.out.println("第1層的節點個數為"+binaryTree.getKLevelNodeCount(root, 1));System.out.println("第2層的節點個數為"+binaryTree.getKLevelNodeCount(root, 2));System.out.println("第3層的節點個數為"+binaryTree.getKLevelNodeCount(root, 3));System.out.println("第4層的節點個數為"+binaryTree.getKLevelNodeCount(root, 4));//測試計算二叉樹的高度System.out.println("二叉樹的高度為:"+binaryTree.getHeight(root));//測試二叉樹的是否存在的元素List<List<Integer>> llist=new ArrayList<List<Integer>>();List<Integer> list1=new ArrayList<>();llist.add(list1);Queue<Integer> queue=new LinkedList<>();queue.offer(1);System.out.println(queue.poll());System.out.println("元素1存在節點"+binaryTree.find(root, 1)+"中");System.out.println("元素4存在節點"+binaryTree.find(root, 4)+"中");System.out.println("元素8存在節點"+binaryTree.find(root, 8)+"中");System.out.println("元素7存在節點"+binaryTree.find(root, 7)+"中");//測試二叉樹的層序遍歷binaryTree.levelOrder(root);//判斷二叉樹是否是完全二叉樹System.out.println("判斷這棵樹是否是完全二叉樹 "+binaryTree.isCompleteTree(root));}
}

3.優先隊列（PriorityQueue）

3.1堆的性質

堆邏輯上是一顆完全二叉樹，物理上是存儲在數組中

總結：一顆完全二叉樹以層序遍歷方式放入數組中存儲，這種方式的主要用法就是堆的表示。

? 關于堆下標位置的計算

如果已知父親(parent) 的下標，

則：左孩子(left) 下標 = 2 * parent + 1;

? ? ? ?右孩子(right) 下標 = 2 * parent + 2;

已知孩子（不區分左右）(child)下標，

則：? ??雙親(parent) 下標 = (child - 1) / 2;

3.2堆的分類

大堆：根節點大于左右兩個子節點的完全二叉樹（父親節點大于其子節點），叫做大堆，或者大根堆，或者最大堆。

小堆：根節點小于左右兩個子節點的完全二叉樹叫小堆（父親節點小于其子節點），或者小根堆，或者最小堆。

3.3堆的底層代碼實現

創建小根堆

創建大根堆

向上調整

現在有一個堆，我們需要在堆的末尾插入數據，再對其進行調整，使其仍然保持堆的結構，這就是向上調整。

以大堆為例：

向下調整

堆的刪除和添加

PriorityQueue類

import java.lang.reflect.Array;
import java.util.Arrays;public class PriorityQueue {public int[] elem;public int usedsize;public PriorityQueue() {this.elem=new int[10];}public void initelem(int [] array){for(int i=0;i<array.length;i++){this.elem[i]=array[i];usedsize++;}}public void elempeek(){for(int i=0;i<this.usedsize;i++){System.out.print(elem[i]+" ");}}//創建小根堆public void Smallrootpiles(){//小根堆的節點數要大于子樹//第一步先確定有多少個樹,利用最后一個節點來找到父親節點for(int parent=(usedsize-1-1)/2;parent>=0;parent--){//也是一樣采用向下調整的方法siftDown2(parent,usedsize);}}public void siftDown2(int parent,int usedsize){//parent:代表調整子樹的起始位置//usedsize:判斷子樹是否還需要調整//1.根據父親節點，找到左子樹孩子節點int child=parent*2+1;//2.找到孩子之間的最小值while(child<usedsize){if(child+1<usedsize&&elem[child]>elem[child+1]){child++;}if(elem[child]<elem[parent]){int num=elem[parent];elem[parent]=elem[child];elem[child]=num;parent=child;child=child*2+1;}else{break;}}}//創建大根堆public void  createhead(){//大根堆的節點數要大于子樹//第一步先確定有多少個樹,利用最后一個節點來找到父親節點for(int parent=(usedsize-1-1)/2;parent>=0;parent--){//采用向下調整siftDown1(parent,usedsize);}}//parent:代表調整子樹的起始位置//usedsize:判斷子樹是否還需要調整public void siftDown1(int parent,int usedsize){//根據父親節點找到左子樹節點int child=parent*2+1;while(child<usedsize){if(child+1<usedsize&&elem[child]<elem[child+1]){child++;}if(elem[child]>elem[parent]){int num=elem[parent];elem[parent]=elem[child];elem[child]=num;
//                elem[child]=elem[child]^elem[parent];
//                elem[parent]=elem[child]^elem[parent];
//                elem[child]=elem[child]^elem[child];parent=child;child=child*2+1;}else{break;}}}//向堆中增加元素public void push(int val) {//先進行判滿處理if (isFull()) {//進行擴容elem = Arrays.copyOf(elem, elem.length * 2);}elem[usedsize] = val;usedsize++;siftUp(usedsize - 1);}//向上調整public void siftUp(int child) {//孩子節點找到父親節點int parent=(child-1)/2;//向上調整while(parent>=0){if(elem[child]>elem[parent]){int num=elem[parent];elem[parent]=elem[child];elem[child]=num;child=parent;parent=(parent-1)/2;}else{break;}}}public boolean isFull(){if(usedsize==this.elem.length){return true;}return false;}//刪除堆的元素public int poll(){if(isEmpty()){return -1;}int val=elem[0];//交換0位置和最后一個節點位置elem[0]=elem[usedsize-1];elem[usedsize-1]=val;//對0節點位置進行向下調整siftDown1(0,usedsize-1);usedsize--;return val;}//判段是否為空public boolean isEmpty(){if (usedsize==0){return true;}return false;}//對節點進行排從小到大排序（再節點本身上排序）public void headsort(){//先對數據進行建大堆this.createhead();int end=usedsize-1;while(end>0){int num=elem[0];elem[0]=elem[end];elem[end]=num;siftDown1(0,end);end--;}}public static void main(String[] args) {}
}

Test類

public class Test {public static void main(String[] args) {//對隊進行初始化PriorityQueue priorityQueue=new PriorityQueue();int[] array={ 27,15,19,18,28,34,65,49,25,37 };priorityQueue.initelem(array);//測試建立小根堆priorityQueue.Smallrootpiles();priorityQueue.elempeek();System.out.println();//測試大根堆的實現priorityQueue.createhead();priorityQueue.elempeek();//測試插入一個元素priorityQueue.push(80);System.out.println();priorityQueue.elempeek();//測試刪除一個元素priorityQueue.poll();System.out.println();priorityQueue.elempeek();System.out.println();//測試堆排序priorityQueue.headsort();priorityQueue.elempeek();//}
}

3.4堆的問題

3.4.1topk問題

給你6個數據，求前3個最大數據。這時候我們用堆怎么做的？

解題思路：

1、如果求前K個最大的元素，要建一個小根堆。

2、如果求前K個最小的元素,要建一個大根堆。

3、第K大的元素。建一個小堆,堆頂元素就是第K大的元素。

4、第K小的元素。建一個大堆,堆頂元素就是第K大的元素。

3.4.2數組的排序

再者說如果要對一個數組進行從小到大排序，要借助大根堆還是小根堆呢？

---->大根堆

3.5PriorityQueue

使用注意：

1. 使用時必須導入PriorityQueue所在的包，即：

import java.util.PriorityQueue;

2. PriorityQueue中放置的元素必須要能夠比較大小，不能插入無法比較大小的對象，否則會拋出 ClassCastException異常

3. 不能插入null對象，否則會拋出NullPointerException

4. 沒有容量限制，可以插入任意多個元素，其內部可以自動擴容

5. 插入和刪除元素的時間復雜度為

6. PriorityQueue底層使用了堆數據結構

7. PriorityQueue默認情況下是小堆---即每次獲取到的元素都是最小的元素

1.優先級隊列的構造

static void TestPriorityQueue(){// 1.創建一個空的優先級隊列，底層默認容量是11PriorityQueue<Integer> q1 = new PriorityQueue<>();// 2.創建一個空的優先級隊列，底層的容量為initialCapacityPriorityQueue<Integer> q2 = new PriorityQueue<>(100);ArrayList<Integer> list = new ArrayList<>();list.add(4);list.add(3);list.add(2);list.add(1);// 用ArrayList對象來構造一個優先級隊列的對象// q3中已經包含了三個元素PriorityQueue<Integer> q3 = new PriorityQueue<>(list);System.out.println(q3.size());System.out.println(q3.peek());}//注意：默認情況下，PriorityQueue隊列是小堆，如果需要大堆需要用戶提供比較器// 用戶自己定義的比較器：直接實現Comparator接口，然后重寫該接口中的compare方法即可
class IntCmp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}}public class TestPriorityQueue {public static void main(String[] args) {PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());p.offer(4);p.offer(3);p.offer(2);p.offer(1);p.offer(5)

自定義排序規則

1.該改變升序降序

2.根據HashMap的value值對HashMap的鍵值對排序

方法摘要

 System.out.println(p.peek());}}static void TestPriorityQueue2(){int[] arr = {4,1,9,2,8,0,7,3,6,5};// 一般在創建優先級隊列對象時，如果知道元素個數，建議就直接將底層容量給好// 否則在插入時需要不多的擴容// 擴容機制：開辟更大的空間，拷貝元素，這樣效率會比較低PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);for (int e: arr) {q.offer(e);}System.out.println(q.size());   // 打印優先級隊列中有效元素個數System.out.println(q.peek());   // 獲取優先級最高的元素// 從優先級隊列中刪除兩個元素之和，再次獲取優先級最高的元素q.poll();q.poll();System.out.println(q.size());   // 打印優先級隊列中有效元素個數System.out.println(q.peek());   // 獲取優先級最高的元素q.offer(0);System.out.println(q.peek());   // 獲取優先級最高的元素// 將優先級隊列中的有效元素刪除掉，檢測其是否為空q.clear();if(q.isEmpty()){System.out.println("優先級隊列已經為空!!!")}else{System.out.println("優先級隊列不為空");}}