当前位置:   article > 正文

web前端算法之二叉树_前端二叉树使用场景

前端二叉树使用场景

二叉树使用场景

  • 数据结构:二叉树是一种常见的数据结构,可以用于存储和组织数据。例如,二叉搜索树是一种特殊的二叉树,它可以快速地查找、插入和删除数据。
  • 排序算法:二叉树可以用于实现一些排序算法,例如快速排序和归并排序。在这些算法中,二叉树被用来将数据划分为独立的子集,并对这些子集进行排序。
  • 表达式求值:二叉树可以用于表示数学表达式,并对其进行求值。在这种情况下,二叉树的每个节点表示一个运算符或操作数,而节点的子节点表示操作数。
  • 实现决策树:在机器学习中,决策树是一种重要的算法,它可以用于分类和回归问题。在这种情况下,二叉树被用来表示决策过程,每个节点表示一个决策条件,而子节点表示不同的结果。
  • 数据压缩:在数据压缩中,二叉树可以用于编码和解码数据。在这种情况下,二叉树的每个节点表示一个符号或一组符号的编码,而子节点表示编码的上下文。
    编译器:在编译器中,二叉树被用来表示源代码的结构,并对源代码进行语法分析和语义分析。在这种情况下,二叉树的每个节点表示一个语法或语义结构,而子节点表示语法或语义规则。

用代码描述二叉树

图1、二叉树

// 构造二叉树
const TreeNode = function(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}
// 创建节点
const a = new TreeNode('A');
const b = new TreeNode('B');
const c = new TreeNode('C');
const d = new TreeNode('D');
const e = new TreeNode('E');
const f = new TreeNode('F');
const g = new TreeNode('G');

// 连接节点
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
console.log("构建的二叉树如下:", a);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

二叉树遍历

前序遍历
  • 概念: 根节点 -> 左子树 -> 右子树
  • 图1中二叉树前序遍历:[‘A’,’ B’,’ D’, ’ E’, ’ C’, ’ F’, ’ G’]
后序遍历
  • 概念: 左子树 -> 右子树 -> 根节点
  • 图1中二叉树后序遍历: [’ D’, ’ E’, ’ B’, ’ F’, ’ G’, ’ C’, ‘A’]
中序遍历
  • 概念: 左子树 -> 根节点 -> 右子树
  • 图1中二叉树后序遍历:[’ D’, ’ B’, ’ C’, ‘A’, ’ F’, ’ C’, ’ G’]

二叉树还原

  • 注意:有中序遍历情况 + 前序或者后序遍历才能还原二叉树
  • 前序遍历+中序遍历 还原二叉树
/**
 * 通过前序、中序还原二叉树
 * @param {array} qian 前序遍历值数组
 * @param {array} zhong 中序遍历值数组
 * @returns 根节点 
 */
function toTreeFromQianzhong(qian, zhong) {
    if(qian !== null && qian.length > 0 && zhong !== null && zhong.length > 0 && qian.length === zhong.length){
        // 通过前序遍历获取根节点
        const node = new TreeNode(qian[0]);
        // 中序处理:得到左子树与右子树
        const nodePos = zhong.indexOf(node.value);
        const zLeft = zhong.slice(0, nodePos);
        const zRight = zhong.slice(nodePos+1, zhong.length);
        // 前序处理:得到左子树与右子树
        const leftEnd = 1+ zLeft.length;
        const qLeft = qian.slice(1, leftEnd);
        const qRight = qian.slice(leftEnd, qian.length);
        // 递归处理左右子树
        node.left = toTreeFromQianzhong(qLeft, zLeft);
        node.right = toTreeFromQianzhong(qRight, zRight);
        return node;
    }else{
        return null;
    }    
}
const qianList = ['A',' B',' D', ' e', ' C', ' F', ' G'];
const zhongList = [' D', ' B', ' C', 'A', ' F', ' C', ' G'];
const qzRoot = toTreeFromQianzhong(qianList, zhongList);
console.log("前序中序还原二叉树", qzRoot);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 后序遍历+中序遍历 还原二叉树
/**
 * 通过后序、中序还原二叉树
 * @param {array} hou 后序遍历值数组
 * @param {array} zhong 中序遍历值数组
 * @returns 
 */
function toTreeFromHouzhong(hou, zhong) {
    if(hou !== null && hou.length > 0 && zhong !== null && zhong.length > 0 && hou.length === zhong.length){
        // 通过后序遍历获取根节点
        const node = new TreeNode(hou[hou.length - 1]);
        // 中序处理:得到左子树与右子树
        const nodePos = zhong.indexOf(node.value);
        const zLeft = zhong.slice(0, nodePos);
        const zRight = zhong.slice(nodePos+1, zhong.length);
        // 前序处理:得到左子树与右子树
        const leftEnd = 0 + zLeft.length;
        const hLeft = hou.slice(0, leftEnd);
        const hRight = hou.slice(leftEnd, hou.length - 1);
        // 递归处理左右子树
        node.left = toTreeFromHouzhong(hLeft, zLeft);
        node.right = toTreeFromHouzhong(hRight, zRight);
        return node;
    }else{
        return null;
    }    
}
const zhongList = [' D', ' B', ' C', 'A', ' F', ' C', ' G'];
const houList = [' D', ' e', ' B', ' F', ' G', ' C', 'A'];
const hzRoot = toTreeFromHouzhong(houList, zhongList);
console.log("后序、中序还原二叉树", hzRoot);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

二叉树diff算法(区分左右子树)

/**
 * 比较两棵二叉树的的diff算法
 * 注意:区分左右子树情况
 * 添加: {type: 'add', old: null,  cur: null}
 * 修改: {type: 'modify', old: null,  cur: null}
 * 删除: {type: 'delete', old: null,  cur: null}
 */
function lrDiffNode(node1, node2, diff) {
    if(node1 === null && node2 === null){
        // 没有变化,并且已经结束
        return diff;
    }else if(node1 !== null && node2 === null){
        // 删除情况,并且已经结束
        diff.push({type: 'delete', old: node1,  cur: node2});
        return diff;
    }else if(node1 === null && node2 !== null){
        // 添加情况,并且已经结束
        diff.push({type: 'add', old: node1,  cur: node2});
        return diff;
    }else{
        // node1与node2都不为空情况下
        if(node1 === node2){
            // 完全相同
            return diff;
        }else{
            // 比对左右子树
            const diffLr = ()=>{
                lrDiffNode(node1.left, node2.left, diff);
                lrDiffNode(node1.right, node2.right, diff);
            };
            if(node1.value === node2.value){
                // 值相同,那么比较左右子树
                diffLr();
                return diff;
            }else{
                // 记录不同信息
                diff.push({type: 'modify', old: node1,  cur: node2});
                // 继续比对左右子树
                diffLr();
                return diff;
            }
        }
    }
}

// 删除:f节点
const qianList1= ['A',' B',' D', ' e', ' C', ' G'];
const zhongList1 = [' D', ' B', ' C', 'A', ' C', ' G'];
const houList1 = [' D', ' e', ' B',  ' G', ' C', 'A'];
const newTreeRoot = toTreeFromQianzhong(qianList1, zhongList1);
console.log("diff: 删除f节点", lrDiffNode(a, newTreeRoot, []));

// 将b节点修改为h
const qianList_modify_b_h = ['A','h',' D', ' e', ' C', ' F', ' G'];
const zhongList_modify_b_h = [' D', 'h', ' C', 'A', ' F', ' C', ' G'];
const houList_modify_b_h = [' D', ' e', 'h', ' F', ' G', ' C', 'A'];
const treeRoot_b_h = toTreeFromHouzhong(houList_modify_b_h, zhongList_modify_b_h);
console.log("diff: b节点修改为h", lrDiffNode(a, treeRoot_b_h, []));
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

二叉树查找

  • 深度优先算法
/**
 * 查找二叉树中元素(深度优先)- 寻找的路径其实就是前序遍历
 * @param root 根节点
 * @param findValue 查找的值
 * @returns 
 */
const findNode = function(root, findValue) {
    if(root!== null){
        if(findValue !== null && findValue !== void 0){
            console.log("深度优先过程:" + root.value);
            if(root.value === findValue){
                return root;
            }else{
                // 分别在左右子树中寻找
                return findNode(root.left, findValue) || findNode(root.right, findValue);
            }
        }else{
            return null;
        }
    }else{
        return null;
    }
}
console.log("find[深度优先]:在tree中找出g元素", findNode(a, ' F'));
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 广度优先算法
/**
 * 查找二叉树中元素(广度优先)
 * @param nodes 
 * @param findValue 
 * @returns 
 */
const findNodeByScope = function(nodes, findValue) {
    if(nodes!== null && nodes.length > 0){
        const nextFindNodes = [];
        for (let node of nodes) {
            console.log("广度优先过程:" + node.value);
            if(node.value === findValue){
                return node;
            }else{
                nextFindNodes.push(node.left);
                nextFindNodes.push(node.right);
            }
        }
        return findNodeByScope(nextFindNodes, findValue);
    }else{
        return null;
    }
}
console.log("find[广度优先]: 在tree中找出g元素", findNodeByScope([a], ' G'));
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/718443
推荐阅读
相关标签
  

闽ICP备14008679号