算法第四版習題2.4.24： 用堆有序的二叉樹實現一個優先隊列，但使用鏈表結構，每個結點需要三個鏈接：兩個向下，一個向上。要求算法基本操作所需時間為對數級。
二叉樹如圖：

此算法實現的主要步驟：
1.將新元素插入到最末結點之后，并上浮到合適位置
2. 從二叉樹頂端刪除最大元素，并將最末結點放到頂端，并下沉頂結點。
此算法的難點在于如何定位最末結點向后一位的結點

一、沈星繁博客中提出的解決辦法

維護一個指向最末結點的指針，通過向上回溯來找下一位結點，如圖：

具體步驟為：
1.向上回溯一層，判斷回溯方向：若為自左路回溯，則右路為后一位結點；若為右路回溯，轉為第2步。
2.繼續向上回溯，直到回溯方向為左路，然向向右下一層，再沿左路下到底。
3.若向上回溯一直為右路，則會回到頂結點，自頂結點一路向左下到底即可。
此算法邏輯較復雜，而且還要判斷回溯方向。具體實現代碼可參見下面鏈接: 沈星繁-算法2.4.

二、我的巧妙算法：

查找某序號結節位置（序號從1開始，自上而下自左到右順序編號），對于二叉樹來說，結點數為N，其下一位就是序號N+1的結點位置。具體查找方法如下：
1.先將序號轉為二進制數。
2.此二進制數的位數代表二叉樹的層數。自左向右分別為頂結點-2層結點-3層結點-4層結點。除第1位頂結點外，其余每位0代表左結點，1代表右結點。
比如要定位10號結點，先轉為二進制為“1010”，定位順序為：頂結點->左->右->左
此算法遍歷的結節數為樹的層數，正好為lgN對數級。
代碼如下：

public Node seekNode(int x) {String s = Integer.toBinaryString(x);Node seek = top; for(int i =1; i<s.length(); i++) {if(s.charAt(i)=='0') seek = seek.left;else seek = seek.right;}return seek;}

邏輯清晰，簡單高效！

總結

以上是生活随笔為你收集整理的算法2.4.24：查找链表二叉树节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。