您好,登錄后才能下訂單哦!
今天就跟大家聊聊有關(guān)如何在javascript中實現(xiàn)二叉樹的創(chuàng)建和遍歷?,可能很多人都不太了解,為了讓大家更加了解,小編給大家總結(jié)了以下內(nèi)容,希望大家根據(jù)這篇文章可以有所收獲。
1、先說二叉樹的遍歷,遍歷方式:
前序遍歷:先遍歷根結(jié)點,然后左子樹,再右子樹
中序遍歷:先遍歷左子樹,然后根結(jié)點,再右子樹
后續(xù)遍歷:先遍歷左子樹,然后右子樹,再根結(jié)點
上代碼:主要還是利用遞歸
function TreeCode() { let BiTree = function (ele) { this.data = ele; this.lChild = null; this.rChild = null; } this.createTree = function () { let biTree = new BiTree('A'); biTree.lChild = new BiTree('B'); biTree.rChild = new BiTree('C'); biTree.lChild.lChild = new BiTree('D'); biTree.lChild.lChild.lChild = new BiTree('G'); biTree.lChild.lChild.rChild = new BiTree('H'); biTree.rChild.lChild = new BiTree('E'); biTree.rChild.rChild = new BiTree('F'); biTree.rChild.lChild.rChild = new BiTree('I'); return biTree; } } //前序遍歷 function ProOrderTraverse(biTree) { if (biTree == null) return; console.log(biTree.data); ProOrderTraverse(biTree.lChild); ProOrderTraverse(biTree.rChild); } //中序遍歷 function InOrderTraverse(biTree) { if (biTree == null) return; InOrderTraverse(biTree.lChild); console.log(biTree.data); InOrderTraverse(biTree.rChild); } //后續(xù)遍歷 function PostOrderTraverse(biTree) { if (biTree == null) return; PostOrderTraverse(biTree.lChild); PostOrderTraverse(biTree.rChild); console.log(biTree.data); } let myTree = new TreeCode(); console.log(myTree.createTree()); console.log('前序遍歷') ProOrderTraverse(myTree.createTree()); console.log('中序遍歷') InOrderTraverse(myTree.createTree()); console.log('后續(xù)遍歷') PostOrderTraverse(myTree.createTree());
二叉樹的非遞歸遍歷
深度優(yōu)先遍歷(主要利用棧的先進后出)
廣度優(yōu)先遍歷(主要利用隊列的先進先出)
//深度優(yōu)先非遞歸 function DepthFirstSearch(biTree) { let stack = []; stack.push(biTree); while (stack.length != 0) { let node = stack.pop(); console.log(node.data); if (node.rChild) { stack.push(node.rChild); } if (node.lChild) { stack.push(node.lChild); } } } //廣度優(yōu)先非遞歸 function BreadthFirstSearch(biTree) { let queue = []; queue.push(biTree); while (queue.length != 0) { let node = queue.shift(); console.log(node.data); if (node.lChild) { queue.push(node.lChild); } if (node.rChild) { queue.push(node.rChild); } } }
深度優(yōu)先主要是利用棧,先壓右子樹,再壓左子樹
廣度優(yōu)先主要利用隊列,先入左子樹,再入右子樹
深度優(yōu)先的遍歷結(jié)果與前序遍歷相同ABDGHCEIF,廣度優(yōu)先的遍歷結(jié)果是 ABCDEFGHI
2、創(chuàng)建二叉樹
1中創(chuàng)建二叉樹的方式過于笨拙,假入我們根據(jù)完全二叉樹的模型建立自己的二叉樹,空數(shù)據(jù)的地方用#表示,如下圖所示我們稱之為擴展二叉樹,我們?nèi)∑淝靶虮闅v的序列 AB#D##C##。
上代碼:也是利用遞歸
//前序遍歷得到的字符串 let strArr = 'AB#D##C##'.split(''); function BiTree(ele) { this.data = ele; this.lChild = null; this.rChild = null; } var newTree = new BiTree('#'); function createBiTree(biTree) { if (strArr.length == 0) return; let str = strArr.shift(); if (str == '#') return; biTree.data = str; if (strArr[0] != '#') { biTree.lChild = new BiTree('#') } createBiTree(biTree.lChild); if (strArr[0] != '#') { biTree.rChild = new BiTree('#') } createBiTree(biTree.rChild); } createBiTree(newTree); console.log(newTree); ProOrderTraverse(newTree)
你也可以用中序遍歷或者后序遍歷實現(xiàn)二叉樹的創(chuàng)建,代碼里生成結(jié)點和構(gòu)建左右子樹的代碼順序交換一下就行了
看完上述內(nèi)容,你們對如何在javascript中實現(xiàn)二叉樹的創(chuàng)建和遍歷?有進一步的了解嗎?如果還想了解更多知識或者相關(guān)內(nèi)容,請關(guān)注億速云行業(yè)資訊頻道,感謝大家的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。