二叉樹是一種很重要的數(shù)據(jù)結(jié)構(gòu)，對(duì)于二叉樹的遍歷，有深度優(yōu)先遍歷和廣度優(yōu)先遍歷，深度優(yōu)先遍歷又有先序、中序、后續(xù)遍歷，廣度優(yōu)先遍歷就是按層遍歷。

1. 深度優(yōu)先遍歷

---

深度優(yōu)先遍歷，也就是先序、中序、后續(xù)遍歷，我之前有一篇隨筆已經(jīng)說(shuō)的很清楚了，在這里我只貼下代碼就好了。

傳送門：詳細(xì)教你實(shí)現(xiàn)BST(二叉排序樹)

在這里我依然用之前建立好的Node、Stack、BST結(jié)構(gòu)來(lái)實(shí)現(xiàn)代碼。

class Node {constructor(data, leftNode, rightNode) {this.data = datathis.leftNode = leftNodethis.rightNode = rightNode}print () {return this.data} }class Stack {constructor() {this.arr = []}pop () {return this.arr.shift()}push (data) {this.arr.unshift(data)}isEmpty () {return this.arr.length == 0} }class BST {constructor() {this.root = null}insert (data) {...}preOrder () {...}inOrder () {...}postOrder () {...}... }

先是先序、中序、后序遍歷的遞歸實(shí)現(xiàn)，很簡(jiǎn)單。

// 遞歸先序 function preOrderFn (node) {if (node) {console.log(node.print())preOrderFn(node.leftNode)preOrderFn(node.rightNode)} }// 遞歸中序 function inOrderFn (node) {if (node) {inOrderFn(node.leftNode)console.log(node.print())inOrderFn(node.rightNode)} }// 遞歸后續(xù) function postOrderFn (node) {if (node) {postOrderFn (node.leftNode)postOrderFn (node.rightNode)console.log(node.print())} }

然后就是先序、中序、后續(xù)遍歷的非遞歸實(shí)現(xiàn)了。詳細(xì)的解釋和說(shuō)明，點(diǎn)擊上面的傳送門就有了，這里不過(guò)多贅述。

// 非遞歸先序 function PreOrderWithoutRecursion (root) {if (!root)returnvar parentNode = rootvar stack = new Stack()while (parentNode || !stack.isEmpty()) {// 一直遍歷到左子樹的最下面，一邊打印data,將一路遍歷過(guò)的節(jié)點(diǎn)push進(jìn)棧中if (parentNode) {console.log(parentNode.data)stack.push(parentNode)parentNode = parentNode.leftNode}// 當(dāng)parentNode為空時(shí)，說(shuō)明已經(jīng)達(dá)到了左子樹的最下面，可以出棧操作了else {parentNode = stack.pop()// 進(jìn)入右子樹，開(kāi)始新一輪循環(huán)parentNode = parentNode.rightNode}} }// 非遞歸中序 function inOrderWithoutRecursion (root) {if (!root)returnvar parentNode = rootvar stack = new Stack()while (parentNode || !stack.isEmpty()) {// 一直遍歷到左子樹的最下面，將一路遍歷過(guò)的節(jié)點(diǎn)push進(jìn)棧中if (parentNode) {stack.push(parentNode)parentNode = parentNode.leftNode}// 當(dāng)parentNode為空時(shí)，說(shuō)明已經(jīng)達(dá)到了左子樹的最下面，可以出棧操作了else {parentNode = stack.pop()console.log(parentNode.data)// 進(jìn)入右子樹，開(kāi)始新一輪循環(huán)parentNode = parentNode.rightNode}} }// 非遞歸后續(xù) function PostOrderWithoutRecursion (root) {if (!root)returnvar parentNode = rootvar stack = new Stack()var lastVisitNode = nullwhile (parentNode || !stack.isEmpty()) {if (parentNode) {stack.push(parentNode)parentNode = parentNode.leftNode}else {parentNode = stack.pop()// 如果當(dāng)前節(jié)點(diǎn)沒(méi)有右節(jié)點(diǎn)或者是右節(jié)點(diǎn)被訪問(wèn)過(guò)，則訪問(wèn)當(dāng)前節(jié)點(diǎn)if (!parentNode.rightNode || parentNode.rightNode.data == lastVisitNode.data) {console.log(parentNode.data)lastVisitNode = parentNode}// 訪問(wèn)右節(jié)點(diǎn)else {stack.push(parentNode)parentNode = parentNode.rightNodewhile (parentNode) {parentNode = parentNode.leftNode}}}} }

2. 廣度優(yōu)先遍歷

---

其實(shí)這片隨筆有點(diǎn)打醬油了，只說(shuō)了兩個(gè)遍歷，還有一個(gè)是在以前實(shí)現(xiàn)過(guò)的。

廣度優(yōu)先遍歷，顧名思義，就是橫向先遍歷，也就是按層次遍歷，從根節(jié)點(diǎn)往下，對(duì)每一層依此訪問(wèn)，在每一層中從左到右（也可以從右到左）遍歷，遍歷完一層就進(jìn)入下一層，直到?jīng)]有節(jié)點(diǎn)。

之前講深度優(yōu)先非遞歸遍歷的時(shí)候，我們用到了一個(gè)棧的數(shù)據(jù)結(jié)構(gòu)，到了廣度優(yōu)先遍歷的時(shí)候，我們就要用到隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)。

為什么上一次用棧，這一次就要用到隊(duì)列了呢？

拿非遞歸中序遍歷舉例，我們每遍歷到一個(gè)節(jié)點(diǎn)就要進(jìn)行入棧操作，遍歷完左節(jié)點(diǎn)之后，還需要找到根節(jié)點(diǎn)，再通過(guò)根節(jié)點(diǎn)找到右節(jié)點(diǎn)，所以我們需要最后遍歷到的節(jié)點(diǎn)在這個(gè)數(shù)據(jù)結(jié)構(gòu)的最頂端，這不就是棧嗎？

先把我們的隊(duì)列的數(shù)據(jù)結(jié)構(gòu)先建立起來(lái)再說(shuō)。依然用數(shù)組模擬隊(duì)列的操作。

class Queue {constructor () {this.arr = []}enqueue (data) {return this.arr.push(data)}dequeue () {return this.arr.shift()}isEmpty () {return this.arr.length == 0} }

為什么要用隊(duì)列呢，我們按層次遍歷，首先遍歷根節(jié)點(diǎn)，然后左子樹，右子樹，然后左子樹的左子樹，左子樹的右子樹，右子樹的左子樹，依此類推。每遍歷到一個(gè)節(jié)點(diǎn)，就將它存在一個(gè)數(shù)據(jù)結(jié)構(gòu)里，先把它的前面的節(jié)點(diǎn)遍歷完，才能遍歷它，也就是一個(gè)先進(jìn)先出（FIFO）的遍歷方式，這不就是隊(duì)列嗎？

說(shuō)下思路：首先現(xiàn)將根節(jié)點(diǎn)做入隊(duì)操作，隊(duì)列里的節(jié)點(diǎn)表示我們要遍歷的節(jié)點(diǎn)，所以隊(duì)列為空的時(shí)候也就是沒(méi)有節(jié)點(diǎn)可以遍歷了，即隊(duì)列不為空的時(shí)候循環(huán)遍歷整個(gè)隊(duì)列。首先我們?nèi)〕鲫?duì)列的第一個(gè)節(jié)點(diǎn)，也就是對(duì)這個(gè)隊(duì)列做出隊(duì)操作，訪問(wèn)這個(gè)節(jié)點(diǎn)的值，如果這個(gè)節(jié)點(diǎn)存在左子樹，那么將它的左子樹放在隊(duì)列的末尾，也就是對(duì)左子樹做入隊(duì)操作，右子樹同理。

思路很簡(jiǎn)單，實(shí)現(xiàn)起來(lái)不難：

class BST {constructor() {this.root = null}// 廣度優(yōu)先遍歷levelOrderTraversal () {levelOrderTraversalFn(this.root)}insert (data) {...}preOrder () {...}inOrder () {...}postOrder () {...}find (data) {..}getMax () {...}getMin () {...}deleteNode (data) {...}depth () {...}nodeCount () {...} }// 廣度優(yōu)先遍歷 function levelOrderTraversalFn (node) {if(!node) {return}var que = new Queue()que.enqueue(node)while(!que.isEmpty()) {node = que.dequeue()console.log(node.data)if(node.leftNode) que.enqueue(node.leftNode)if(node.rightNode) que.enqueue(node.rightNode)} }

我們?cè)囈幌?#xff1a;

沒(méi)錯(cuò)，那我們的廣度優(yōu)先遍歷也就寫完了。

轉(zhuǎn)載于:https://www.cnblogs.com/isLiu/p/8328533.html

總結(jié)

以上是生活随笔為你收集整理的二叉树的深度优先遍历和广度优先遍历的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。