在我們描述堆之前，我們首先要明白一個概念，什么是樹？
樹的概念及結構
1.樹的概念
樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根在上，而葉在下的，
有一個特殊的結點，稱為根結點，根節點沒有前驅結點，除根節點外，其余結點被分成m(m > 0)個互不相交的集合T1、T2、…… 、Tm，其中每一個集合Ti(1 <= i <= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，但可以有0個或多個后繼，
由此可知，樹是遞回定義的，
下面介紹一些與樹相關的概念（以上面的樹為例）：
（1）結點的度：一個節點含有的子樹的個數稱為該節點的度；如上圖：A的為6，即B、C、D、E、F、G，
（2）葉結點：度為0的節點稱為葉結點；如上圖：B、C、H、I、K、L、M、N、P、Q 為葉結點，
（3）雙親結點或父結點：若一個節點含有子結點，則這個結點稱為其子結點的父結點；如上圖：A是B的父結點，
（4）孩子結點或子結點：一個結點含有的子樹的根結點稱為該結點的子結點；如上圖：B是A的孩子節點，
（5）兄弟結點：具有相同父結點的結點互稱為兄弟結點； 如上圖：B、C是兄弟結點，
（6）樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6，
（7）結點的層次：從根開始定義起，根為第1層，根的子結點為第2層，以此類推，
（8）樹的高度或深度：樹中結點的最大層次； 如上圖：樹的高度為4，
（9）節點的祖先：從根到某一結點所經分支上的所有結點；如上圖：D、A是H的祖先；A是所有結點的公共祖先，
（10）子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫，
（11）森林：多棵互不相交的樹的集合稱為森林，
2.樹的表示方法
樹由于不是線性結構，所以相對線性表，要存盤、表示就相對麻煩，實際中樹有很多種表示方式，如：雙親表示法，孩子表示法、孩子兄弟表示法等等，這里簡單地介紹其中最常用的孩子兄弟表示法，
孩子兄弟表示法就是用孩子結點來找到下一層的結點，用兄弟結點來找到這一層其余的結點，結構如下，
typedef int DataType; struct Node { struct Node* firstChild1; // 第一個孩子結點 struct Node* pNextBrother; // 指向其下一個兄弟結點 DataType data; // 結點中的資料域 };
二叉樹
1.二叉樹概念及結構
概念：一棵二叉樹是結點的一個有限集合，該集合為空，或者是由一個根節點加上兩棵稱為左子樹和右子樹的二叉樹組成，
二叉樹的特點：
（1）每個結點最多有兩棵子樹，即二叉樹不存在度大于2的結點，
（2）二叉樹的子樹有左右之分，其子樹的次序不能顛倒，
結構
特殊的二叉樹：
（1）滿二叉樹(Perfect Binary Tree)
每一層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，
也就是說，如果一個二叉樹的層數為K（根節點是第1層），且結點總數是(2^k) -1 ，則它就是滿二叉樹，也稱為完美二叉樹
（2）完全二叉樹(Complete Binary Tree)
完全二叉樹是由滿二叉樹而引出來的，對于深度為K的、有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 滿二叉樹是一種特殊的完全二叉樹，
完全二叉樹的葉子結點只能出現在最下層和次下層，且最下層的葉子結點從左到右連續；前K-1層是滿的二叉樹，
換句話說，完全二叉樹從根結點到倒數第二層滿足完美二叉樹，最后一層可以不完全填充，其葉子結點都靠左對齊，
（3）完滿二叉樹(Full Binary Tree)
換句話說，所有非葉子結點的度都是2，（只要你有孩子，你就必然是有兩個孩子，）
注：Full Binary Tree又叫做Strictly Binary Tree，
什么是堆？
堆（英語：heap)是計算機科學中一類特殊的資料結構的統稱，堆通常是一個可以被看做一棵樹的陣列物件，堆總是滿足下列性質：
-
堆中某個節點的值總是不大于或不小于其父節點的值；
-
堆總是一棵完全二叉樹，
將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，常見的堆有二叉堆、斐波那契堆等，
堆是非線性資料結構，相當于一維陣列，有兩個直接后繼，
堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當且僅當滿足下關系時，稱之為堆，
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
若將和此次序列對應的一維陣列（即以一維陣列作此序列的存盤結構）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大于（或不小于）其左、右孩子結點的值，由此，若序列{k1,k2,…,kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值），
注意： 在二叉樹中，若當前節點的下標為 i， 則其父節點的下標為 i/2，其左子節點的下標為 i*2，其右子節點的下標為i*2+1；
堆的插入：
每次插入都是將先將新資料放在陣列最后，由于從這個新資料的父結點到根結點必然為一個有序的序列，現在的任務是將這個新資料插入到這個有序序列中——這就類似于直接插入排序中將一個資料并入到有序區間中，
我們通過一個插入例子來看看插入操作的細節，我們將數字 16 插入到這個堆中：
堆的陣列是： [ 10, 7, 2, 5, 1 ]，
第一步是將新的元素插入到陣列的尾部，陣列變成：[ 10, 7, 2, 5, 1, 16 ]；
相應的樹變成了：
16 被添加最后一行的第一個空位，
不行的是，現在堆屬性不滿足，因為 2 在 16 的上面，我們需要將大的數字在上面（這是一個最大堆）
為了恢復堆屬性，我們需要交換 16 和 2，
現在還沒有完成，因為 10 也比 16 小，我們繼續交換我們的插入元素和它的父節點，直到它的父節點比它大或者我們到達樹的頂部，這就是所謂的 shift-up，每一次插入操作后都需要進行，它將一個太大或者太小的數字“浮起”到樹的頂部，
最后我們得到的堆：
現在每一個父節點都比它的子節點大，
堆的洗掉：
堆中每次都只能洗掉堆頂元素，為了便于重建堆，實際的操作是將最后一個資料的值賦給根結點，然后再從根結點開始進行一次從上向下的調整，調整時先在左右子結點中找最小的，如果父結點比這個最小的子結點還小說明不需要調整了，反之將父結點和它交換后再考慮后面的結點，相當于根結點資料的“下沉”程序，
我們將這個樹中的 (10) 洗掉：
現在頂部有一個空的節點，怎么處理？
當插入節點的時候，我們將新的值返給陣列的尾部，現在我們來做相反的事情：我們取出陣列中的最后一個元素，將它放到樹的頂部，然后再修復堆屬性，
現在來看怎么 shift-down (1)，為了保持最大堆的堆屬性，我們需要樹的頂部是最大的資料，現在有兩個數字可用于交換 7 和 2，我們選擇這兩者中的較大者稱為最大值放在樹的頂部，所以交換 7 和 1，現在樹變成了：
繼續堆化直到該節點沒有任何子節點或者它比兩個子節點都要大為止，對于我們的堆，我們只需要再有一次交換就恢復了堆屬性：
最大堆：
1.構造最大堆
原始資料為a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}，采用順序存盤方式，對應的完全二叉樹如下圖所示：
基本思想：
首先將每個葉子節點視為一個堆，再將每個葉子節點與其父節點一起構造成一個包含更多節點的對，所以，在構造堆的時候，首先需要找到最后一個節點的父節點，從這個節點開始構造最大堆；直到該節點前面所有分支節點都處理完畢，這樣最大堆就構造完畢了，
假設樹的節點個數為n，以1為下標開始編號，直到n結束，對于節點i，其父節點為i/2；左孩子節點為i*2，右孩子節點為i*2+1，最后一個節點的下標為n，其父節點的下標為n/2，
我們邊針對上邊陣列操作如下圖所示，最后一個節點為7，其父節點為16，從16這個節點開始構造最大堆；構造完畢之后，轉移到下一個父節點2，直到所有父節點都構造完畢，
代碼實作如下：
strcut MaxHeap { Etype *heap; //資料元素存放的空間，下標從1開始存數資料，下標為0的作為作業空間，存盤臨時資料 int HeapSize;//資料元素的個數 int MaxSize; //存放資料元素空間的大小 }; MaxHeap H; void MaxHeapInit (MaxHeap &H) { for(int i = H.HeapSize/2; i>=1; i--) { H.heap[0] = H.heap[i]; int son = i*2; while(son <= H.HeapSize) { if(son < H.HeapSize && H.heap[son] < H.heap[son+1]) son++; if(H.heap[0] >= H.heap[son]) break; else { H.heap[son/2] = H.heap[son]; son *= 2; } } H.heap[son/2] = H.heap[0]; } }
給定一個整形陣列a[]={16,7,3,20,17,8}，對其進行堆排序，
堆排序是借助堆來實作的選擇排序，思想同簡單的選擇排序，以下以大頂堆為例，注意：如果想升序排序就使用大頂堆，反之使用小頂堆，原因是堆頂元素需要交換到序列尾部，
首先，實作堆排序需要解決兩個問題：
1. 如何由一個無序序列鍵成一個堆？
2. 如何在輸出堆頂元素之后，調整剩余元素成為一個新的堆？
第一個問題，可以直接使用線性陣列來表示一個堆，由初始的無序序列建成一個堆就需要自底向上從第一個非葉元素開始挨個調整成一個堆，
第二個問題，怎么調整成堆？首先是將堆頂元素和最后一個元素交換，然后比較當前堆頂元素的左右孩子節點，因為除了當前的堆頂元素，左右孩子堆均滿足條件，這時需要選擇當前堆頂元素與左右孩子節點的較大者（大頂堆）交換，直至葉子節點，我們稱這個自堆頂自葉子的調整成為篩選，
從一個無序序列建堆的程序就是一個反復篩選的程序，若將此序列看成是一個完全二叉樹，則最后一個非終端節點是n/2取底個元素，由此篩選即可，舉個栗子：
49,38,65,97,76,13,27,49序列的堆排序建初始堆和調整的程序如下：
動圖演示:
（1）影片從一排數字開始
（2）先將一排數字放入陣列（這個陣列看做堆），顯然這個堆是不滿足條件的
（3）從最后一個父節點開始對堆進行調整（heapify）使其滿足堆的性質（綠色代表調整好了，淺藍色表示正在調整）
（4）堆構建結束后將堆頂元素與最后一個節點交換，將最大值放在最后（紅色元素），剩下的n-1個元素堆的性質被破壞，需要重新做一次heapify使前n-1個元素滿足堆的性質，從而回圈（4）這個程序實作堆排序
首先根據該陣列元素構建一個完全二叉樹，具體程序如下(從左到右，從上到下按順序一步一步的詳細程序)：
2.最大堆插入節點
最大堆的插入節點的思想就是先在堆的最后添加一個節點，然后沿著堆樹上升，跟最大堆的初始化程序大致相同，
void MaxHeapInsert (MaxHeap &H, EType &x)
{
if(H.HeapSize == H.MaxSize)
return false;
int i = ++H.HeapSize;
while(i!=1 && x>H.heap[i/2])
{
H.heap[i] = H.heap[i/2];
i = i/2;
}
H.heap[i] = x;
return true;
}
3.最大堆堆頂節點洗掉
最大堆堆頂節點洗掉思想如下：將堆樹的最后的節點提到根結點，然后洗掉最大值，然后再把新的根節點放到合適的位置，
void MaxHeapDelete (MaxHeap &H, EType &x)
{
if(H.HeapSize == 0)
return false;
x = H.heap[1];
H.heap[0] = H.heap[H.HeapSize--];
int i = 1, son = i*2;
while(son <= H.HeapSize)
{
if(son <= H.HeapSize && H.heap[0] < H.heap[son+1])
son++;
if(H.heap[0] >= H.heap[son])
break;
H.heap[i] = H.heap[son];
i = son;
son = son*2;
}
H.heap[i] = H.heap[0];
return true;
}
最小堆
整體操作和最大堆類似，這里不做贅述，
應用場景：
海量資料中找出前k大數（topk問題）
先拿10000個數建堆，然后依次添加剩余元素，如果大于堆頂的數（10000中最小的），將這個數替換堆頂，并調整結構使之仍然是一個最小堆，這樣，遍歷完后，堆中的10000個數就是所需的最大的10000個，建堆時間復雜度是O（mlogm），演算法的時間復雜度為O（nmlogm）（n為10億，m為10000），
優化的方法：可以把所有10億個資料分組存放，比如分別放在1000個檔案中，這樣處理就可以分別在每個檔案的10^6個資料中找出最大的10000個數，合并到一起在再找出最終的結果，
下面整理一下這方面的問題：
top K問題
在大規模資料處理中，經常會遇到的一類問題：在海量資料中找出出現頻率最好的前k個數，或者從海量資料中找出最大的前k個數，這類問題通常被稱為top K問題，例如，在搜索引擎中，統計搜索最熱門的10個查詢詞；在歌曲庫中統計下載最高的前10首歌等，
針對top K類問題，通常比較好的方案是分治+Trie樹/hash+小頂堆（就是上面提到的最小堆），即先將資料集按照Hash方法分解成多個小資料集，然后使用Trie樹活著Hash統計每個小資料集中的query詞頻，之后用小頂堆求出每個資料集中出現頻率最高的前K個數，最后在所有top K中求出最終的top K，
例如：有1億個浮點數，如果找出其中最大的10000個？
最容易想到的方法是將資料全部排序，然后在排序后的集合中進行查找，最快的排序演算法的時間復雜度一般為O（nlogn），如快速排序，但是在32位的機器上，每個float型別占4個位元組，1億個浮點數就要占用400MB的存盤空間，對于一些可用記憶體小于400M的計算機而言，很顯然是不能一次將全部資料讀入記憶體進行排序的，其實即使記憶體能夠滿足要求（我機器記憶體都是8GB），該方法也并不高效，因為題目的目的是尋找出最大的10000個數即可，而排序卻是將所有的元素都排序了，做了很多的無用功，
第二種方法為區域淘汰法，該方法與排序方法類似，用一個容器保存前10000個數，然后將剩余的所有數字——與容器內的最小數字相比，如果所有后續的元素都比容器內的10000個數還小，那么容器內這個10000個數就是最大10000個數，如果某一后續元素比容器內最小數字大，則刪掉容器內最小元素，并將該元素插入容器，最后遍歷完這1億個數，得到的結果容器中保存的數即為最終結果了，此時的時間復雜度為O（n+m^2），其中m為容器的大小，即10000，
第三種方法是分治法，將1億個資料分成100份，每份100萬個資料，找到每份資料中最大的10000個，最后在剩下的100*10000個資料里面找出最大的10000個，如果100萬資料選擇足夠理想，那么可以過濾掉1億資料里面99%的資料，100萬個資料里面查找最大的10000個資料的方法如下：用快速排序的方法，將資料分為2堆，如果大的那堆個數N大于10000個，繼續對大堆快速排序一次分成2堆，如果大的那堆個數N大于10000個，繼續對大堆快速排序一次分成2堆，如果大堆個數N小于10000個，就在小的那堆里面快速排序一次，找第10000-n大的數字；遞回以上程序，就可以找到第1w大的數，參考上面的找出第1w大數字，就可以類似的方法找到前10000大數字了，此種方法需要每次的記憶體空間為10^6*4=4MB，一共需要101次這樣的比較，
第四種方法是Hash法，如果這1億個書里面有很多重復的數，先通過Hash法，把這1億個數字去重復，這樣如果重復率很高的話，會減少很大的記憶體用量，從而縮小運算空間，然后通過分治法或最小堆法查找最大的10000個數，
第五種方法采用最小堆，首先讀入前10000個數來創建大小為10000的最小堆，建堆的時間復雜度為O（mlogm）（m為陣列的大小即為10000），然后遍歷后續的數字，并于堆頂（最小）數字進行比較，如果比最小的數小，則繼續讀取后續數字；如果比堆頂數字大，則替換堆頂元素并重新調整堆為最小堆，整個程序直至1億個數全部遍歷完為止，然后按照中序遍歷的方式輸出當前堆中的所有10000個數字，該演算法的時間復雜度為O（nmlogm），空間復雜度是10000（常數），
實際運行：
實際上，最優的解決方案應該是最符合實際設計需求的方案，在時間應用中，可能有足夠大的記憶體，那么直接將資料扔到記憶體中一次性處理即可，也可能機器有多個核，這樣可以采用多執行緒處理整個資料集，
下面針對不容的應用場景，分析了適合相應應用場景的解決方案，（1）單機+單核+足夠大記憶體
如果需要查找10億個查詢次（每個占8B）中出現頻率最高的10個，考慮到每個查詢詞占8B，則10億個查詢次所需的記憶體大約是10^9 * 8B=8GB記憶體，如果有這么大記憶體，直接在記憶體中對查詢次進行排序，順序遍歷找出10個出現頻率最大的即可，這種方法簡單快速，使用，然后，也可以先用HashMap求出每個詞出現的頻率，然后求出頻率最大的10個詞，
（2）單機+多核+足夠大記憶體
這時可以直接在記憶體總使用Hash方法將資料劃分成n個partition，每個partition交給一個執行緒處理，線程的處理邏輯同（1）類似，最后一個執行緒將結果歸并，
該方法存在一個瓶頸會明顯影響效率，即資料傾斜，每個執行緒的處理速度可能不同，快的執行緒需要等待慢的執行緒，最終的處理速度取決于慢的執行緒，而針對此問題，解決的方法是，將資料劃分成c×n個partition（c>1），
每個執行緒處理完當前partition后主動取下一個partition繼續處理，知道所有資料處理完畢，最后由一個執行緒進行歸并，（3）單機+單核+受限記憶體
這種情況下，需要將原資料檔案切割成一個一個小檔案，如次啊用hash(x)%M，將原檔案中的資料切割成M小檔案，如果小檔案仍大于記憶體大小，繼續采用Hash的方法對資料檔案進行分割，知道每個小檔案小于記憶體大小，這樣每個檔案可放到記憶體中處理，采用（1）的方法依次處理每個小檔案，
（4）多機+受限記憶體
這種情況，為了合理利用多臺機器的資源，可將資料分發到多臺機器上，每臺機器采用（3）中的策略解決本地的資料，可采用hash+socket方法進行資料分發，
從實際應用的角度考慮，（1）（2）（3）（4）方案并不可行，因為在大規模資料處理環境下，作業效率并不是首要考慮的問題，演算法的擴展性和容錯性才是首要考慮的，演算法應該具有良好的擴展性，以便資料量進一步加大（隨著業務的發展，資料量加大是必然的）時，在不修改演算法框架的前提下，可達到近似的線性比；演算法應該具有容錯性，即當前某個檔案處理失敗后，能自動將其交給另外一個執行緒繼續處理，而不是從頭開始處理，
top K問題很適合采用MapReduce框架解決，用戶只需撰寫一個Map函式和兩個Reduce 函式，然后提交到Hadoop（采用Mapchain和Reducechain）上即可解決該問題，具體而言，就是首先根據資料值或者把資料hash(MD5)后的值按照范圍劃分到不同的機器上，最好可以讓資料劃分后一次讀入記憶體，這樣不同的機器負責處理不同的數值范圍，實際上就是Map，得到結果后，各個機器只需拿出各自出現次數最多的前N個資料，然后匯總，選出所有的資料中出現次數最多的前N個資料，這實際上就是Reduce程序，對于Map函式，采用Hash演算法，將Hash值相同的資料交給同一個Reduce task；對于第一個Reduce函式，采用HashMap統計出每個詞出現的頻率，對于第二個Reduce 函式，統計所有Reduce task，輸出資料中的top K即可，
直接將資料均分到不同的機器上進行處理是無法得到正確的結果的，因為一個資料可能被均分到不同的機器上，而另一個則可能完全聚集到一個機器上，同時還可能存在具有相同數目的資料，
以下是一些經常被提及的該類問題，
（1）有10000000個記錄，這些查詢串的重復度比較高，如果除去重復后，不超過3000000個，一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門，請統計最熱門的10個查詢串，要求使用的記憶體不能超過1GB，
（2）有10個檔案，每個檔案1GB，每個檔案的每一行存放的都是用戶的query，每個檔案的query都可能重復，按照query的頻度排序，
（3）有一個1GB大小的檔案，里面的每一行是一個詞，詞的大小不超過16個位元組，記憶體限制大小是1MB，回傳頻數最高的100個詞，
（4）提取某日訪問網站次數最多的那個IP，
（5）10億個整數找出重復次數最多的100個整數，
（6）搜索的輸入資訊是一個字串，統計300萬條輸入資訊中最熱門的前10條，每次輸入的一個字串為不超過255B，記憶體使用只有1GB，
（7）有1000萬個身份證號以及他們對應的資料，身份證號可能重復，找出出現次數最多的身份證號，
重復問題
在海量資料中查找出重復出現的元素或者去除重復出現的元素也是常考的問題，針對此類問題，一般可以通過位圖法實作，例如，已知某個檔案內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數，
本題最好的解決方法是通過使用位圖法來實作，8位整數可以表示的最大十進制數值為99999999，如果每個數字對應于位圖中一個bit位，那么存盤8位整數大約需要99MB，因為1B=8bit，所以99Mbit折合成記憶體為99/8=12.375MB的記憶體，即可以只用12.375MB的記憶體表示所有的8位數電話號碼的內容，
遞回序：
value =https://www.cnblogs.com/741162830qq/archive/2022/12/20/=null ; return
node.left
node.right
1,2,4,4(left==null),4(right ==null),2,5,5(left==null),5(right ==null),2,1,3,6,6,6,3,7,7,7,3,1
先序（頭、左、右）第一次出現：1，2， 4，5，3，6，7
中序（左、頭、右）第二次出現：4，2，5，1，6，3，7
后序 （左、右、頭）第三次出現：4，5，2，6，7，3，1
任何遞回函式都可以改為非遞回函式，
class Node<V>{
V value;
Node left;
Node right;
}
先序遍歷：
先把頭節點放到堆疊里面，
1.每次在堆疊中彈出一個節點current
2.列印current
3.先壓右 再壓左，如果有的話，沒有什么都不做，
4.重復上面操作，
1節點 彈出，列印1 ，先壓3 再壓2，彈出2，列印2，先壓5，再壓4，彈出4 ，列印4，沒有什么都不做，彈出5.
public static void preOrderUnRecur(Node head){
System.out.println("pre-order:");
if(head != null){
Stack<Node> stack = new Stack<Node>();
stack.add(head);
while (!stack.isEmpty()){
head = stack.pop();
System.out.println(head.value+"");
if(head.right != null){
stack.push(head.right);
}
if(head.left != null){
stack.push(head.left);
}
}
}
System.out.println();
}
后序遍歷：
1.當前節點current 彈出
2.把當前節點放到收集堆疊
3.先壓左，再壓右，沒有左右直接走
4.周而復始
5.收集完之后，單獨列印收集堆疊里面的，
//后序遍歷
public static void posOrderUnRecur(Node head){
System.out.println("pos-order:");
if(head != null){
Stack<Node> stack = new Stack<Node>();
Stack<Node> newStack = new Stack<Node>();
stack.push(head);
while (!stack.isEmpty()){
head = stack.pop();
newStack.push(head);
System.out.println(head.value+"");
if(head.left!= null){
stack.push(head.left);
}
if(head.right!= null){
stack.push(head.right);
}
}
while (!newStack.isEmpty()){
System.out.println(newStack.pop().value +"");
}
}
System.out.println();
}
中序遍歷：
先左，再頭，再右
每棵子樹 ，整棵樹左邊界進堆疊，依次彈出的程序中，列印，對彈出節點的右樹重復，
4，2，5，1，6，3，7
1，2，4 進堆疊，每一次彈一個節點，4彈出，列印4 ，4 沒有右樹，彈出2，列印，2有右樹5，5 進堆疊，5 彈出，列印5 ，5沒有右樹，彈出1，列印1，1有右樹3，3，6 進堆疊，
彈出6，列印6 ，6沒有右樹，彈出3，列印3，3有右樹7，彈出7 列印7， 7無右樹，整個堆疊彈空，
//中序遍歷
public static void inOrderUnRecur(Node head){
System.out.println("in-order:");
if(head != null){
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head); //左邊界進堆疊
head = head.left;//左邊界全壓
} else {
head = stack.pop();//沒有左邊界，彈出節點
System.out.println(head.value + "");
head = head.right;//移動到右 壓右
}
}
}
System.out.println();
}
二叉樹的先序遍歷，就是深度遍歷，
寬度遍歷用佇列，先進先出，
先左 后右，
public static void wide(Node head){
if (head ==null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while (!queue.isEmpty()){
Node cur = queue.poll();
System.out.println(cur.value);
if(cur.left !=null){
queue.add(cur.left);
}
if(cur.right !=null){
queue.add(cur.right);
}
}
}
求一棵二叉樹的最大寬度：
public static int maxWidth(Node head){
if (head ==null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
HashMap<Node,Integer> levelMap = new HashMap<>();
levelMap.put(head,1);
int curLevel = 1;
int curLevelNodes = 0;
int max = Integer.MIN_VALUE;
while (!queue.isEmpty()){
Node cur = queue.poll();
int curNodeLevel = levelMap.get(cur);
if(curNodeLevel == curLevel){
curLevelNodes++;
}else{
max = Math.max(max,curLevelNodes);
curLevel++;
curLevelNodes = 1;
}
// System.out.println(cur.value);
if(cur.left !=null){
levelMap.put(cur.left,curNodeLevel+1);
queue.add(cur.left);
}
if(cur.right !=null){
levelMap.put(cur.right,curNodeLevel+1);
queue.add(cur.right);
}
}
return max;
}
如果錯過了一天，那么真的就錯過一天，不拋棄，不放棄，點一盞心燈給自己，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/540357.html
標籤：其他