本篇文章給大家介紹一下使用javascript實現二叉樹的創(chuàng)建和遍歷的方法。有一定的參考價值，有需要的朋友可以參考一下，希望對大家有所幫助。

創(chuàng)新互聯公司專業(yè)為企業(yè)提供江海網站建設、江海做網站、江海網站設計、江海網站制作等企業(yè)網站建設、網頁設計與制作、江海企業(yè)網站模板建站服務，十年江海做網站經驗，不只是建網站，更提供有價值的思路和整體網絡服務。

1、先說二叉樹的遍歷，遍歷方式：

前序遍歷：先遍歷根結點，然后左子樹，再右子樹

中序遍歷：先遍歷左子樹，然后根結點，再右子樹

后續(xù)遍歷：先遍歷左子樹，然后右子樹，再根結點

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

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)先的遍歷結果與前序遍歷相同ABDGHCEIF，廣度優(yōu)先的遍歷結果是 ABCDEFGHI

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

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

你也可以用中序遍歷或者后序遍歷實現二叉樹的創(chuàng)建，代碼里生成結點和構建左右子樹的代碼順序交換一下就行了

推薦教程：《JavaScript視頻教程》

網站題目：javascript如何實現二叉樹的創(chuàng)建和遍歷？（代碼示例）
文章鏈接：http://www.yijiale78.com/article18/cppdgp.html

成都網站建設公司_創(chuàng)新互聯，為您提供軟件開發(fā)、小程序開發(fā)、定制網站、品牌網站建設、自適應網站、響應式網站

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯