Java二叉樹的四種遍歷方式詳解
二叉樹的四種遍歷方式：
- 二叉樹的遍歷（traversing binary tree）是指從根結點出發(fā)，按照某種次序依次訪問二叉樹中所有的結點，使得每個結點被訪問依次且僅被訪問一次。
四種遍歷方式分別為：先序遍歷、中序遍歷、后序遍歷、層序遍歷。
遍歷之前，我們首先介紹一下，如何創(chuàng)建一個二叉樹，在這里用的是先建左樹在建右樹的方法，
首先要聲明結點TreeNode類，代碼如下：
public class TreeNode {
public int data;
public TreeNode leftChild;
public TreeNode rightChild;
public TreeNode(int data){
this.data = data;
}
}
再來創(chuàng)建一顆二叉樹：
/**
* 構建二叉樹
* @param list 輸入序列
* @return
*/
public static TreeNode createBinaryTree(LinkedList<Integer> list){
TreeNode node = null;
if(list == null || list.isEmpty()){
return null;
}
Integer data = list.removeFirst();
if(data!=null){
node = new TreeNode(data);
node.leftChild = createBinaryTree(list);
node.rightChild = createBinaryTree(list);
}
return node;
}
接下來按照上面列的順序一一講解，
首先來看前序遍歷，所謂的前序遍歷就是先訪問根節(jié)點，再訪問左節(jié)點，最后訪問右節(jié)點，
如上圖所示，前序遍歷結果為：
ABDFECGHI
實現代碼如下：
/**
* 二叉樹前序遍歷 根-> 左-> 右
* @param node 二叉樹節(jié)點
*/
public static void preOrderTraveral(TreeNode node){
if(node == null){
return;
}
System.out.print(node.data+" ");
preOrderTraveral(node.leftChild);
preOrderTraveral(node.rightChild);
}
再者就是中序遍歷，所謂的中序遍歷就是先訪問左節(jié)點，再訪問根節(jié)點，最后訪問右節(jié)點，
如上圖所示，中序遍歷結果為：
DBEFAGHCI
實現代碼如下：
/**
* 二叉樹中序遍歷 左-> 根-> 右
* @param node 二叉樹節(jié)點
*/
public static void inOrderTraveral(TreeNode node){
if(node == null){
return;
}
inOrderTraveral(node.leftChild);
System.out.print(node.data+" ");
inOrderTraveral(node.rightChild);
}
最后就是后序遍歷，所謂的后序遍歷就是先訪問左節(jié)點，再訪問右節(jié)點，最后訪問根節(jié)點。
如上圖所示，后序遍歷結果為：
DEFBHGICA
實現代碼如下：
/**
* 二叉樹后序遍歷 左-> 右-> 根
* @param node 二叉樹節(jié)點
*/
public static void postOrderTraveral(TreeNode node){
if(node == null){
return;
}
postOrderTraveral(node.leftChild);
postOrderTraveral(node.rightChild);
System.out.print(node.data+" ");
}
講完上面三種遞歸的方法，下面再給大家講講非遞歸是如何實現前中后序遍歷的
還是一樣，先看非遞歸前序遍歷
1.首先申請一個新的棧，記為stack；
2.聲明一個結點treeNode，讓其指向node結點；
3.如果treeNode的不為空，將treeNode的值打印，并將treeNode入棧，然后讓treeNode指向treeNode的右結點，
4.重復步驟3，直到treenode為空；
5.然后出棧，讓treeNode指向treeNode的右孩子
6.重復步驟3，直到stack為空.
實現代碼如下：
public static void preOrderTraveralWithStack(TreeNode node){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = node;
while(treeNode!=null || !stack.isEmpty()){
//迭代訪問節(jié)點的左孩子，并入棧
while(treeNode != null){
System.out.print(treeNode.data+" ");
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
//如果節(jié)點沒有左孩子，則彈出棧頂節(jié)點，訪問節(jié)點右孩子
if(!stack.isEmpty()){
treeNode = stack.pop();
treeNode = treeNode.rightChild;
}
}
}
中序遍歷非遞歸，在此不過多敘述具體步驟了，
具體過程：
1.申請一個新棧，記為stack，申請一個變量cur，初始時令treeNode為頭節(jié)點；
2.先把treeNode節(jié)點壓入棧中，對以treeNode節(jié)點為頭的整棵子樹來說，依次把整棵樹的左子樹壓入棧中，即不斷令treeNode=treeNode.leftChild，然后重復步驟2；
3.不斷重復步驟2，直到發(fā)現cur為空，此時從stack中彈出一個節(jié)點記為treeNode，打印node的值，并讓treeNode= treeNode.right，然后繼續(xù)重復步驟2；
4.當stack為空并且cur為空時結束。
public static void inOrderTraveralWithStack(TreeNode node){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = node;
while(treeNode!=null || !stack.isEmpty()){
while(treeNode != null){
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
if(!stack.isEmpty()){
treeNode = stack.pop();
System.out.print(treeNode.data+" ");
treeNode = treeNode.rightChild;
}
}
}
后序遍歷非遞歸實現，后序遍歷這里較前兩者實現復雜一點，我們需要一個標記位來記憶我們此時節(jié)點上一個節(jié)點，具體看代碼注釋
public static void postOrderTraveralWithStack(TreeNode node){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = node;
TreeNode lastVisit = null; //標記每次遍歷最后一次訪問的節(jié)點
while(treeNode!=null || !stack.isEmpty()){//節(jié)點不為空，結點入棧，并且指向下一個左孩子
while(treeNode!=null){
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
//棧不為空
if(!stack.isEmpty()){
//出棧
treeNode = stack.pop();
/**
* 這塊就是判斷treeNode是否有右孩子，
* 如果沒有輸出treeNode.data，讓lastVisit指向treeNode，并讓treeNode為空
* 如果有右孩子，將當前節(jié)點繼續(xù)入棧，treeNode指向它的右孩子,繼續(xù)重復循環(huán)
*/
if(treeNode.rightChild == null || treeNode.rightChild == lastVisit) {
System.out.print(treeNode.data + " ");
lastVisit = treeNode;
treeNode = null;
}else{
stack.push(treeNode);
treeNode = treeNode.rightChild;
}
}
}
}
最后再給大家介紹一下層序遍歷
具體步驟如下：
1.首先申請一個新的隊列，記為queue；
2.將頭結點head壓入queue中；
3.每次從queue中出隊，記為node，然后打印node值，如果node左孩子不為空，則將左孩子入隊；如果node的右孩子不為空，則將右孩子入隊；
4.重復步驟3，直到queue為空。
實現代碼如下：
public static void levelOrder(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
root = queue.pop();
System.out.print(root.data+" ");
if(root.leftChild!=null) queue.add(root.leftChild);
if(root.rightChild!=null) queue.add(root.rightChild);
}
}
總結
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關注腳本之家的更多內容！
相關文章
String類代表字符串，java程序中的所有字符串文字（例如"abc"）都被實現為此類的實例。本文將詳解String類的使用，以及如何進行字符串比較2022-08-08
以前做項目，總是寫Ant配置文件，滿足于自己更靈活的配置，而沒有去思考，這么做到底值不值得2017-08-08
SpringCloud Eureka實現服務注冊與發(fā)現
Eureka是一種基于REST(具像狀態(tài)傳輸)的服務，主要用于AWS云中定位服務，以實現中間層服務器的負載平衡和故障轉移。本文記錄一個簡單的服務注冊與發(fā)現實例。感興趣的小伙伴們可以參考一下2019-01-01
JAR文件就是Java 檔案文件Java Archive，它是 Java 的一種文檔格式，這篇文章主要介紹了Java中Jar包反編譯解壓和壓縮,需要的朋友可以參考下2023-09-09
Java循環(huán)創(chuàng)建對象內存溢出的解決方法
在Java中,如果在循環(huán)中不當地創(chuàng)建大量對象而不及時釋放內存,很容易導致內存溢出（OutOfMemoryError）,所以本文給大家介紹了Java循環(huán)創(chuàng)建對象內存溢出的解決方法,需要的朋友可以參考下2025-01-01
最近項目需求，準備從Spring Boot 2.x升級到3.x，升級后發(fā)現編譯器報了一堆錯誤，本文主要介紹了Spring?Boot?2.x升3.x的那些事，具有一定的參考價值，感興趣的可以了解一下2024-01-01
跟著思路走，之后從簡單題入手，反復去看，做過之后可能會忘記，之后再做一次，記不住就反復做，反復尋求思路和規(guī)律，慢慢積累就會發(fā)現質的變化2022-03-03
SpringBoot整合SpringSecurity認證與授權
在項目開發(fā)中,權限認證是很重要的,尤其是一些管理類的系統(tǒng),對于權限要求更為嚴格,本文主要介紹了SpringBoot整合SpringSecurity認證與授權,感興趣的可以了解一下2023-11-11
這篇文章主要介紹了Mybatis plus中使用in查詢出錯的問題及解決方法，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-08-08
詳解tryAcquire()、addWaiter()、acquireQueued()
這篇文章主要tryAcquire()、addWaiter()、acquireQueued()的用法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-03-03