JAVA遞歸實現線索化二叉樹

基礎理論

首先，二叉樹遞歸遍歷分為先序遍歷、中序遍歷和后序遍歷。

先序遍歷為：根節點+左子樹+右子樹

中序遍歷為：左子樹+根節點+右子樹

后序遍歷為：左子樹+右子樹+根節點

(只要記住根節點在哪里就是什么遍歷，且都是先左再右)

線索化

現在有這么一棵二叉樹，它的數據結構由左節點+權+右節點構成。

可以看到4,5,6,7這幾個節點的左右節點空間被浪費了。因此，線索化是指有效利用這些空間。

中序遍歷的順序為：4 2 5 1 6 3 7

現在引入前驅節點以及后繼節點。

前驅節點：線索化二叉樹時，一個節點的前一個節點

后繼節點：線索化二叉樹時，一個節點的后一個節點

(例如下圖：根據中序遍歷，5的前驅節點是2 , 5的后繼節點是1)

(中序遍歷)實現線索化二叉樹

定義數據結構ThreadedNode

//節點的權

int value;

//左兒子

ThreadedNode leftNode;

//右兒子

ThreadedNode rightNode;

//標識指針類型,其中0,1分別表示有無線索化，默認為0

int leftType;

int rightType;

中序遍歷

//中序遍歷

public void midShow() {

//左子節點

if(leftNode!=null) {

leftNode.midShow();

}

//當前節點

System.out.println(value);

//右子節點

if(rightNode!=null) {

rightNode.midShow();

}

}

這里使用遞歸的方式來實現。我們先把問題簡單化，只看紅圈的部分，如下圖

定義一個節點pre用來存儲當前節點，類似指針。

從根節點1開始遞歸，如果當前節點為空，返回，到4，此時4的前驅結點為null,結點5的前驅結點為2

遍歷到5的時候指向前驅結點2，前驅結點2為上一層遞歸的指針，因此指向它的前驅結點就行，再把左指針類型置為1

如果當前節點的前驅結點pre的右指針為null,則將它設置為當前節點，此時即4的后繼結點為2，并將右指針類型置為1

每處理一個節點，當前節點是下一個節點的前驅節點

線索化二叉樹ThreadedBinaryTree

//中序線索化二叉樹

public void threadNodes() {

threadNodes(root);

}

public void threadNodes(ThreadedNode node) {

//當前節點如果為null，直接返回

if(node==null) {

return;

}

//處理前驅節點

if(node.leftNode==null){

//讓當前節點的左指針指向前驅節點

node.leftNode=pre;

//改變當前節點左指針的類型

node.leftType=1;

}

//處理前驅的右指針，如果前驅節點的右指針是null(沒有指下右子樹)

if(pre!=null&&pre.rightNode==null) {

//讓前驅節點的右指針指向當前節點

pre.rightNode=node;

//改變前驅節點的右指針類型

pre.rightType=1;

}

//每處理一個節點，當前節點是下一個節點的前驅節點

pre=node;

}

現在再把上面這段代碼按照中序遍歷的方式放在中間,進行遞歸

//當前節點如果為null，直接返回

if(node==null) {

return;

}

//處理左子樹

threadNodes(node.leftNode);

//----------------------------------------------------------

//處理前驅節點

if(node.leftNode==null){

//讓當前節點的左指針指向前驅節點

node.leftNode=pre;

//改變當前節點左指針的類型

node.leftType=1;

}

//處理前驅的右指針，如果前驅節點的右指針是null(沒有指下右子樹)

if(pre!=null&&pre.rightNode==null) {

//讓前驅節點的右指針指向當前節點

pre.rightNode=node;

//改變前驅節點的右指針類型

pre.rightType=1;

}

//每處理一個節點，當前節點是下一個節點的前驅節點

pre=node;

//-----------------------------------------------------------

//處理右子樹

threadNodes(node.rightNode);

}

現在編寫測試方法

package demo7;

public class TestThreadedBinaryTree {

public static void main(String[] args) {

//創建一顆樹

ThreadedBinaryTree binTree = new ThreadedBinaryTree();

//創建一個根節點

ThreadedNode root = new ThreadedNode(1);

//把根節點賦給樹

binTree.setRoot(root);

//創建一個左節點

ThreadedNode rootL = new ThreadedNode(2);

//把新創建的節點設置為根節點的子節點

root.setLeftNode(rootL);

//創建一個右節點

ThreadedNode rootR = new ThreadedNode(3);

//把新創建的節點設置為根節點的子節點

root.setRightNode(rootR);

//為第二層的左節點創建兩個子節點

rootL.setLeftNode(new ThreadedNode(4));

ThreadedNode fiveNode = new ThreadedNode(5);

rootL.setRightNode(fiveNode);

//為第二層的右節點創建兩個子節點

rootR.setLeftNode(new ThreadedNode(6));

rootR.setRightNode(new ThreadedNode(7));

//中序遍歷樹

binTree.midShow();

System.out.println("===============");

//中前線索化二叉樹

binTree.threadNodes();

binTree.threadIterate();

}

}

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的java线索二叉树的实现_JAVA递归实现线索化二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

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