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

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

放牧的风6个月前 (12-24)JavaScript69

二叉树

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

  • 常见的树型结构有:文件夹目录,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://faka.grazingwind.com/post/59.html

分享给朋友:

相关文章

ES6必知必会 —— Module

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

JavaScript深入系列目录

JavaScript深入之从原型到原型链JavaScript深入之词法作用域和动态作用域JavaScript深入之执行上下文栈JavaScript深入之变量对象JavaScript深入之作用域链JavaScript深入之从ECMAScrip...

js中push(),pop(),unshift(),shift()的用法小结

1、push()、pop()和unshift()、shift()这两组同为对数组的操作,并且会改变数组的本身的长度及内容。不同的是 push()、pop() 是从数组的尾部进行增减,unshift()、shift() 是从数组的头...

这些原生DOM操作你还记住多少😨

这些原生DOM操作你还记住多少😨

前言 最近在二次封装一个公司内部的UI组件库,其中一个模块就是给 element-plus 的 message 进行扩展,大量运用到了原生DOM操作,操作DOM最方便...

在jquery each循环中的continue和break

jquery each中不能直接使用continue或break解决方案要实现break和continue的功能的话,要使用其它的方式 break—-用return false; continue –用return tu...

基于MySQL + Node.js + Leaflet的离线地图展示,支持百度、谷歌、高德、腾讯地图

基于MySQL + Node.js + Leaflet的离线地图展示,支持百度、谷歌、高德、腾讯地图

1. 基本说明本项目实现了离线展示百度、谷歌、高德、腾讯地图。主要功能如下:实现了地图瓦片图下载、存储。目前支持存储至MySQLNode.js服务调用MySQL中的瓦片图Leaflet展示地图展示效果如下:2. 地图瓦片下载工具及配置工具下...

发表评论

访客

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