您好,登錄后才能下訂單哦!
前言:
緊接著上篇 二叉樹的javascript實(shí)現(xiàn) ,來(lái)說(shuō)一下二叉樹的遍歷。
本次一本正經(jīng)的胡說(shuō)八道,以以下這個(gè)二叉樹為例子進(jìn)行遍歷:
接著是要引入二叉樹實(shí)現(xiàn)的代碼:
function Node(data, left, right) { this.data = data; this.left = left; this.right = right; this.show = show; } function show() { return this.data; } function BST() { this.root = null; this.insert = insert; } function insert(data) { var n = new Node(data, null, null); if (this.root == null) { this.root = n; } else { var current = this.root; var parent; while (true) { parent = current; if (data < current.data) { current = current.left; if (current == null) { parent.left = n; break; } } else { current = current.right; if (current == null) { parent.right = n; break; } } } } }
二叉樹遍歷的分類
二叉樹的遍歷分為先序、中序、后序遍歷。這里說(shuō)到的先序、中序、后序是相對(duì)于父節(jié)點(diǎn)來(lái)說(shuō)。父節(jié)點(diǎn)的值先輸出就是先序,三者間它在中間輸出就是中序,最后輸出就是后序。至于那個(gè)是父節(jié)點(diǎn)是相對(duì)而言的,因?yàn)槌巳~子節(jié)點(diǎn)(最底下一層節(jié)點(diǎn)),其他每個(gè)節(jié)點(diǎn)都可以是父節(jié)點(diǎn)。
先序遍歷
先序遍歷就是,先打印父節(jié)點(diǎn),然后是左子節(jié)點(diǎn)(左子樹),然后再打印右子節(jié)點(diǎn)(子樹)。
function preOrder(node) { if (!(node == null)) { console.log(node.show() + " "); preOrder(node.left); preOrder(node.right); } } // 給BST類添加先序遍歷的成員方法 function BST() { this.root = null; this.insert = insert; this.preOrder = preOrder; }
preOrder函數(shù)是遞歸實(shí)現(xiàn)的,應(yīng)該說(shuō)二叉樹的遍歷都是遞歸實(shí)現(xiàn)的??赡苡行┤藭?huì)因?yàn)橄刃虮闅v的特征:“先打印父節(jié)點(diǎn),然后是左子節(jié)點(diǎn)(左子樹),然后再打印右子節(jié)點(diǎn)(子樹)” 而陷入一個(gè)錯(cuò)誤的想法,這想法是什么請(qǐng)看下圖:
注意紅框部分,父節(jié)點(diǎn)是10,左子節(jié)點(diǎn)是3,右子節(jié)點(diǎn)是18,因?yàn)樯厦娴慕Y(jié)論,可能會(huì)錯(cuò)誤地認(rèn)為打印的順序是10 → 3 → 18,然而事實(shí)并非如此[捂臉],真是的順序是:先打印10,然后是打印左子樹,打印完左子樹的全部節(jié)點(diǎn)后,才開始打印以10位父節(jié)點(diǎn)的右子樹:
這個(gè)時(shí)候,你的腦海就該這樣想:
然后是這樣想:
如此類推打印完以10為父節(jié)點(diǎn)的左子樹,然后也是以這樣的方式打印以10為父節(jié)點(diǎn)的右子樹,按著這種 拆分代替的思想 來(lái)理解會(huì)更好明白二叉樹的遍歷。
然后最終,先序遍歷改二叉樹的順序是:
按圖的輸出順序是:10 -> 3 -> 2 -> 4 -> 9 -> 8 -> 9 -> 18 -> 13 -> 21
最后來(lái)實(shí)踐一下,先序遍歷:
var bst = new BST(); var nums = [10, 3, 18, 2, 4, 13, 21, 9, 8, 9]; for(var i = 0; i < nums.length; i++) { bst.insert(nums[i]); } bst.preOrder(bst.root);
這里強(qiáng)調(diào)一下,輸出順序和插入順序有關(guān)的,因?yàn)槟悴迦腠樞虿煌傻亩鏄湟彩遣煌?。有疑?wèn)的可以去 二叉樹的javascript實(shí)現(xiàn) 細(xì)看一下,有比較明白的說(shuō)明了二叉樹,也可以實(shí)驗(yàn)一下:
中序遍歷
看完先序遍歷,已經(jīng)可以類推到很多和中序、后序遍歷相關(guān)的知識(shí)點(diǎn)。中序遍歷的特征是:先打印左子樹(左子節(jié)點(diǎn)),接著打印父節(jié)點(diǎn),最后打印右子樹(右子節(jié)點(diǎn))。
function inOrder(node) { if (!(node == null)) { inOrder(node.left); console.log(node.show() + " "); inOrder(node.right); } } // 給BST類添加該成員方法 function BST() { this.root = null; this.insert = insert; this.preOrder = preOrder; this.inOrder = inOrder; }
中序遍歷的打印順序:
按上圖的輸出順序是:2 -> 3 -> 4 -> 8 -> 9 -> 9 -> 10 -> 13 -> 18 -> 21
接著是,實(shí)踐一下中序遍歷:
后序遍歷
function postOrder(node) { if (!(node == null)) { postOrder(node.left); postOrder(node.right); console.log(node.show() + " "); } } // 給BST類添加該成員方法 function BST() { this.root = null; this.insert = insert; this.preOrder = preOrder; this.inOrder = inOrder; this.postOrder = postOrder; }
后序遍歷的打印順序
按上圖的輸出順序是:2 -> 8 -> 9 -> 9 -> 4 -> 3 -> 13 -> 21 -> 18 -> 10
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。