今天就跟大家聊聊有關(guān)如何在javascript中實(shí)現(xiàn)二叉樹(shù)的創(chuàng)建和遍歷？，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),寧陵企業(yè)網(wǎng)站建設(shè),寧陵品牌網(wǎng)站建設(shè),網(wǎng)站定制,寧陵網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,寧陵網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

1、先說(shuō)二叉樹(shù)的遍歷，遍歷方式：

前序遍歷：先遍歷根結(jié)點(diǎn)，然后左子樹(shù)，再右子樹(shù)

中序遍歷：先遍歷左子樹(shù)，然后根結(jié)點(diǎn)，再右子樹(shù)

后續(xù)遍歷：先遍歷左子樹(shù)，然后右子樹(shù)，再根結(jié)點(diǎn)

上代碼：主要還是利用遞歸

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());

二叉樹(shù)的非遞歸遍歷

• 深度優(yōu)先遍歷（主要利用棧的先進(jìn)后出）

• 廣度優(yōu)先遍歷（主要利用隊(duì)列的先進(jìn)先出）

//深度優(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)先主要是利用棧，先壓右子樹(shù)，再壓左子樹(shù)

廣度優(yōu)先主要利用隊(duì)列，先入左子樹(shù)，再入右子樹(shù)

深度優(yōu)先的遍歷結(jié)果與前序遍歷相同ABDGHCEIF，廣度優(yōu)先的遍歷結(jié)果是 ABCDEFGHI

2、創(chuàng)建二叉樹(shù)

1中創(chuàng)建二叉樹(shù)的方式過(guò)于笨拙，假入我們根據(jù)完全二叉樹(shù)的模型建立自己的二叉樹(shù)，空數(shù)據(jù)的地方用#表示，如下圖所示我們稱之為擴(kuò)展二叉樹(shù)，我們?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)

你也可以用中序遍歷或者后序遍歷實(shí)現(xiàn)二叉樹(shù)的創(chuàng)建，代碼里生成結(jié)點(diǎn)和構(gòu)建左右子樹(shù)的代碼順序交換一下就行了

看完上述內(nèi)容，你們對(duì)如何在javascript中實(shí)現(xiàn)二叉樹(shù)的創(chuàng)建和遍歷？有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝大家的支持。