public void threadedPreNodes(HeroNode node) {
// 如果node==null,退出
if (node == null) {
return;
}
// 處理當前結點的前驅節點
if (node.getLeft() == null) {
// 讓當前結點的左指標指向前驅節點
node.setLeft(pre);
// 修改當前節點的左指標型別
node.setLeftType(1); // 當前左指標指向前驅節點
}
// 處理后繼節點
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
// 每處理一個節點后，pre要跟著node走
pre = node;
// 線索化左子樹
if (node.getLeftType() != 1) {
threadedPreNodes(node.getLeft());
}
// 線索化右子樹
if (node.getRightType() != 1) { //為什么這個if不能去掉呢？
threadedPreNodes(node.getRight());
}
}最近資料結構學到了線索樹，如上是撰寫的一個前序線索樹方法。
如上27行的if判斷為什么不能去除呢？我從紙上畫了好幾次邏輯感覺去掉也沒有什么問題，右節點的連接作業是交給下一個元素負責的，即當處在這個元素時，右節點為空，講道理進入了遞回也會由第3行的if退出，但是運行的時候若去掉似乎就無法退出遞回。
不勝感激！！！！這個問題卡得我太難受了！謝謝！！！！！
uj5u.com熱心網友回復：
當線索化了之后 原來的節點會添加 前驅 和后繼啊 if (node.getLeft() == null) {
// 讓當前結點的左指標指向前驅節點
node.setLeft(pre);//之前沒有 現在就有了 導致 你下面不判斷type!=1 就一直不是null
// 修改當前節點的左指標型別
node.setLeftType(1); // 當前左指標指向前驅節點
}所以你的第3行的if永遠也退不了
uj5u.com熱心網友回復：
左子樹我知道設定后會有影響，所以要判斷。
我的問題在于右子樹為什么也需要if進行判斷呢？當線索化的時候右邊的連接是當node到下一個節點時才進行的，換言之當node在當前這個節點時右邊是空，遞回為什么不會執行第三行的if呢？
uj5u.com熱心網友回復：
是當時確實是右邊沒有節點但是當呼叫了方法之后 線索化左子樹 (遞回調自己)之后 你當前的node 就成了 pre了
只要
這個方法一進去 不就給pre 設定了右節點了 (相當于外面的node有了一個右節點) 出去之后 node. getRight() 就不是null了 就一直線索化出不來
只要左節點有值 并 滿足 就添加節點
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
uj5u.com熱心網友回復：
// 線索化左子樹
if (node.getLeftType() != 1) {
threadedPreNodes(node.getLeft());
}
// 線索化右子樹
threadedPreNodes(node.getRight());
我的意思是這樣寫為什么不行，左子樹的if陳述句是可以過濾掉你說的那種情況的，此時為線索化的右子樹遞回進入后總該是null了吧。
uj5u.com熱心網友回復：
你只有一個節點嗎？ 如果只有一個那么沒有問題 是null 沒事情可是如果有兩個 A 和 A的 左 B 來說吧 node A pre null
A 進去 前三個if不進 pre=A 直接去了線索化左子樹方法中
B 進去 綁前驅節點 B left為 A 在綁后繼節點 A right 為B 再讓 pre為B//注意此時就已經有了 right 節點了
判斷node.getLeftType() != 1 為1 false 不去 索化左子樹
線索化右子去了 當前node為B B.right為空出堆疊
到A了 A有right節點 不會跳出 因為你沒有判斷 node.getRightType() != 1 是否已經線索化
uj5u.com熱心網友回復：
你要是實在不清楚 可以debug 看一下 你就知道為什么了uj5u.com熱心網友回復：
哦~我明白了，謝謝你，超級謝謝你
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/37891.html
標籤：Eclipse