生活随笔
收集整理的這篇文章主要介紹了
数据结构与算法--二叉树第k个大的节点
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
二叉樹第k個大的節點
數據結構與算法–面試必問AVL樹原理及實現
數據結構與算法–二叉樹的深度問題
數據結構與算法–二叉堆（最大堆，最小堆）實現及原理
數據結構與算法–二叉查找樹轉順序排列雙向鏈表
數據結構與算法-- 二叉樹中和為某一值的路徑
數據結構與算法-- 二叉樹后續遍歷序列校驗
數據結構與算法-- 廣度優先打印二叉樹
數據結構與算法–解決問題的方法- 二叉樹的的鏡像
數據結構與算法–重建二叉樹
數據結構與算法–二叉查找樹實現原理
數據結構與算法–二叉樹實現原理
數據結構與算法–B樹原理及實現
數據結構與算法–數字在排序數組中出現次數
數據結構與算法–死磕二叉樹
數據結構與算法–二叉樹第k個大的節點
數據結構與算法–求1~n能組成的所有二叉搜索樹的排列
- 之前遇到過多個類型的題型但是都是針對數組這種數據結構，如果兩篇：
數據結構與算法–最小的k個數
數據結構與算法–查找與排序另類用法-旋轉數組中的最小數字
- 其中最小k個數我們用二分法的思路，很快得出解，還有就是用二叉堆的特性求解
- 在旋轉數組中查找最小值，直接二分查找完成
- 由上可見，二分法在數組中查找第k個大小的數還是很好用的。但是我們此處針對的是二叉排序樹，二分法可能排不上用處
方法一統計節點法
-
利用二叉排序數的特性，左節點 比 根小， 右節點比根大，那么需要找第 k 大的,直接統計左右節點個數
- 如果右邊節點個數 rightCount > k，那么第k 大的必然在右節點
- 如果右節點個數 rightCount < k，那么有兩種情況：
- 當rightCount < k， 并且rightCount - k = 1 此時，最大的就是當前根節點
- 如果rightCount < k，并且rigntCount- k > 1 此時，那么第 k 大的節點就是左節點的 k - rightCount - 1 個大的節點
-
我們依次篩選左右節點，直到找到k 的具體節點，或者父節點，將k范圍縮小到1或 0
-
當k = 1 ，就是最右節點，當k = 0 就是最左節點。我們用如下圖實例
-
情況一：正好是root節點情況
-
情況二：在left節點中
-
情況三，在right節點中
-
經如上分析有如下代碼：
public class FinMaxKNumberInBinary {public static void main(String
[] args
) {BinaryNode node
= new BinaryNode(null
, null
, null
);BinarySearchTree searchTree
= new BinarySearchTree();Random random
= new Random();for (int i
= 0; i
< 5; i
++) {node
= searchTree
.insert(random
.nextInt(100), node
);}searchTree
.printTree(node
);System
.out
.println();System
.out
.println(getMaxKNumber(node
, 4).getElement());}public static BinaryNode
getMaxKNumber(BinaryNode binaryNode
, Integer k
) {if (binaryNode
== null
|| k
< 0) {return null
;}if (k
== 1) {BinaryNode right
= binaryNode
;while (right
.getRight() != null
) {right
= right
.getRight();}return right
;}if (k
== 0) {BinaryNode left
= binaryNode
;while (left
.getLeft() != null
) {left
= left
.getLeft();}return left
;}BinaryNode baseCount
= new BinaryNode(null
, null
, null
);baseCount
.setCount(0);int rightCount
= countNode(binaryNode
.getRight(), baseCount
).getCount();if (rightCount
>= k
) {return getMaxKNumber(binaryNode
.getRight(), k
);}if (k
- rightCount
== 1) {return binaryNode
;}if (k
- rightCount
> 1) {return getMaxKNumber(binaryNode
.getLeft(), k
- rightCount
- 1);}return null
;}public static BinaryNode
countNode(BinaryNode binaryNode
, BinaryNode baseCount
) {if (binaryNode
== null
) {return baseCount
;}baseCount
.setCount(baseCount
.getCount() + 1);countNode(binaryNode
.getLeft(), baseCount
);countNode(binaryNode
.getRight(), baseCount
);return baseCount
;}
}
- 以上實現方案中通過遞歸不斷將 第 k大的節點范圍縮小，在最后的2個節點中找出我們的值，問題在于，存在太多重復的遍歷，如上情況三種：
- 當遍歷右子樹 C的時候其實已經遍歷過 G，F
- 但是在之后的步驟中還依然需要遍歷G， F繼續縮小范圍，因此時間效率很低
方法二逆中序遍歷
- 還是利用二叉搜索樹的特性，我們需要找最大的第 k位置，但是在二叉樹三種遍歷方式中，前序，中序，后續遍歷，只有中序遍歷是按順序排列二叉搜索樹的所有節點，但是是小到大的順序
- 由此我們得到啟發：
- 我們利用中序遍歷，求第k個大的，也就是從小到大排列的第 s - k+ 1 個數據，但是此時我們并不知道二叉樹的總節點，無法得出這個值
- 如果我們反過來遍歷，中序遍歷是 左，中，右， 我們換成 右，根，左，那么直接求第k個位置的遍歷到的節點就得到我們的解
- 因此最簡單的遍歷查找方式如下
public class FinMaxKNumberInBinary {public static void main(String
[] args
) {BinaryNode node
= new BinaryNode(null
, null
, null
);BinarySearchTree searchTree
= new BinarySearchTree();Random random
= new Random();for (int i
= 0; i
< 5; i
++) {node
= searchTree
.insert(random
.nextInt(100), node
);}searchTree
.printTree(node
);System
.out
.println();System
.out
.println(getMaxKNumber(node
, 4).getElement());System
.out
.println(getMaxKNumberOver(node
, 4).getElement());}public static BinaryNode
getMaxKNumberOver(BinaryNode binaryNode
, Integer k
) {if (binaryNode
== null
|| k
< 0) {return null
;}BinaryNode baseCount
= new BinaryNode(null
, null
, null
);baseCount
.setCount(0);return printOver(binaryNode
, baseCount
, k
);}public static BinaryNode
printOver(BinaryNode node
, BinaryNode baseCount
, Integer k
) {if(node
== null
){return baseCount
;}baseCount
= printOver(node
.getRight(), baseCount
, k
);baseCount
.setCount(baseCount
.getCount() + 1);if(baseCount
.getCount() == k
){baseCount
= node
;baseCount
.setCount(k
);return baseCount
;}return printOver(node
.getLeft(), baseCount
, k
);}
}
上一篇：數據結構與算法–再來聊聊數組
下一篇：數據結構與算法–求1~n能組成的所有二叉搜索樹的排列
總結
以上是生活随笔為你收集整理的数据结构与算法--二叉树第k个大的节点的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
