欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

JS树的遍历

程序员文章站 2022-03-14 18:12:49
...

先序、中序、后序、层次遍历:

//树的数据结构
function TreeNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
}

//先序遍历(Degree Left Right)
function DLR(root){
    console.log(root.val);
    if(root.left){
        DLR(root.left);
    }
    if(root.right){
        DLR(root.right);
    }
}

//中序遍历(Left Degree Right)
function LDR(root){
    if(root.left){
        LDR(root.left);
    }
    console.log(root.val);
    if(root.right){
        LDR(root.right);
    }
}

//后序遍历(Left Right Degree)
function LRD(root){
    if(root.left){
        LRD(root.left);
    }
    if(root.right){
        LRD(root.right);
    }
    console.log(root.val);
}

//层次遍历
function levelTraversal(root){
    if(!root) return false; //如果头结点为空,返回假
    let result = [];    //创建一个数组,存放结果
    let tree = [];  //创建一个数组存放二叉树
    tree.push(root);    //先传入头结点

    //当tree数组长度不为空
    while(tree.length){
        let node = tree.shift();    //将数组第一个结点放到node中
        result.push(node.val);  //将node结点的值压到result数组中
        //如果node结点左子树不为空
        if(node.left){
            tree.push(node.left);
        }
        //如果node结点右子树不为空
        if(node.right){
            tree.push(node.right);
        }
    }
    return result;
}

let tnode = new TreeNode(3);
tnode.left = {"val":2};
tnode.right = {"val":1};
console.log(tnode);
console.log("先序遍历:");
DLR(tnode);
console.log("中序遍历:");
LDR(tnode);
console.log("后序遍历:");
LRD(tnode);
console.log("层次遍历:",levelTraversal(tnode));

JS树的遍历

相关标签: 数据结构