站长推荐产品,护栏板销售网站怎么做,虚拟主机app,天猫商城网上购物正品下载树结构
树的特点
树通常有一个根。连接着根的是树干树干到上面之后会进行分叉成树枝#xff0c;树枝还会分又成更小的树枝在树枝的最后是叶子
树的抽象
树可以模拟生活中的很多场景#xff0c;比如#xff1a;公司组织架构、家谱、DOM Tree、电脑文件夹架构 优秀的哈希函…树结构
树的特点
树通常有一个根。连接着根的是树干树干到上面之后会进行分叉成树枝树枝还会分又成更小的树枝在树枝的最后是叶子
树的抽象
树可以模拟生活中的很多场景比如公司组织架构、家谱、DOM Tree、电脑文件夹架构 优秀的哈希函数补充 快速计算霍纳法则均匀分布质数长度、幂的底 数据结构对比
数组
优点 数组的主要优点是根据 下标值访问 效率会很高但是如果我们希望根据元素来查找对应的位置呢比较好的方式先对数组进行排序再进行二分查找 缺点 需要 先对数组进行排序生成有序数组才能提高查找效率另外数组和插入和删除数据时需要有大量的位移操作插入到首位或者中间位置的时候效率很低
链表
优点 链表的插入和删除操作效率都很高 缺点 查找效率很低需要从头开始依次访问链表中的每个数据项直到找到而且即使插入和删除操作操作效率很高但是如果要插入和删除中间位置的数据还是需要从头先找到对应的数据
哈希表
优点 哈希表的插入、查询、删除效率都是非常高的 缺点 空间利用率不高底层使用的数组并且某些单元是没有被利用的哈希表中的元素是无序的不能安装固定的顺序来遍历哈希表中的元素不能快速的找出哈希表中的 最大值或最小值 这些特殊的值
树
不能说树结构比其他结构都要好因为 每种数据结构都有自己的特定的应用场景但是树确实综合了上面的数据结构的优点并且弥补了上面数据结构的缺点
而且模拟某些场景我们使用树结构会更加方便
因为数结构的非线性可以表示一对多的关系比如文件的目录结构
树的术语
不过大部分术语都与真实世界的树相关或者和家庭关系相关(如父节点和子节点)
树Treenn0个节点构成的有限集合
当 n0 时称为空树
对于任一颗非空树n0它具备以下性质
树中有一个称为 “根Root” 的特殊节点用 r 表示其余节点可分为 mm0个互不相交的有限集 T1、T2…Tm其中每个集合本身又是一棵树称为原来数的 “子树SubTree” 节点的度Degree节点的子树个数树的度Degree树的所有节点的最大度数叶节点Leaf度为 0 的节点也称为叶子节点父节点Parent有子树节点时其子树的根节点的父节点子节点Child若 A 节点是 B 节点的父节点则称 B 节点是 A 节点的子节点子节点也称孩子节点兄弟节点Sibling具有同一父节点的各节点彼此是兄弟节点路径和路径长度从节点 n1 到 nk 的路径为一个节点序列 n1、n2…nk ni 是 n(i1) 的父节点路径所包含边的个数为路径的长度 节点的层次Level规定节点在 1 层其它任一节点的层数是其父节点的层数1树的深度Depth树中所有节点中的最大层次是这棵树的深度
表示方法 所有的数本质上都可以使用二叉树模拟出来 二叉树
二叉树分类
如果树中每个节点 最多只能有两个子节点这样的数就称为 “二叉树”
二叉树可以为空也就是没有节点若不为空则它是由根节点和称为其 左子树TL 和 右子树TR 的两个不相交的二叉树组成 二叉树有几个比较重要的特性笔试题中比较常见
一颗二叉树第 i 层的最大节点树为2^(i-1), i1深度为 k 的二叉树有最大节点总数为2^k-1, k1对任何非空二叉树 T若 n0 表示叶子点的个数n2 是度为 2 的非叶节点个数那么两者满足关系 n0n21
完美二叉树Perfect Binary Tree也称满二叉树Full Binary Tree
在二叉树中除了下一层的叶节点外每层节点都有 2 个子节点就构成了满二叉树 完全二叉树Complete Binary Tree
除二叉树最后一层外其它各层的节点个数都达到最大个数最后一层从左到右的叶节点连续存在只缺右侧若干节点完美二叉树是特殊的完全二叉树 二叉树存储
二叉树的存储常见的方式是数组和链表 二叉树最常见的方式还是使用链表存储
每个节点封装成一个 NodeNode 中包含存储的数据左节点的引用右节点的引用 二叉搜索树
二叉搜索树BSTBinary Search Tree也称二叉排序树或二叉查找树
二叉搜索树是一颗二叉树可以为空如果不为空满足以下性质
非空左子树的所有键值小于根节点的键值非空右子树的所有键值大于其根节点的键值左、右子树本身也都是二叉搜索树 这种方式就是二分查找的思想
查找所需的最大次数等于二叉搜索树的深度插入节点也利用类似的方法一层层比较大小找到新节点合适的位置
封装二叉搜索树
常见操作
插入操作
insert(value)向树中插入一个新的数据
查找操作
search(value)在树中查找一个数据如果节点存在则返回 true如果不存在则返回 falsemin返回树中最小的值/数据max返回树中最大的值/数据
遍历操作
inOrderTraverse通过中序遍历方式遍历所有节点preOrderTraverse通过先序遍历方式遍历所有节点postOrderTraverse通过后序遍历方式遍历所有节点levelOrderTraverse通过层序遍历方式遍历所有节点
删除操作
remove(value)从树中移除某个数据
插入数据
插入其他节点时我们需要判断该值到底是插入到左边还是插入到右边判断的依据来自于新节点的 value 和原来节点的 value 值的比较 如果新节点的 newValue 小于原节点的 oldValue那么就向左边插入如果新节点的 newValue 大于原节点的 oldValue那么就向右插入 代码1位置就是准备向左子树插入数据但是它本身有分成两种情况 情况一左子树上原来没有内容那么直接插入即可情况二左子树上已经有了内容那么久一次向下继续查找新的走向所以使用递归调用即可 代码2位置和代码1位置几乎逻辑是相同的只是去向右查找 情况一左右树上原来没有内容那么直接插入即可情况二右子树上已经有了内容那么就一次向下继续查找新的走向所以使用递归调用即可
class BSTreeT {private insertNode(node: TreeNodeT, newNode: TreeNodeT) {// 代码1if (newNode.value node.value) {// 去左边继续查找空白位置if (node.left null) {node.left newNode} else {this.insertNode(node.left, newNode)}// 代码2} else {// 去右边继续查找空白位置if (node.right null) {node.right newNode} else {this.insertNode(node.right, newNode)}}}
}遍历数据
遍历一棵树是指访问树的每个节点也可以对每个节点进行某些操作我们这里就是简单的打印但是树和线性结构不太一样线性结构我们通常按照从前到后的顺序遍历但是树呢应该从树的顶端还是底端开始呢从左开始还是从右开始呢
二叉树遍历常见的四种方式
先序遍历中序遍历后序遍历层序遍历 先序/中序/后序取决于访问根节点root的时机
在所有的树结构中包括子树都是如此
先序遍历
优先访问根节点之后访问左子树最后访问右子树 递归版本
class TreeNodeT extends NodeT {preOrderTraverse() {this.preOrderTraverseNode(this.root)}private preOrderTraverseNode(node: TreeNodeT | null) {if (node) {console.log(node.value)this.preOrderTraverseNode(node.left)this.preOrderTraverseNode(node.right)}}
}非递归版本
class TreeNodeT extends NodeT {preOrderTraversalNoRecursion() {let stack: TreeNodeT[] []let current: TreeNodeT | null this.rootwhile (current ! null || stack.length ! 0) {while (current ! null) {console.log(current.value)stack.push(current)current current.left}current stack.pop()!current current.right}}
}中序遍历
优先访问左子树之后访问根节点最后访问右子树 递归版本
class TreeNodeT extends NodeT {inOrderTraverse() {this.inOrderTraverseNode(this.root)}private inOrderTraverseNode(node: TreeNodeT | null) {if (node) {this.inOrderTraverseNode(node.left)console.log(node.value)this.inOrderTraverseNode(node.right)}}
}非递归版本
class TreeNodeT extends NodeT {inOrderTraversalNoRecursion() {let stack: TreeNodeT[] []let current: TreeNodeT | null this.rootwhile (current ! null || stack.length ! 0) {while (current ! null) {stack.push(current)current current.left}current stack.pop()!console.log(current.value)current current.right}}
}后序遍历
优先访问左子树之后访问右子树最后访问根节点 递归版本
class TreeNodeT extends NodeT {postOrderTraverse() {this.postOrderTraverseNode(this.root)}private postOrderTraverseNode(node: TreeNodeT | null) {if (node) {this.postOrderTraverseNode(node.left)this.postOrderTraverseNode(node.right)console.log(node.value)}}
}非递归版本
class TreeNodeT extends NodeT {preOrderTraversalNoRecursion() {let stack: TreeNodeT[] []let current: TreeNodeT | null this.rootwhile (current ! null || stack.length ! 0) {while (current ! null) {console.log(current.value)current current.left}current stack.pop()!stack.push(current)current current.right}}
}层序遍历
层序遍历很好理解就是从上向下逐层遍历
层序遍历通常我们会借助队列来完成
也是队列的一个经典应用场景 class TreeNodeT extends NodeT {levelOrderTraverse() {// 1.如果没有根节点那么不需要遍历if (!this.root) return// 2.创建队列结构const queue: TreeNodeT[] []queue.push(this.root)// 3.遍历队列中所有的节点依次出队while (queue.length) {// 3.1.访问节点的过程const current queue.shift()!console.log(current.value)// 3.2.将左子节点放入队列if (current.left) {queue.push(current.left)}// 3.3.将右子节点放入到队列if (current.right) {queue.push(current.right)}}}
}最值
在二叉搜索树中搜索最值是一件非常简单的事情其实用眼睛就可以看出来了 class TreeNodeT extends NodeT {/** 获取最值操作最大值 */getMaxValue(): T | null {let current this.rootwhile (current current.right) {current current.right}return current?.value ?? null}/** 获取最值操作最小值 */getMinValue(): T | null {let current this.rootwhile (current current.left) {current current.left}return current?.value ?? null}
}搜索特定的值
二叉搜索树不仅仅获取最值效率非常高搜索特定的值效率也非常高
注意这里的实现返回 boolean 类型即可
class TreeNodeT extends NodeT {searchNoRecursion(value: T): boolean {let current this.rootwhile (current) {// 找到了节点if (current.value value) return trueif (current.value value) {current current.right} else {current current.left}}return false}search(value: T): boolean {return this, this.searchNode(this.root, value)}searchNode(node: TreeNodeT | null, value: T): boolean {// 1.如果节点为null那么就直接退出递归if (node null) return false// 2.判断node节点的value和传入的value的大小if (node.value value) {return this.searchNode(node.left, value)} else if (node.value value) {return this.searchNode(node.right, value)} else {return true}}
}删除操作
二叉搜索树的删除有些复杂我们一点点完成
删除节点要从查找到删除的节点开始找到节点后需要考虑三种情况
该节点是叶节点没有子节点比较简单该节点有一个子节点相对简单该节点有两个子节点情况复杂
我们先从查找要删除的节点入手
先找到要删除的节点找到要删除节点 删除叶子节点删除只有一个子节点删除有两个子节点的节点
class TreeNodeT extends NodeT {left: TreeNodeT | null nullright: TreeNodeT | null nullparent: TreeNodeT | null nullget isLeft(): boolean {return !!(this.parent this.parent.left this)}get isRight(): boolean {return !!(this.parent this.parent.right this)}
}class TreeNodeT extends NodeT {private searchNode(value: T): TreeNodeT | null {let current this.rootlet parent: TreeNodeT | null nullwhile (current) {if (current.value value) return currentparent currentif (current.value value) {current current.right} else {current current.left}if (current) current.parent parent}return null}
}情况一没有子节点
这种情况相对比较简单我们需要检测 current 的 left 以及 right 是否都为 null都为 null 之后还要检测一个东西就是是否 current 就是根都为 null并且为根那么相当于清空了根因为只有它否则就把父节点的 left 或者 right 字段设置为 null 即可
如果只有一个单独的根直接删除即可
如果是叶节点那么处理方式如下
class TreeNodeT extends NodeT {remove(value: T): boolean {// 1.搜索当前是否有这个valueconst current this.searchNode(value)if (!current) return false// 2.获取到三个东西当前节点/父节点是否属于父节点的左子节点还是右子节点// 2.1.如果删除的是叶子节点if (current.left null current.right null) {if (current this.root) {// 根节点this.root null} else if (current.isLeft) {// 父节点的左子节点current.parent!.left null} else {current.parent!.right null}}return true}
}情况二一个子节点
这种情况也不是很难要删除的 current 节点只有 2 个连接如果有两个子节点就是三个连接了一个连接父节点一个连接唯一的子节点需要从这三者之间爷爷-自己-儿子将自己current剪断让爷爷直接连接儿子即可这个过程要求改变父节点的 left 或者 right指向要删除节点的子节点当然这个过程中还要考虑是否 current 就是根
class TreeNodeT extends NodeT {remove(value: T): boolean {if (current.right null) {// 2.2.只有一个子节点只有左子节点if (current this.root) {this.root current.left} else if (current.isLeft) {current.parent!.left current.left} else {current.parent!.right current.left}} else if (current.left null) {// 2.3.只有一个子节点只有右子节点if (current this.root) {this.root current.right} else if (current.isLeft) {current.parent!.left current.right} else {current.parent!.right current.right}}return true}
}情况三两个节点 情况一删除 9 节点 处理方式相对简单将 8 位置替换到 9或者将 10 位置替换到 9注意这里是替换也就是 8 位置替换到 9 时7 指向 8而 8 还需要指向 10找 8 或 10 情况二删除 7 节点 一种方式是将 5 拿到 7 的位置3 依然指向 5但是 5 有一个 right需要指向 9依然是二叉搜索树另一种方式是在右侧找一个找 8也就是将 8 替换到 7 的位置8 的 left 指向 5right 指向 9依然是二叉搜索树找 5 或 8 情况三删除 15 节点并且我希望也在右边找 18 替换 15 的位置20 的 left 指向 19也是一个二叉搜索树找 14 或 18
class TreeNodeT extends NodeT {private getSuccessor(delNode: TreeNodeT) {// 获取右子树let current delNode.rightlet successor: TreeNodeT | null nullwhile (current) {successor currentcurrent current.leftif (current) {current.parent successor}}// 拿到后继节点if (successor ! delNode.right) {successor!.parent!.left successor!.rightsuccessor!.right delNode.right}// 将删除节点的 left赋值给后继节点的 leftsuccessor!.left delNode.leftreturn successor}remove(value: T): boolean {else {// 2.4.两个子节点const successor this.getSuccessor(current)if (current this.root) {this.root successor} else if (current.isLeft) {current.parent!.left successor} else {current.parent!.right successor}}return true}
}寻找规律
如果我们要 删除的节点有两个子节点甚至子节点还有子节点这种情况下我们需要 从下面的子节点中找到一个子节点来替换当前的节点
但是找到这个节点有什么特征呢应该是 current 节点下面所有节点中 最接近 current 节点 的
要么比 current 节点小一点点要么比 current 节点大一点点总结你最接近 current你就可以用来替换 current 的位置
这个节点怎么找呢
比 current 小一点点的节点一定是 current 左子树的最大值比 current 大一点点的节点一定是 current 右子树的最小值
前驱和后继
在二叉搜索树中这两个特别的节点有两个特别的名字比 current 小一点点的节点称为 current 节点的 前驱比 current 大一点点的节点称为 current 节点的 后继
也就是为了能够删除有两个子节点的 current要么找到它的前驱要么找到它的后继
class TreeNodeT extends NodeT {remove(value: T): boolean {// 1.搜索当前是否有这个valueconst current this.searchNode(value)if (!current) return false// 2.获取到三个东西当前节点/父节点是否属于父节点的左子节点还是右子节点let replaceNode: TreeNodeT | null nullif (current.left null current.right null) {// 2.1.如果删除的是叶子节点replaceNode null} else if (current.right null) {// 2.2.只有一个子节点只有左子节点replaceNode current.left} else if (current.left null) {// 2.3.只有一个子节点只有右子节点replaceNode current.right} else {// 2.4.两个子节点const successor this.getSuccessor(current)replaceNode successor}if (current this.root) {this.root replaceNode} else if (current.isLeft) {current.parent!.left replaceNode} else {current.parent!.right replaceNode}return true}
}删除操作非常复杂一些程序员都尝试着避开删除操作
他们的做法是在 Node 类中添加一个 boolean 字段比如名称为 isDeleted要删除一个节点时就将此字段设置为 true其他操作比如 find() 在查找之前先判断这个节点是不是标记为删除这样相对比较简单每次删除节点不会改变原有的树结构但是在二叉树的存储中还保留这那些本已经被删除掉的节点
完整代码
import { btPrint } from hy-algokitclass INodeT {value: Tconstructor(value: T) {this.value value}
}
class TreeNodeT extends NodeT {left: TreeNodeT | null nullright: TreeNodeT | null nullparent: TreeNodeT | null nullget isLeft(): boolean {return !!(this.parent this.parent.left this)}get isRight(): boolean {return !!(this.parent this.parent.right this)}
}
class BSTreeT {private root: TreeNodeT | null nullprint() {btPrint(this.root)}private searchNode(value: T): TreeNodeT | null {let current this.rootlet parent: TreeNodeT | null nullwhile (current) {if (current.value value) return currentparent currentif (current.value value) {current current.right} else {current current.left}if (current) current.parent parent}return null}/** 插入数据的操作 */insert(value: T) {// 1.根据传入value创建Node(TreeNode)节点const newNode new TreeNode(value)// 2.判断当前是否已经有了根节点if (!this.root) {// 当前树为空this.root newNode} else {// 树中已经有其他值this.insertNode(this.root, newNode)}}private insertNode(node: TreeNodeT, newNode: TreeNodeT) {if (newNode.value node.value) {// 去左边继续查找空白位置if (node.left null) {node.left newNode} else {this.insertNode(node.left, newNode)}} else {// 去右边继续查找空白位置if (node.right null) {node.right newNode} else {this.insertNode(node.right, newNode)}}}// 遍历的操作/** 先序遍历 */preOrderTraverse() {this.preOrderTraverseNode(this.root)}private preOrderTraverseNode(node: TreeNodeT | null) {if (node) {console.log(node.value)this.preOrderTraverseNode(node.left)this.preOrderTraverseNode(node.right)}}/** 中序遍历 */inOrderTraverse() {this.inOrderTraverseNode(this.root)}private inOrderTraverseNode(node: TreeNodeT | null) {if (node) {this.inOrderTraverseNode(node.left)console.log(node.value)this.inOrderTraverseNode(node.right)}}/** 后序遍历 */postOrderTraverse() {this.postOrderTraverseNode(this.root)}private postOrderTraverseNode(node: TreeNodeT | null) {if (node) {this.postOrderTraverseNode(node.left)this.postOrderTraverseNode(node.right)console.log(node.value)}}/** 层序遍历 */levelOrderTraverse() {// 1.如果没有根节点那么不需要遍历if (!this.root) return// 2.创建队列结构const queue: TreeNodeT[] []queue.push(this.root)// 3.遍历队列中所有的节点依次出队while (queue.length) {// 3.1访问节点的过程const current queue.shift()!console.log(current.value)// 3.2将左子节点放入队列if (current.left) {queue.push(current.left)}// 3.3将右子节点放入到队列if (current.right) {queue.push(current.right)}}}/** 获取最值操作最大值 */getMaxValue(): T | null {let current this.rootwhile (current current.right) {current current.right}return current?.value ?? null}/** 获取最值操作最小值 */getMinValue(): T | null {let current this.rootwhile (current current.left) {current current.left}return current?.value ?? null}/** 搜索特定的值 */search(value: T): boolean {return !!this.searchNode(value)}searchNodeValue(node: TreeNodeT | null, value: T): boolean {// 1.如果节点为null那么就直接退出递归if (node null) return false// 2.判断node节点的value和传入的value的大小if (node.value value) {return this.searchNodeValue(node.left, value)} else if (node.value value) {return this.searchNodeValue(node.right, value)} else {return true}}/** 删除操作 */private getSuccessor(delNode: TreeNodeT) {// 获取右子树let current delNode.rightlet successor: TreeNodeT | null nullwhile (current) {successor currentcurrent current.leftif (current) {current.parent successor}}// 拿到后继节点if (successor ! delNode.right) {successor!.parent!.left successor!.rightsuccessor!.right delNode.right}// 将删除节点的 left赋值给后继节点的 leftsuccessor!.left delNode.leftreturn successor}remove(value: T): boolean {// 1.搜索当前是否有这个valueconst current this.searchNode(value)if (!current) return false// 2.获取到三个东西当前节点/父节点是否属于父节点的左子节点还是右子节点let replaceNode: TreeNodeT | null nullif (current.left null current.right null) {// 2.1.如果删除的是叶子节点replaceNode null} else if (current.right null) {// 2.2.只有一个子节点只有左子节点replaceNode current.left} else if (current.left null) {// 2.3.只有一个子节点只有右子节点replaceNode current.right} else {// 2.4.两个子节点const successor this.getSuccessor(current)replaceNode successor}if (current this.root) {this.root replaceNode} else if (current.isLeft) {current.parent!.left replaceNode} else {current.parent!.right replaceNode}return true}
}平衡树
二叉搜索树缺陷
二叉搜索树作为数据存储的结构有重要的优势
可以快速地找到给定关键字的数据项并且可以快速地插入和删除数据项
但是二叉搜索树有一个很麻烦的问题
如果插入的数据是有序的数据比如下面的情况有一颗初始化为 9、8、12 的二叉树插入下面的数据7、6、5、4、3
非平衡树
比较好的二叉搜索树数据应该是 左右分布均匀 的但是插入 连续数据 后分布的不均匀称这种树为非平衡树对于一颗平衡二叉树来说插入/查找等操作的效率是 O(logN)对于一颗非平衡二叉树相当于编写了一个链表查找效率变成了 O(N) 平衡性
为了能以较快的时间 O(log N)来操作一棵树我们需要保证树总是平衡的
至少大部分是平衡的那么时间复杂度也是接近 O(logN) 的也就是说树中 每个节点左边的子孙节点的个数应该尽可能的等于 右边的子孙节点的个数
AVL 树
AVL 树是最早的一种平衡树它有些办法保证树的平衡每个节点存储了一个额外的数据因为 AVL 树是平衡的所以时间复杂度也是 O(logN)但是每次插入/删除操作相对于红黑树效率都不高所以整体效率不如红黑树
红黑树
红黑树也通过一些特性来保持树的平衡因为是平衡树所以时间复杂度也是 O(logN)另外插入/删除等操作红黑树的性能要优于 AVL 树所以现在平衡树的应用基本都是红黑树
