多线程 Java包装类 希腊字母 bam firebase plugins db2 Notify.js 后台管理模板下载 jq去除空格 jquery选择子元素 jquery关闭当前窗口 mysql倒序 kb转mb ab软启动器 pcm接口 nfc卡片 python连接mysql python安装教程 python中count python文件操作 windows安装python环境 java环境搭建 java函数式接口 java如何连接mysql java基础框架 java学习流程 狮子狗出装 忧思华光玉 临时会话 html5下载 win10有哪些版本 软件龙头股 dnf95b套 3dmax2014下载 js递归函数 flash教程 苹果8怎么截屏 画图橡皮擦怎么放大 bat转exe
当前位置: 首页 > 学习教程  > 编程语言

es 实现二叉树的前序中序,后序遍历,后序中序还原二叉树,前序中序还原二叉树,二叉树的比较diff

2020/12/5 11:01:07 文章标签:

// 二叉树class Node {constructor(value) {this.value value;this.left null;this.right null;}/*** 二叉树的前序遍历* returns {null}* constructor*/DLR() {if (!this) return null;// 输出当前的console.log(this.value);this.left && this.left.DLR();this.ri…

// 二叉树

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    /**
     * 二叉树的前序遍历
     * @returns {null}
     * @constructor
     */
    DLR() {
        if (!this) return null;
        // 输出当前的
        console.log(this.value);
        this.left && this.left.DLR();
        this.right && this.right.DLR();
    }

    /**
     * 二叉树的中序遍历
     * @returns {null}
     * @constructor
     */
    LDR() {
        if (!this) return null;
        // 先遍历左边
        this.left && this.left.LDR();
        // 遍历自己
        console.log(this.value);
        // 遍历右边
        this.right && this.right.LDR();
    }

    /**
     * 后序遍历
     * @returns {null}
     * @constructor
     */
    LRD() {
        if (!this) return null;
        // 先遍历左边
        this.left && this.left.LRD();
        // 遍历右边
        this.right && this.right.LRD();
        // 遍历自己
        console.log(this.value);
    }

    /**
     * 获取一颗二叉树的深度
     * @returns {number}
     */
    getDepth() {
        if (!this) return 0;
        return 1 + Math.max(this.left && this.left.getDepth(), this.right && this.right.getDepth())
    }

    /**
     * 二叉树的深度优先搜索 其实就是二叉树的前序遍历
     * @param target {String} 目标的值
     * @returns {boolean} 结果
     */
    searchByDepth(target = '') {
        if (!this || !target) return false;
        if (this.value === target) return true;
        return !!(this.left && this.left.searchByDepth(target)) || !!(this.right && this.right.searchByDepth(target))

    }

    /**
     * 二叉树的深度优先搜索
     * @param target {String} 搜索的值
     * @returns {boolean} 结果
     */
    searchByWidth(target = "") {
        if (!this || !target) return false;
        let _searchByWidth = (nodeArr = []) => {
            if (nodeArr.length < 1) return false;
            let nextLayer = [];
            for (let i = 0, l = nodeArr.length; i < l; i++) {
                if (nodeArr[i].value === target) return true;
                else {
                    nodeArr[i].left && nextLayer.push(nodeArr[i].left)
                    nodeArr[i].right && nextLayer.push(nodeArr[i].right)
                }
            }
            return _searchByWidth(nextLayer);
        }
        return _searchByWidth([this]);
    }

}

// 前序遍历的结果 A B D E C
// 中序遍历的结果 D B E A C
// 后序遍历的结果 D E B C A
/**
 * 通过前序和中序还原二叉树
 * @param qArr {Array} 前序列表
 * @param zArr {Array} 后序列表
 * @returns {Node|null} 二叉树节点
 */
function getNodeByQZ(qArr, zArr) {
    if (qArr.length !== zArr.length || qArr.length === 0) return null;
    let rootVal = qArr[0], root = new Node(rootVal), rootIndex = zArr.indexOf(rootVal);
    let zLeft = zArr.slice(0, rootIndex), qLeft = qArr.slice(1, rootIndex + 1);
    let zRight = zArr.slice(rootIndex + 1), qRight = qArr.slice(rootIndex + 1);
    root.left = getNodeByQZ(qLeft, zLeft);
    root.right = getNodeByQZ(qRight, zRight);
    return root;
}

// 中序遍历的结果 D B E A C
// 后序遍历的结果 D E B C A
/**
 * 通过中序和后序还原二叉树
 * @param zArr {Array} 中序数组
 * @param hArr {Array} 后序数据
 * @returns {Node|null} 合并的二叉树
 */
function getNodeByZH(zArr, hArr) {
    if (zArr.length !== hArr.length || zArr.length === 0) return null;
    let rootIndex = zArr.indexOf(hArr[hArr.length - 1]), root = new Node(hArr[hArr.length - 1]);
    let zLeft = zArr.slice(0, rootIndex), hLeft = hArr.slice(0, rootIndex);
    let zRight = zArr.slice(rootIndex + 1), hRight = hArr.slice(rootIndex, hArr.length - 1);
    root.left = getNodeByZH(zLeft, hLeft);
    root.right = getNodeByZH(zRight, hRight);
    return root;

}

// 比较两颗二叉树的异同
/**
 * 两颗二叉树的比较异同
 * @param root1 {Node}
 * @param root2 {Node}
 * @returns {[]|*[]}
 */
function diff(root1, root2) {
    let result = []
    if (!root1 && !root2) return [];
    else if (root1 && !root2) result.push({type: '删除', from: root1, to: root2});
    else if (!root1 && root2) result.push({type: '新增', from: root1, to: root2});
    else if (root1.value === root2.value) {
        let leftResult = diff(root1.left, root2.left)
        let rightResult = diff(root1.right, root2.right)
        result = [...result, ...leftResult, ...rightResult];
    } else {
        result.push({type: '更新', from: root1, to: root2})
        let leftResult = diff(root1.left, root2.left)
        let rightResult = diff(root1.right, root2.right)
        result = [...result, ...leftResult, ...rightResult];
    }
    return result;
}

测试:

// 创建一个二叉树
let a = new Node('A');
let b = new Node('B');
let c = new Node('C');
let d = new Node('D');
let e = new Node('E');

a.left = b;
a.right = c;
b.left = d;
b.right = e;

// a.DLR();  // 前序遍历的结果 A B D E C
// a.LDR();  // 中序遍历的结果 D B E A C
// a.LRD();  // 后序遍历的结果 D E B C A
// console.log(a.getDepth()); // 获取的深度 3
// console.log(a.searchByDepth('E')); // true
// console.log(a.searchByDepth('F')); // false
// console.log(a.searchByWidth('E')); // true
// console.log(a.searchByWidth('F')); // false
// console.log(getNodeByQZ(['A', 'B', 'D', 'E', 'C'], ['D', 'B', 'E', 'A', 'C']));
// console.log(getNodeByZH(['D', 'B', 'E', 'A', 'C'], ['D', 'E', 'B', 'C', 'A']));

在这里插入图片描述

let root1 = getNodeByQZ(['A', 'B', 'D', 'E', 'C'], ['D', 'B', 'E', 'A', 'C']);
let root2 = getNodeByQZ(['A', 'B', 'D', 'C', 'F'], ['D', 'B', 'A', 'F', 'C']);
console.log(diff(root1, root2));

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_450375.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?