遍历
深度优先遍历
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)