当前位置:首页 > 前端 > JavaScript > 正文内容

二叉树及其遍历方法:JavaScript实践

放牧的风2年前 (2020-12-24)JavaScript461

二叉树

  • 常见的数组,栈,列表都是线性结构

  • 常见的树型结构有:文件夹目录,dom结构,路由的配置...

二叉树

二叉树是每个结点最多有两个子树的树形结构,每个结点的度最多是2。左边的称为 左子树 , 右边的称为 右子树 , 左子树 , 右子树 是有顺序的。

实现二叉搜索树

p3-juejin.byteimg.com_tos-cn-i-k3u1fbpfcp_0edc7dff6104483d88cbbc8f28cec56a_tplv-k3u1fbpfcp-zoom-1.image.png

class Node {
    constructor(element, parent) {
        this.element = element; //当前节点
        this.parent = parent; //节点的父亲
        this.left = null; //节点的左侧是什么
        this.rigth = null; //节点的右侧是什么
    }
}

class Tree {
    constructor(compare) {
        //比较器,可以用户自己配置比较规则
        this.compare = compare || this.compare;
        //根节点
        this.root = null;
        //总共有多少个节点
        this.size = 0;
    }

    //内部实现的比较规则,如果用户自己配置了比较规则,则用用户自己的比较规则
    compare(e1, e2) {
        return e1 > e2;
    }

    //向树中添加节点
    add(element) {
        //判断根节点是否存在
        if (this.root == null) {
            //添加为根节点
            this.root = new Node(element, null);
            this.size++;
        } else { //已经存在根节点了
            //获取对比的参照物
            let currentNode = this.root;
            //父亲节点
            let parent = null;
            //对比的结果
            let compare = null;
            while (currentNode) {
                parent = currentNode;
                compare = this.compare(currentNode.element, element);
                if (compare) {
                    //小于参照物
                    currentNode = currentNode.left;
                } else {
                    //大于参照物
                    currentNode = currentNode.rigth;
                }
            }

            //将节点挂到树上
            const node = new Node(element, parent);
            if (compare) {
                parent.left = node;
            } else {
                parent.rigth = node;
            }
            this.size++;
        }
    }
}

const t = new Tree((e1, e2) => {
    return e1.id > e2.id;
});

//自定义比较规则
t.add({
    id: 10,
    name: '章三1'
});
t.add({
    id: 8,
    name: '章三2'
});
t.add({
    id: 6,
    name: '章三3'
});
t.add({
    id: 19,
    name: '章三4'
});
t.add({
    id: 15,
    name: '章三5'
});
t.add({
    id: 22,
    name: '章三6'
});
t.add({
    id: 20,
    name: '章三7'
});
console.dir(t, {
    depth: 1000
});


二叉树的遍历

常见的四种遍历方式

  • 前序:preorder traversal, 先根节点,再左子树,最后右子树

  • 中序:inorder traversal, 先左子树,再根节点,最后右子树,遍历出来的结果是有序的

  • 后序:postorder traversal, 先左子树,再右子树,最后根节点

  • 层序:levelorder traversal, 从上到下,从左到有一次遍历

前序遍历

递归实现
preOrderTraversal(cb) {
    const traversal = node => {
        if (node == null) return;
        //先抛出根节点
        cb(node);
        //先遍历左边,再遍历右边
        traversal(node.left);
        traversal(node.rigth);
    }
    traversal(this.root);
}
循环实现
preOrderTraversal(cb) {
    const queue = [this.root];
    while (queue.length) {
        const node = queue.pop();
        cb(node);
        if (node.rigth) {
            queue.push(node.rigth);
        }
        if (node.left) {
            queue.push(node.left);
        }
    }
}

中序遍历

inOrderTraversal(cb) {
    const traversal = node => {
        if (node == null) return;
        traversal(node.left);
        cb(node);
        traversal(node.rigth);
    }
    traversal(this.root)
}

后序遍历

postOderTraversal(cb) {
    const traversal = node => {
        if (node == null) return;
        traversal(node.left);
        traversal(node.rigth);
        cb(node);
    }
    traversal(this.root)
}

层序遍历

levelOrderTraversal(cb) {
    const stack = [this.root];
    while (stack.length) {
        const node = stack.shift();
        cb(node);
        if (node.left) {
            stack.push(node.left);
        }
        if (node.rigth) {
            stack.push(node.rigth);
        }
    }
}

树的反转

reversalTree() {
    if (this.root == null) return;
    const stack = [this.root];
    let currentNode = null;
    let index = 0
    while (currentNode = stack[index++]) {
        const temp = currentNode.left;
        currentNode.left = currentNode.rigth;
        currentNode.rigth = temp;
        if (currentNode.left) {
            stack.push(currentNode.left);
        }
        if (currentNode.rigth) {
            stack.push(currentNode.rigth)
        }
    }
    return this.root;
}

完整代码

class Node {
    constructor(element, parent) {
        this.element = element; //当前节点
        this.parent = parent; //节点的父亲
        this.left = null; //节点的左侧是什么
        this.rigth = null; //节点的右侧是什么
    }
}

class Tree {
    constructor(compare) {
        //比较器,可以用户自己配置比较规则
        this.compare = compare || this.compare;
        //根节点
        this.root = null;
        //总共有多少个节点
        this.size = 0;
    }

    //内部实现的比较规则,如果用户自己配置了比较规则,则用用户自己的比较规则
    compare(e1, e2) {
        return e1 > e2;
    }

    //向树中添加节点
    add(element) {
        //判断根节点是否存在
        if (this.root == null) {
            //添加为根节点
            this.root = new Node(element, null);
            this.size++;
        } else { //已经存在根节点了
            //获取对比的参照物
            let currentNode = this.root;
            //父亲节点
            let parent = null;
            //对比的结果
            let compare = null;
            while (currentNode) {
                parent = currentNode;
                compare = this.compare(currentNode.element, element);
                if (compare) {
                    //小于参照物
                    currentNode = currentNode.left;
                } else {
                    //大于参照物
                    currentNode = currentNode.rigth;
                }
            }

            //将节点挂到树上
            const node = new Node(element, parent);
            if (compare) {
                parent.left = node;
            } else {
                parent.rigth = node;
            }
            this.size++;
        }
    }

    // preOrderTraversal(cb) {
    //     const traversal = node => {
    //         if (node == null) return;
    //         //先抛出根节点
    //         cb(node);
    //         //先遍历左边,再遍历右边
    //         traversal(node.left);
    //         traversal(node.rigth);
    //     }
    //     traversal(this.root);
    // }

    preOrderTraversal(cb) {
        const queue = [this.root];
        while (queue.length) {
            const node = queue.pop();
            cb(node);
            if (node.rigth) {
                queue.push(node.rigth);
            }
            if (node.left) {
                queue.push(node.left);
            }
        }
    }

    inOrderTraversal(cb) {
        const traversal = node => {
            if (node == null) return;
            traversal(node.left);
            cb(node);
            traversal(node.rigth);
        }
        traversal(this.root)
    }

    postOderTraversal(cb) {
        const traversal = node => {
            if (node == null) return;
            traversal(node.left);
            traversal(node.rigth);
            cb(node);
        }
        traversal(this.root)
    }

    levelOrderTraversal(cb) {
        const stack = [this.root];
        while (stack.length) {
            const node = stack.shift();
            cb(node);
            if (node.left) {
                stack.push(node.left);
            }
            if (node.rigth) {
                stack.push(node.rigth);
            }
        }
    }

    reversalTree() {
        if (this.root == null) return;
        const stack = [this.root];
        let currentNode = null;
        let index = 0
        while (currentNode = stack[index++]) {
            const temp = currentNode.left;
            currentNode.left = currentNode.rigth;
            currentNode.rigth = temp;
            if (currentNode.left) {
                stack.push(currentNode.left);
            }
            if (currentNode.rigth) {
                stack.push(currentNode.rigth)
            }
        }
        return this.root;
    }
}

const t = new Tree((e1, e2) => {
    return e1.id > e2.id;
});

//自定义比较规则
t.add({ id: 10, name: '章三1' });
t.add({ id: 8, name: '章三2' });
t.add({ id: 6, name: '章三3' });
t.add({ id: 19, name: '章三4' });
t.add({ id: 15, name: '章三5' });
t.add({ id: 22, name: '章三6' });
t.add({ id: 20, name: '章三7' });

console.dir(t.reversalTree(), { depth: 1000 });

// t.levelOrderTraversal((node) => {
//     console.log(node.element)
// })


扫描二维码推送至手机访问。

版权声明:本文由放牧的风发布,如需转载请注明出处。

本文链接:https://grazingwind.com/post/59.html

分享给朋友:

相关文章

ES6必知必会 —— Module

1. ES6在语言标准的层面上,实现了模块功能,成为浏览器和服务器通用的模块解决方案,完全可以取代 CommonJS 和 AMD 规范,基本特点如下:每一个模块只加载一次, 每一个JS只执行一次, 如果下次再去加载同目录下同文件,直接从内存...

JavaScript专题系列目录

JavaScript专题之跟着underscore学防抖JavaScript专题之跟着underscore学节流JavaScript专题之数组去重JavaScript专题之类型判断(上)JavaScript专题之类型判断(下)JavaScr...

JavaScript 中常见设计模式整理

JavaScript 中常见设计模式整理

开发中,我们或多或少地接触了设计模式,但是很多时候不知道自己使用了哪种设计模式或者说该使用何种设计模式。本文意在梳理常见设计模式的特点,从而对它们有比较清晰的认知。JavaScript 中常见设计模式单例模式策略模式代理模式迭代器模式发布-...

JavaScript中undefined与null的区别

JavaScript中undefined与null的区别

大多数计算机语言,有且仅有一个表示"无"的值,比如,C语言的NULL,Java语言的null,Python语言的None,Ruby语言的nil。有点奇怪的是,JavaScript语言居然有两个表示"无"...

babel、vue编译,Prettier原理等离不开的AST技术

babel、vue编译,Prettier原理等离不开的AST技术

概要本文将通过以下几个方面对AST进行学习为什么要了解AST,简要说明AST在开发中的重要性什么是AST,对AST有一个直观的认识AST是如何生成的,分析将代码解析成AST的原理AST的具体应用,通过解读babel原理、vue模板编译过程,...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。