【数据结构与算法】二叉树遍历、判断和 diff 算法

遍历

深度优先遍历

function Node(value) {
    this.value = value
    this.left = null
    this.right = null
}

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')
let f  = new Node('f')
let g  = new Node('g')
a.left = c
a.right = b
c.left = f
c.right= g
b.left = d
b.rihgt = e

function deepSearch(root, target) {
    if (root == null) return false
    if (root.value == target) return true
    let left = deepSearch(root.left,target)
    let right = deepSearch(root.right,target)
    return left || right
}

console.log(deepSearch(a, 'c'))

广度优先遍历

function Node(value) {
    this.value = value
    this.left = null
    this.right = null
}

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')
let f = new Node('f')
let g = new Node('g')
a.left = c
a.right = b
c.left = f
c.right = g
b.left = d
b.rihgt = e

function breadthSearch(rootList, target) {
    if (rootList == null || rootList.length == 0) return false
    // 当前层的所有子节点
    let childList = []
    for (let i = 0; i < rootList.length; i++) {
        if (rootList[i] != null && rootList[i].value == target) {
            return true
        } else {
            rootList[i].left && childList.push(rootList[i].left)
            rootList[i].right && childList.push(rootList[i].right)
        }
    }
    return breadthSearch(childList, target)
}

console.log(breadthSearch([a], 'n'))

判断是否相同

普通情况

function Node(value) {
    this.value = value
    this.left = null
    this.right = null
}

let a1 = new Node('a')
let b1 = new Node('b')
let c1 = new Node('c')
let d1 = new Node('d')
let e1 = new Node('e')
let f1 = new Node('f')
let g1 = new Node('g')
a1.left = c1
a1.right = b1
// c1.left = f1
c1.right = g1
b1.left = d1
b1.right = e1
let a2 = new Node('a')
let b2 = new Node('b')
let c2 = new Node('c')
let d2 = new Node('d')
let e2 = new Node('e')
let f2 = new Node('f')
let g2 = new Node('g')
a2.left = c2
a2.right = b2
// c2.left = f2
c2.right = g2
b2.left = d2
b2.right = e2

function compareTree(root1, root2) {
    if (root1 == null && root2 == null) return true
    if (root1 == null || root2 == null) return false
    let leftTree = compareTree(root1.left, root2.left)
    let rightTree = compareTree(root1.right, root2.right)
    return root1.value == root2.value && leftTree && rightTree
}

console.log(compareTree(a1, a2))

特殊情况

子树左右互换也算相同。

function Node(value) {
    this.value = value
    this.left = null
    this.right = null
}

let a1 = new Node('a')
let b1 = new Node('b')
let c1 = new Node('c')
let d1 = new Node('d')
let e1 = new Node('e')
let f1 = new Node('f')
let g1 = new Node('g')
a1.left = c1
a1.right = b1
c1.left = f1
c1.right = g1
b1.left = d1
b1.right = e1
let a2 = new Node('a')
let b2 = new Node('b')
let c2 = new Node('c')
let d2 = new Node('d')
let e2 = new Node('e')
let f2 = new Node('f')
let g2 = new Node('g')
a2.left = b2
a2.right = c2
c2.left = f2
c2.right = g2
b2.left = d2
b2.right = e2

function compareTree(root1, root2) {
    if (root1 == null && root2 == null) return true
    if (root1 == null || root2 == null) return false
    return root1.value == root2.value && compareTree(root1.left, root2.left) && compareTree(root1.right, root2.right)
    || root1.value == root2.value && compareTree(root1.left, root2.right) && compareTree(root1.right, root2.left)
}

console.log(compareTree(a1, a2))

diff 算法

function Node(value) {
    this.value = value
    this.left = null
    this.right = null
}

let a1 = new Node('a')
let b1 = new Node('b')
let c1 = new Node('c')
let d1 = new Node('d')
let e1 = new Node('e')
let f1 = new Node('f')
let g1 = new Node('g')
a1.left = c1
a1.right = b1
c1.left = f1
c1.right = g1
b1.left = d1
b1.right = e1
let a2 = new Node('a')
let b2 = new Node('z')
let c2 = new Node('c')
let d2 = new Node('x')
let e2 = new Node('e')
let f2 = new Node('f')
let g2 = new Node('g')
a2.left = c2
a2.right = b2
c2.left = f2
// c2.right = g2
f2.right = g2
b2.left = d2
b2.right = e2

function diffTree(root1, root2, diffList) {
    if (root1 == null && root2 == null) {
        return diffList
    } else if (root1 == null && root2 != null) {
        diffList.push({type: '新增', origin: null, now: root2});
    } else if (root1 != null && root2 == null) {
        diffList.push({type: '删除', origin: root1, now: null});
    } else if (root1.value != root2.value) {
        diffList.push({type: '修改', origin: root1, now: root2});
        // 判断父节点本身改变，但是子节点并没有改变的情况
        diffTree(root1.left, root2.left, diffList)
        diffTree(root1.right, root2.right, diffList)
    } else {
        diffTree(root1.left, root2.left, diffList)
        diffTree(root1.right, root2.right, diffList)
    }
}
/**
 * 判断树的变化
 * {type: '新增', origin: null, now: c2}
 * {type: '修改', origin: c1, now: c2}
 * {type: '删除', origin: c2, now: null}
 * @type {*[]}
 */
let diffList = []
diffTree(a1, a2, diffList)
console.log(diffList)