二叉樹的四種遍歷 以及代碼實現(xiàn),看這一篇就夠了
點擊上方藍色字體，選擇“標星公眾號”
優(yōu)質文章，第一時間送達
★ 前言：
二叉樹的遍歷，是我們數(shù)據(jù)結構?重點中的重點?，90% 的筆試題都是二叉樹遍歷的變形
但是呢，有很多小伙伴對它的遍歷方式還是有些模糊
那么，接下來我就為大家詳細介紹各種遍歷方式的區(qū)別：
何為 遍歷 ：?
就是把二叉樹中的每個結點，一個不落的都走一遍。。
我們先封裝一個 二叉樹 的對象類：
public?class?TreeNode?{
????int?v;
????TreeNode?left;?//?左子樹
????TreeNode?right;?//?右子樹
????public?TreeNode(int?v)?{
????????this.v?=?v;
????}
????@Override
????public?String?toString()?{
????????return?String.format("%c",v);
????}
}
1、DFS（Depth First Search）：深度優(yōu)先遍歷 – 棧
第一種視角看三種遍歷：
（1）前序遍歷：
遍歷順序：（遞歸）
把根結點放前面處理：
1、首先，處理 根結點
2、接著，完整地遍歷根的 左子樹（采用先序）
3、最后，完整地遍歷根的 右子樹（采用先序）
具體實現(xiàn)：根 { 左子樹 } { 右子樹 }
① 我們是從 根結點 開始，
即 ：A{ } { }
② 由于我們是先遍歷 左子樹
所以， A { B{}{} } { }
A { B{ D{}{} }{} } { }
A { B{ D{}{G} }{} } { }
③ 最后遍歷 右子樹：
A { B{ D{}{G} }{} } { C{}{} }
A { B{ D{}{G} }{} } { C{E}{} }
A { B{ D{}{G} }{} } { C{E}{ F{}{} } }
A { B{ D{}{G} }{} } { C{E}{ F{H}{} } }
這樣我們就得出了我們先序遍歷出來的結果：
A B D G C E F H
① 代碼實現(xiàn)：（遞歸）
//?前序遍歷
????public?static?void?preTraversal(TreeNode?root)?{
????????//?前提：這顆樹不是空樹（根結點存在）
????????if?(root?!=?null)?{
????????????//?1、首先處理根結點
????????????System.out.printf("%c",root.v);
????????????//?2、按照前序的方式，遞歸處理該結點的左子樹
????????????preTraversal(root.left);
????????????//?3、按照前序的方式，遞歸處理該結點的右子樹
????????????preTraversal(root.right);
????????}?
????}
② 代碼實現(xiàn)：（非遞歸）
????public?static?void?preOrder(TreeNode?root)?{
????????Deque<TreeNode>?stack?=?new?LinkedList<>();
????????TreeNode?cur?=?root;
????????while?(!stack.isEmpty()?||?cur?!=?null)?{
????????????//遍歷左子樹
????????????while?(cur?!=?null)?{
????????????????System.out.println(cur.v);
????????????????stack.push(cur);
????????????????cur?=?cur.left;
????????????}
????????????//取出棧頂元素
????????????TreeNode?top?=?stack.pop();
????????????//遍歷右子樹
????????????cur?=?top.right;
????????}
????}
（2）中序遍歷：
遍歷順序：（遞歸）
1、先遍歷整顆樹的 左子樹（采用中序）
2、中間再處理 根結點 （根放到中間處理）
3、再遍歷整棵樹的 右子樹 （采用中序）
具體實現(xiàn)：{ 左子樹 } 根 { 右子樹 }
即：{ } A { }
我們先來遍歷 左子樹， 遍歷的方式采用 中序遍歷
{ {}B{} } A { }
{ { {}D{} }B{} } A { }
{ { {}D{G} }B{} } A { }
我們再來遍歷 右子樹，遍歷的方式仍然采用 中序遍歷
{ { {}D{G} }B{} } A { {}C{} }
{ { {}D{G} }B{} } A { {E}C{} }
{ { {}D{G} }B{} } A { {E}C{ {}F{} } }
{ { {}D{G} }B{} } A { {E}C{ {H}F{} } }
這樣我們就得出了我們 中序遍歷 出來的結果：
D G B A E C H F
① 代碼實現(xiàn)：（遞歸）
//?中序遍歷
????public?static?void?inTraversal(TreeNode?root)?{
????????if?(root?!=?null)?{
????????????//?1、中序遍歷左子樹
????????????inTraversal(root.left);
????????????//?2、處理根
????????????System.out.printf("%c",root.v);
????????????//?3、中序遍歷右子樹
????????????inTraversal(root.right);
????????}
????}
② 代碼實現(xiàn)：（非遞歸）
public?static?void?inOrder(TreeNode?root)?{
????????Deque<TreeNode>?stack?=?new?LinkedList<>();
????????TreeNode?cur?=?root;
????????while?(!stack.isEmpty()?||?cur?!=?null)?{
????????????//遍歷左子樹
????????????while?(cur?!=?null)?{
????????????????stack.push(cur);
????????????????cur?=?cur.left;
????????????}
????????????//取出棧頂元素
????????????TreeNode?top?=?stack.pop();
????????????//回來的時候打印他
????????????System.out.println(top.v);
????????????//遍歷右子樹
????????????cur?=?top.right;
????????}
????}
（3）后序遍歷：
遍歷順序：（遞歸）
1、先遍歷整顆樹的 左子樹（采用后序）
2、再遍歷整棵樹的 右子樹 （采用后序）
3、最后再處理 根結點 （根放到最后處理）
具體實現(xiàn)：{ 左子樹 } { 右子樹 } 根
即：{ } { } A
我們先來遍歷 左子樹， 遍歷的方式采用 后序遍歷：
{ {}{}B } { }A
{ { {}{}D }{}B } { }A
{ { {}{G}D }{}B } { }A
我們再來遍歷 右子樹，遍歷的方式仍然采用 后序遍歷
{ { {}{G}D }{}B } { }A
{ { {}{G}D }{}B } { {}{}C }A
{ { {}{G}D }{}B } { {E}{}C }A
{ { {}{G}D }{}B } { {E}{ {}{}F }C }A
{ { {}{G}D }{}B } { {E}{ {H}F}{}C }A
這樣我們就得出了我們 后序遍歷 出來的結果：
G D B E H F C A
① 代碼實現(xiàn)：（遞歸）
//?后序遍歷
????public?static?void?postTraversal(TreeNode?root)?{
????????if?(root?!=?null)?{
????????????//?1、后續(xù)遍歷左子樹
????????????postTraversal(root.left);
????????????//?2、后續(xù)遍歷右子樹
????????????postTraversal(root.right);
????????????//?3、處理根
????????????System.out.printf("%c",root.v);
????????}
????}
② 代碼實現(xiàn)：（非遞歸）
????public?static?void?postOrder(TreeNode?root)?{
????????Deque<TreeNode>?stack?=?new?LinkedList<>();
????????TreeNode?cur?=?root;
????????TreeNode?last?=?null;//記錄上次遍歷的結點
????????while?(!stack.isEmpty()?||?cur?!=?null)?{
????????????//遍歷左子樹
????????????while?(cur?!=?null)?{
????????????????//第一次經(jīng)過?cur?這個結點
????????????????stack.push(cur);
????????????????cur?=?cur.left;
????????????}
????????????//取出棧頂元素但不刪除
????????????TreeNode?top?=?stack.peek();
????????????if(top.right?==?null)?{
????????????????//第二次經(jīng)過?top?這個結點（因為右邊為空，所以可以看作第三次）
????????????????//從左子樹中回來，但是右子樹為空，可以看作從右子樹回來
????????????????stack.pop();
????????????????last?=?top;
????????????????System.out.println(top.v);
????????????}?else?if?(top.right?==?last){
????????????????//第三次經(jīng)過?top
????????????????//說明從右子樹中回來的
????????????????stack.pop();
????????????????last?=?top;
????????????????System.out.println(top.v);
????????????}?else?{
????????????????//第二次經(jīng)過?top
????????????????//說明從左子樹中回來的
????????????????cur?=?top.right;
????????????}
????????}
????}
第二種視角看三種遍歷：
前序 / 中序 / 后序，都是沿著紅色的虛線前進
根據(jù)每次結點 經(jīng)過的次數(shù) 來進行判斷是 什么 類型 的遍歷：
前序：A B D C E F
中序：D B A E C F
后序：D B E F C A
2、BFS（Broadcast First Search）：廣度優(yōu)先遍歷
層次遍歷：- - （隊列）
按照從上到下，從左到右依次將二叉樹遍歷一遍
步驟：準備一個隊列
1、啟動階段 : 把根節(jié)點放入隊列
2、開啟循環(huán)，直到隊列為空（isEmpty）
（1）從隊列中取出隊首結點
（2）層序遍歷經(jīng)過該結點（打印）
（3）把該結點的 左 / 右 孩子放入隊列中（如果存在）
重復上述循環(huán)，即可層序遍歷完二叉樹
最終打印的結果是：A B C D E F G H I
代碼實現(xiàn)：
//層序遍歷
public?class?TreeLevelOrder?{
????public?static?void?levelOrderTraversal(TreeNode?root)?{
????????if?(root?==?null)?{
????????????return;
????????}
????????//隊列的元素的類型是樹的結點
????????Queue<TreeNode>?queue?=?new?LinkedList<>();
????????//1、把根節(jié)點放入隊列
????????queue.add(root);
????????//2、開啟循環(huán)
????????while?(!queue.isEmpty())?{
????????????//（1）從隊列中取出隊首元素
????????????//node?就是層序遍歷時經(jīng)過的結點
????????????TreeNode?node?=?queue.remove();
????????????//（2）打印遍歷結點的值
????????????System.out.println(node.v);
????????????//（3）把該結點的左右子樹放入隊列中
????????????if?(node.left?!=?null)?{
????????????????queue.add(node.left);
????????????}
????????????if?(node.right?!=?null)?{
????????????????queue.add(node.right);
????????????}
????????}
????}
}
用途：（判斷完全二叉樹）
————————————————
版權聲明：本文為CSDN博主「小喬不掉發(fā)」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權協(xié)議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：
https://blog.csdn.net/qq_45658339/article/details/109608414
鋒哥最新SpringCloud分布式電商秒殺課程發(fā)布
??????
??長按上方微信二維碼?2 秒
感謝點贊支持下哈?