树形结构
树形结构
树
树是一个类似于链表的二维结构，每个节点可以指向 0 个或多个其他节点
树具有以下特点：
- 单根：如果一个节点 A 指向了另一个节点 B，仅能通过 A 直接找到 B 节点，不可能通过其他节点直接找到 B 节点
- 无环：节点的指向不能形成环
树的术语：
- 结点的度：某个节点的度 = 该节点子节点的数量
- 树的度：一棵树中，最大的节点的度为该树的度
- 结点的层：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推；
- 树的高度或深度：树中结点的最大层次
- 叶子节点：度为 0 的结点称为叶结点；
- 分支节点：非叶子节点
- 子节点、父节点：相对概念，如果 A 节点有一个子节点 B，则 A 是 B 的父节点，B 是 A 的子节点
- 兄弟节点：如果两个节点有同一个父节点，则它们互为兄弟节点
- 祖先节点：某个节点的祖先节点，是从树的根到该节点本身经过的所有节点
- 后代节点：如果 A 是 B 的祖先节点，B 则是 A 的后代节点
树的代码表示法：
function Node(value) {
this.value = value
this.children = []
}
二叉树
如果一颗树的度为 2，则该树是二叉树
二叉树可以用下面的代码表示
function Node(value) {
this.value = value
this.left = null
this.right = null
}
二叉树的相关算法
编写各种函数，实现下面的功能
对二叉树遍历打印
- 前(先)序遍历 DLR
/** * 前序遍历 * @param {*} root */ function DLR(root) { //输出自己 if (!root) { return } console.log(root.value) //输出左边 DLR(root.left) //输出右边 DLR(root.right) }- 中序遍历 LDR
/** * 中序遍历 * @param {*} root */ function LDR(root) { if (!root) { return } //输出左边 LDR(root.left) //输出自己 console.log(root.value) //输出右边 LDR(root.right) }- 后序遍历 LRD
/** * 后续遍历 * @param {*} root */ function LRD(root) { if (!root) { return } // 输出左边 LRD(root.left) // 输出右边 LRD(root.right) // 输出自己 console.log(root.value) }根据前序遍历和中序遍历结果，得到一颗二叉树
/**
* 根据前序遍历和中序遍历的结果，得到一颗二叉树
* @param {Array} dlr 数组
* @param {Array} ldr 数组
*/
function getTree(dlr, ldr) {
//严谨性判断
if (dlr.length !== ldr.length) {
throw new Error('无解')
}
if (dlr.length === 0) {
return null
}
// 正常逻辑
var rootValue = dlr[0] //前序遍历的第一个就是根，得到根的值
var root = new Node(rootValue) //创建根节点
//加左节点
var index = ldr.indexOf(rootValue) //根节点在中序遍历中的索引
var leftLDR = ldr.slice(0, index) //左边的中序遍历结果
var leftDLR = dlr.slice(1, 1 + leftLDR.length) //左边的前序遍历结果
root.left = getTree(leftDLR, leftLDR)
//加右节点
var rightLDR = ldr.slice(index + 1) //右边的中序遍历结果
var rightDLR = dlr.slice(1 + leftLDR.length)
root.right = getTree(rightDLR, rightLDR)
return root
}
- 计算树的深度
/**
* 得到树的深度
* @param {*} root
*/
function getDepth(root) {
if (!root) {
return 0
}
return 1 + Math.max(getDepth(root.left), getDepth(root.right))
}
查询二叉树
- 深度优先 Depth First Search
/** * 深度优先搜索 * 搜索target在树中是否存在 * @param {*} root * @param {*} target */ function searchDeep(root, target) { if (!root) { return false } console.log(root.value) //先看自己 if (root.value === target) { return true //找到了 } // 左边或右边任何一个找到，都行 return searchDeep(root.left, target) || searchDeep(root.right, target) }- 广度优先 Breadth First Search
/** * 广度优先搜索 * 搜索target在树中是否存在 * @param {*} root * @param {*} target */ function searchWide(root, target) { if (!root) { return false } /** * 辅助函数 * @param {*} layer 要搜索的节点数组 */ function _searchWide(layer) { if (layer.length === 0) { return false //这一层没有东西了 } console.log(layer) var nextLayer = [] //下一层的数组 for (var i = 0; i < layer.length; i++) { if (layer[i].value === target) { return true } else { if (layer[i].left) { nextLayer.push(layer[i].left) } if (layer[i].right) { nextLayer.push(layer[i].right) } } } //说明这一层没有希望 return _searchWide(nextLayer) } return _searchWide([root]) }比较两棵二叉树，得到比较的结果
/**
* 得到两颗树的差异
* [
* {type: "修改", from: B, to: T},
* {type: "删除", from: D, to: null},
* {type: "新增", from: null, to: F},
* ]
* @param {*} root1
* @param {*} root2
*/
function diff(root1, root2) {
var result = [] //保存差异结果的数组
if (!root1 && !root2) {
//两棵树都没有节点
return result
}
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) {
//两边的值不一样
result.push({
type: '修改',
from: root1,
to: root2
})
//比较后续
var resultLeft = diff(root1.left, root2.left) //左边的差异
var resultRight = diff(root1.right, root2.right) //右边差异
result = result.concat(resultLeft)
result = result.concat(resultRight)
} else {
//两边一样
//比较后续
var resultLeft = diff(root1.left, root2.left) //左边的差异
var resultRight = diff(root1.right, root2.right) //右边差异
result = result.concat(resultLeft)
result = result.concat(resultRight)
}
return result
}
