数据结构-树(数据结构树和二叉树知识点总结)
树
树是一种非线性结构，它对于存储快速查找的元素非常用有用， 树是一种分层数据的抽象模型
树的相关术语
树结构实现
树的遍历
添加和移除节点
树的相关术语
位于树顶部的节点叫作根节点。它没有父节点。
树中的每个元素都叫作节点.节点分为内部节点和外部节点。至少有一个子节点的节点称为内部节点，没有子元素的节点成为外部节点或叶节点。
节点的深度：取决当前节点去祖先节点的数量。
节点的高度：所有节点深度的最大值
二叉树 & 二叉搜索树（BST树）
二叉树中每个节点最多有个节点，一个是左侧节点，一个是右侧节点
二叉搜索树是二叉树特殊分别，只允许你在左侧存储比父节点小数据，右侧节点存储比父节点大数据
BST实现
insert(key) 向树插入一个新的键
search(key) 在树种搜索key是否存在
remove(key) 删除树种特定的值
min() 寻找树的最小值
max() 寻找树的最大值
preOrderTraverse 先序遍历： 先输出当前节点值，在输出左节点，然后右节点值
middleOrderTraverse 中序遍历： 先输出左侧节点值，在输出当前节点值，然后右节点值
postSequenceTraverse 后续遍历： 先输出左侧节点值，在输出右侧节点值，然后输出当前节点值
class Node { constructor(value) { this.key = value this.left = null this.right = null } } class bstTree { root = null insert(key) { const item = new Node(key) const insertNode = (node, key) => { if (!node) { node = item } if (node.key - key > 0) { node.left = insertNode(node.left, key) } else if (node.key - key < 0) { node.right = insertNode(node.right, key) } return node } if (!this.root) { this.root = item } else { insertNode(this.root, key) } return true } remove(key) { const removeNode = (node, key) => { if (!node) { return null } if (node.key - key > 0) { node.left = removeNode(node.left, key) } else if (node.key - key < 0) { node.right = removeNode(node.right, key) } else { // 找到目标节点 if (node.left === null && node.right === null) { node = null } else if (node.left && node.right === null) { node = node.left } else if (node.right && node.left === null) { node = node.right } else { // 目标节点存在左右节点的话， 保持左树不变，取右树最小节点，并且把右树最小节点删除掉 const rightMin = this.minNode(node.right) node.key = rightMin.key node.right = removeNode(node.right, rightMin.key) } } return node } return removeNode(this.root, key) } search(key) { const searchNode = (node, key) => { if (!node) { return undefined } if (node.key - key > 0) { return searchNode(node.left, key) } else if (node.key - key < 0) { return searchNode(node.right, key) } else { return node } } return searchNode(this.root, key) } // 先序遍历 preOrderTraverse() { let str = '' const loop = (node) => { if (!node) { return } str = `${str} => ${node.key}` loop(node.left) loop(node.right) } loop(this.root) console.log(str) } // 中序遍历 middleOrderTraverse() { const loop = (node) => { if (!node) { return } loop(node.left) console.log(node.key) loop(node.right) } loop(this.root) } // 后序遍历 postSequenceTraverse() { const loop = (node) => { if (!node) { return } loop(node.left) loop(node.right) console.log(node.key) } loop(this.root) } min() { if (!this.root) { return undefined } return this.minNode(this.root) } minNode(node) { let current = node while (current && current.left) { current = current.left } return current } max() { let current = this.root while (current && current.right) { current = current.right } return current } }
作者：levi_m
链接：https://juejin.cn/post/7029614572952649765