節點演算法
⑴ 完全二叉樹中葉子節點的演算法
noip中經常會遇到求完全二叉樹葉子結點的問題，比如第十一屆全國青少年信息學奧林匹克聯賽初賽試題的第四題：完全二叉樹的結點個數為4 *N+ 3 ，則它的葉結點個數為（）。
A. 2 *N B. 2 *N- 1 C. 2 *N+ 1 D. 2 *N- 2 E. 2 *N+ 2
結論：如果一棵具有n個結點的深度為k的完全二叉樹，其葉子結點數和總結點數有這樣的關系：n（葉子）＝（n總＋1）/2，由上所知，我們可以判斷這道題的 葉結點個數為（4 *N+ 3+1）/2=2 *N+ 2.
14(第十二屆)．高度為n的均衡的二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是高度為n-1的滿二叉樹。在這里，樹高等於葉結點的最大深度，根結點的深度為0，如果某個均衡的二叉樹共有2381個結點，則該樹的樹高為（）。
A. 10 B. 11 C. 12 D. 13
均衡二叉樹就是：任意兩個度不為2的節點的深度之差不大於1
例如：
1
/ \
2 3
\ /
4 5
是均衡二叉樹
而
1
/ \
2 3
\ / \
4 5 6
/
7
就不是，2和7的深度差2.
因為2^11 = 2048；所以一顆滿二叉樹從深度為0（根節點）到深度10的總節點數是2047，剩下2381-2047 = 334個節點，這剩下的節點的深度都是11。
所以答案為B
⑵ Dijkstra演算法
Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。注意該演算法要求圖中不存在負權邊。
設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。
（1）初始時，S只包含起點D；U包含除D外的其他頂點，且U中頂點的距離為「起點D到該頂點的距離」（例如，U中頂點A的距離為[D,A]的長度，然後D和A不相鄰，則A的距離為∞）
（2）從U中選出「距離最短的頂點K」，並將頂點K加入到S中；同時，從U中移除頂點K
（3）更新U中各個頂點到起點D的距離。之所以更新U中頂點的距離，是由於上一步中確定了K是求出最短路徑的頂點，從而可以利用K來更新其他頂點到起點D的距離（例如，[D,A]的距離可能大於[D,K]+[K,A]的距離）
（4）重復步驟（2）和（3），直到遍歷完所有頂點
https://blog.csdn.net/yalishadaa/article/details/55827681
⑶ 圖解迪傑斯特拉演算法(Dijkstra)
探索圖論瑰寶：迪傑斯特拉演算法詳解
讓我們深入解析Dijkstra演算法，這是一把探索加權圖中最短路徑的神奇鑰匙。旨在幫助你輕松理解，期待你的指正。
- 演算法目標: 在帶權重的圖中，尋找到起點至所有節點的捷徑之路。
- 原理精要
- 從起點出發，逐步揭示節點間的最短路徑，區分已知和未知節點，確保未知節點的路徑長度優於已知。
- 遵循遞推規則：按路徑長度升序排序，利用已知節點信息不斷推進。
- 關鍵步驟：每次迭代，都對未知節點進行路徑更新，直至找到終點。
- 實際應用: 以節點C為例，它與A、B相連，初始dist[C]1=4（A至C），dist[C]2=5（B至C）。
在演算法過程中，動態調整節點集合：mindist[C]更新為4，CL=C包含A(0)、B(2)和C(4)，DL初始為空。
第三次迭代，節點F、E加入游戲，dist[F]=6，dist[E]=5，mindist[E]保持，CL和DL相應調整...
...（每次迭代，都像漣漪擴散，不斷優化路徑，直到遍歷所有節點，揭示出F、E、D、G、H的最短路徑。）
最終成果：揭示了節點C、E、F、D、G的獨特路徑優勢。
進一步地，dist[I]2和dist[H]1同步更新為14，標志著關鍵節點的路徑變化：
CL擴展至A(0)、B(2)、C(4)、E(5)、F(6)、D(7)、G(8)、H(9)和I(9)，DL指向終點。
結論：Dijkstra演算法如漣漪擴散，揭示了H和I的最短路徑，最後，整個圖的最短路徑網路在終點處完成交融。
想像一下，就像一顆石子投入平靜的湖面，Dijkstra演算法逐步揭示出網路中每一個節點的最短路徑，直至波及整個圖的每一個角落。