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

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

放牧的风4年前 (2020-12-24)JavaScript1727

二叉树

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

  • 常见的树型结构有:文件夹目录,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

分享给朋友:

相关文章

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

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

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

JavaScript ES6 系列目录

JavaScript ES6 系列目录

ES6 系列之 let 和 constES6 系列之模板字符串ES6 系列之箭头函数ES6 系列之模拟实现 Symbol 类型ES6 系列之迭代器与 for ofES6 系列之模拟实现一个 Set 数据结构ES6 系列之 WeakMapES...

JavaScript 中常见设计模式整理

JavaScript 中常见设计模式整理

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

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

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

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

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

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

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