菜单 搜索
首页 前端知识 typescript常见数据结构与算法

typescript常见数据结构与算法

2024-05-19 09:05:32 前端知识 前端哥 347 676 我要收藏

吸取了之前刷题的教训，近期系统的学习了下数据结构，并理解性的对常用的数据结构进行封装，颇有收获。
期间所写的代码已上传至github：sunshine-fan/ts-data-structure-arithmetic: 封装一些常用的数据结构以及一些算法题解 (github.com)，后续对一些算法题的题解也会陆陆续续上传至该仓库。

线性结构

image-20230304150922862

1.数组

数组（Array）结构是一种重要的数据结构
  1. 原生数据结构
  2. 可以借助数组结构来实现其他的数据结构,比如栈（Stack）、队列（Queue）、堆（Heap）
通常数组的内存是连续的，所以数组在知道下标值的情况下，访问效率是比较高的
数组的缺点：
  1. 数组的创建通常需要申请一段连续的内存空间(一整块的内存)，并且大小是固定的(大多数编程语言数组都是固定的)，所以当当前数组不能满足容量需求时，需要扩容。 (一般情况下是申请一个更大的数组，比如2倍。 然后将原数组中的元素复制过去)
  2. 而且在数组开头或者中间位置插入数据的成本很高，需要大量元素位移
  3. 尽管javascript的Array底层可以帮我们做这些事，但背后的原理依然是这样。

数组的各种用法（MDN): https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array

2.栈结构

栈（stack），它是一种受限的线性结构，后进先出(LIFO)
实现栈结构有两种比较常见的方式
  1. 基于数组实现
  2. 基于链表实现
基于数组实现栈结构
class stack<T>{
  private arr:T[] = [] 
  //压入栈
  push(ele:T){
    this.arr.push(ele) 
  }
  //栈顶元素弹出栈
  pop():T|undefined{
    return this.arr.pop()
  }
  //查看栈顶元素
  peek():T{
    return this.arr[this.arr.length-1]
  }
  //栈是否为空
  isEmpty():boolean{
    return this.arr.length === 0
  }
  //栈长度
  size():number{
    return this.arr.length
  }
}
export default stack; 
复制
测试（代码已上传至github）
  1. 十进制转二进制
  2. 有效的括号

2.队列结构

队列(Queue)，它是一种受限的线性表，先进先出(FIFO First In First Out)
  1. 受限之处在于他只允许在队列前端进行删除操作
  2. 而在队列的后端进行插入操作

image-20230304153724645

队列跟栈一样，有两种实现方案
  1. 基于数组实现
  2. 基于链表实现
基于数组实现队列Queue
// 定义队列方法接口
interface IQueue<T>{
  //入队
  enqueue(ele:T):void;
  //出队
  dequeue():T  | undefined;
  // 查看队头元素
  peek():T|undefined;
  //队列是否为空
  isEmpty():boolean;
  //队列长度
  size():number;
}
// 队列结构实现
class ArrayQueue<T> implements IQueue<T>{
  private arr:T[]=[];
  enqueue(ele: T): void {
    this.arr.push(ele);
  }
  dequeue(): T | undefined {
    return this.arr.shift();
  }
  peek(): T | undefined {
     return this.arr[0];
  }
  isEmpty(): boolean {
    return this.arr.length===0;
  }
  size(): number {
     return this.arr.length;
  }
 
}
export default ArrayQueue
 
复制
测试（代码已上传至github）

击鼓传花

约瑟夫环

3.链表结构

链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。
链表的优势
  1. 相对于数组，内存空间不是连续的，可以充分利用计算机的内存，实现灵活的内存动态管理
  2. 链表不必在创建时就确定大小，并且大小可以无限的延伸下去。
  3. 链表在插入和删除数据时，时间复杂度可以达到O(1),相对数组效率高很多
相对于数组链表的一些缺点
  1. 链表访问任何一个位置的元素时，都需要从头开始访问。(无法跳过第一个元素访问任何一个元素)。
  2. 无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的元素
链表结构的封装
class Node<T>{
  value:T
  next:Node<T> | null = null
  constructor(value:T){
    this.value = value
  }
}
//创建LinkedList的类
class LinkedList<T>{
  private head:Node<T> | null = null
  private size:number = 0
  //根据元素位置获取当前元素节点
  private getNode(position:number):Node<T> | null{
    let index = 0
    let current = this.head
    while(index++<position && current){
      current = current.next
    }
    return current
  }
    
  get length(){
    return this.size
  }
  
  //链表添加操作
  append(value:T){
    const node = new Node(value)
    const head = this.head
    if(!head){
      this.head = node
      this.size++
      return this.head
    }else{
      let current:Node<T> | null = head
      while(current.next){
        current = current!.next
      }
      current.next = node
      this.size++
      return current
    }
  }
    
  //插入操作 引出了Node节点的位置属性
  insert(value:T,position:number):boolean{
    //判断越界问题
    if(position<0 || position>this.size) return false;
    const newNode = new Node(value)
    //判断当前插入是否是第一个节点
    let current = this.head
    if(position===0){
      newNode.next = current
      //head也是一个节点
      this.head = newNode
    }else{
      let previous = this.getNode(position-1)
      //记录前一个节点
      newNode.next = previous!.next
      previous!.next = newNode
    }
    this.size++
    //默认返回
    return true;
  }
    
  //删除链表中指定位置元素
  removeAt(position:number):boolean{
    if(position<0||position>this.size) return false
    let current = this.head;
    if(position===0){
      current = null
    }else{
     current = this.getNode(position-1)
     current!.next = current?.next?.next??null
    }
    this.size--;
    return true;
  }
    
  //过去对应位置的元素
  get(position:number):T|null{
    if(position<0||position>this.size) return null
    let current = this.head
    let index = 0
    while(index++<position&&current){
      current= current.next
    }
    return current?.value??null
  }
    
  //遍历链表
  traverse(){
    if(!this.head) return null
    let current:Node<T> | null = this.head
    let str =""
    while(current){
      str+=current.value+"-->"
      current = current.next
    }
    return str+"null"
  }
    
  //修改某个位置的元素
  update(element:T,position:number){
    if(position<0||position>this.size) return
    //获取节点
    const current = this.getNode(position)
    if(current){
      current.value = element
    }
  }
}
 
const list =new LinkedList()
list.append(1)
list.append(2)
list.append(3)
list.insert(9,2)
list.insert(8,4)
console.log(list.traverse());
console.log(list.removeAt(2)); //删除操作
console.log(list.traverse());
console.log(list.get(3)); //8 
export {Node,LinkedList}
复制
数组与链表的复杂度对比

image-20230304161459741

数组是一种连续的存储结构，通过下标可以直接访问数组中的任意元素。
  1. 时间复杂度：对于数组，随机访问时间复杂度为O(1)，插入和删除操作时间复杂度为O(n)。
  2. 空间复杂度：数组需要连续的存储空间，空间复杂度为O(n)。

链表是一种链式存储结构，通过指针链接起来的节点组成，访问链表中元素需要从头结点开始遍历。

  1. 时间复杂度：对于链表，随机访问时间复杂度为O(n)，插入和删除操作时间复杂度为O(1)。
  2. 空间复杂度：链表需要为每个节点分配存储空间，空间复杂度为O(n)。

在实际开发中，选择使用数组还是链表需要根据具体应用场景来决定。

  1. 如果数据量不大，且需要频繁随机访问元素，使用数组可能会更好。
  2. 如果数据量大，或者需要频繁插入和删除元素，使用链表可能会更好
删除Node节点（给定一个节点）
class listNode{
  val:number
  next:listNode|null
  constructor(val?:number,next?:listNode|null){
    this.val = val===undefined?0:val
    this.next = next===undefined?null:next
  }
}
// 将后一个节点的值赋予，当前要删除的节点，并将当前删除的节点的指向后一个节点，
// 做到替换删除
function deleteNode(node:listNode|null):void{
  node!.val =  node!.next!.val
  node!.next = node!.next!.next
}
let node = new listNode(1)
let current = node
for(var i =3;i<5;i++){
  current.next = new listNode(i)
  current = current.next
}
console.log(node);
deleteNode(node.next)
console.log(node);
 
export {listNode}
复制
反转链表

listNode.ts

class listNode{
  val:number
  next:listNode|null
  constructor(val?:number,next?:listNode|null){
    this.val = val===undefined?0:val
    this.next = next===undefined?null:next
  }
}
export {listNode}
复制
栈结构实现
import {listNode} from './listNode'
 
function reverseList(head:listNode | null): listNode|null {
  if(!head || head.next===null) return head
  //栈结构 加大了空间复杂度
  let stack:listNode[] = []
  while(head){
    stack.push(head)
    head = head.next  
  }
  let newHead:listNode = stack.pop()!
  let newHeadCurrent= newHead
  while(stack.length>0){
    newHeadCurrent.next = stack.pop()!
    newHeadCurrent = newHeadCurrent.next
  }
  newHeadCurrent.next = null 
  return newHead;
}
 
//todo 创建链表结构
let node = new listNode(1)
let current = node
for(var i =3;i<5;i++){
  current.next = new listNode(i)
  current = current.next
}
console.log("反转前"+node);
console.log("反转后"+reverseList(node));
复制
循环实现
import {listNode} from './listNode'
 
function reverseList(head:listNode | null): listNode|null {
  if(!head || head.next===null) return head
  let newHead:listNode|null = null
  let current:listNode | null;
  while(head){
    current= head.next
    head.next = newHead
    newHead = head
    head = current
  }
  return newHead;
}
 
//todo 创建链表结构
let node = new listNode(1)
let current = node
for(var i =3;i<5;i++){
  current.next = new listNode(i)
  current = current.next
}
console.log("反转前");
console.log(node);
console.log("反转后");
console.log(reverseList(node));
 
复制

递归实现

import {listNode} from './listNode'
 
function reverseList(head:listNode | null): listNode|null {
  if(!head || head.next===null) return head
  let newHead = reverseList(head.next)
  head.next.next = head
  head.next = null
  return newHead
} 
 
//todo 创建链表结构
let node = new listNode(1)
let current = node
for(var i =3;i<5;i++){
  current.next = new listNode(i)
  current = current.next
}
console.log("反转前");
console.log(node);
console.log("反转后");
console.log(reverseList(node));
复制

4.哈希表(HashTable)

哈希表到底是什么呢

它的结构就是数组，但是它神奇的地方在于对数组下标值的一种变换，这种变换我们可以使用哈希函数，通过哈希函数可以获取到HashCode。

image-20230304162109978

哈希表的一些概念（由于hashtable的概念较多，本文不在罗列了，详情可以看下述文章）

javascript hash是什么-js教程-PHP中文网

哈希表通常是基于数组进行实现的，但是相对于数组，它也很多的优势
  1. 它可以提供非常快速的插入-删除-查找操作；
  2. 无论多少数据，插入和删除值都接近常量的时间：即O(1)的时间复杂度。实际上，只需要几个机器指令即可完成；
  3. 哈希表的速度比树还要快，基本可以瞬间查找到想要的元素；
  4. 哈希表相对于树来说编码要容易很多；
哈希表相对于数组的一些不足
  1. 哈希表中的数据是没有顺序的，所以不能以一种固定的方式(比如从小到大)来遍历其中的元素（没有特殊处理情况下）。
  2. 通常情况下，哈希表中的key是不允许重复的，不能放置相同的key，用于保存不同的元素。
  3. 空间利用率不高，底层使用的是数组，并且某些单元是没有被利用的
  4. 不能快速的找出哈希表中的最大值或者最小值这些特殊的值
创建哈希表结构
class HashTable<T=any>{
  storage:[string,T][][] = []
  //定义数组的长度
  private limit:number =7
  //记录已经存在元素的个数
  private count:number=0
  //hash函数
  private hashFunc(key:string,max:number):number{
    let hashCode = 0
    const length =key.length
    for(let i=0;i<length;i++){
      // 霍纳法则计算hashCode
      hashCode = 31*hashCode+key.charCodeAt(i)
    }
    //求出索引值
    const index= hashCode % max
    return index    
  }
  //扩容的质数
  private isPrime(num:number){
    const temp = Math.floor(Math.sqrt(num))
    for(let i = 2; i <= temp; i++){
      if(num % i){
        return false
      }
    }
    return true
  }
  //获取一个质数为容量
  private getPrime(num:number){
    let prime = num
    while(!this.isPrime){
      prime++
    }
    return prime
  }
  //插入元素
  put(key:string,value:T){
    let index = this.hashFunc(key,this.limit)
    //取出索引位置对应位置的数组（桶）
    let bucket = this.storage[index]
    //3.判断桶内是否存在值
    if(!bucket){  
      bucket = []
      this.storage[index] =bucket
    }
    //4.确定已经有一个数组了，但是数组中是否已经存在key（判断是否存在）
    let isUpdate = false
    for(let i=0;i<bucket.length;i++){
      const tuple = bucket[i]
      const tupleKey = tuple[0]
      if(tupleKey===key){
        //更新的操作 
        tuple[1] = value
        isUpdate=true
      }
    }
    // 如果桶中没有该元素，就直接加入桶中
    if(!isUpdate){
      bucket.push([key,value])
      this.count++
      //判断数组是否扩容
      if(this.count>this.limit*0.75){
        const primeNum = this.getPrime(Math.floor(this.limit*2))
        this.resize(primeNum)
      }
    }
  }
  //获取元素
  get(key:string){
    //生成对应的key值
    const index = this.hashFunc(key,this.limit)
    //根据索引获取桐bucket
    const bucket = this.storage[index]
    if(!bucket) return null
    //3.遍历桶中的数据
    for(let i =0;i<bucket.length;i++){
      const tuple = bucket[i]
      if(tuple[0] === key){
        return tuple[1]
      }
    }
    return null
  }
  //删除数据
  delete(key:string){
    //生成对应的key值
    const index = this.hashFunc(key,this.limit)
    //根据索引获取桐bucket
    const bucket = this.storage[index]
    if(!bucket) return null
    //3.遍历桶中的数据
    for(let i =0;i<bucket.length;i++){
      const tuple = bucket[i]
      if(tuple[0] === key){
        bucket.splice(i,1)
        this.count--
         //判断数组是否扩容
        if(this.count>8 && this.count<this.limit*0.25){
          const primeNum = this.getPrime(Math.floor(this.limit/2))
          this.resize(primeNum)
        }
        return tuple[1]
      }
    }
    return null
  }
  //扩容
  resize(newlimit:number){
    //1.保存旧数组中的内容
    const oldStorage = this.storage
    //2.重置属性
    this.limit = newlimit
    this.count = 0
    this.storage =[]
    //3.遍历原来数组中的所有数据
    oldStorage.forEach(bucket=>{
      //如果没有数据直接返回
      if(!bucket)return
      //3.1bucket中存在数据，那么将所有数据重置hash
      for(let i=0;i<bucket.length;i++) {
        const tuple = bucket[i]
        this.put(tuple[0],tuple[1]) 
      }
    })
  }
}
let hsTable = new HashTable()
hsTable.put("aaa",100)
hsTable.put("asd",200)
hsTable.put("bns",300)
hsTable.put("abc",300)
console.log(hsTable.delete("abc"));
console.log(hsTable.get("bns"));
console.log(hsTable.storage);
复制

5.树

树的术语

  1. 节点的度（Degree）：节点的子树个数。

  2. 树的度 （Degree） ：树的所有节点中最大的度数。

  3. 叶节点（Leaf）：度为0的节点。(也称为叶子节点)

  4. 父节点（Parent）：有子树的节点是其子树的根节点的父节点

  5. 子节点（Child）：若A节点是B节点的父节点，则称B节点是A节点的子节点；子节点也称孩子节点。

  6. 兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点。

  7. 路径和路径长度：从节点n1到nk的路径为一个节点序列n1 ，n2，… ，nk

    • ni是 n(i+1)的父节点

    • 路径所包含 边 的个数为路径的长度。

  8. 节点的层次（Level）：规定根节点在1层，其它任一节点的层数是其父节点的层数加1。

  9. 树的深度（Depth）：对于任意节点n, n的深度为从根到n的唯一路径长，根的深度为0。

  10. 树的高度（Height）：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为

image-20230304164021951

二叉树的概念

如果树中每个节点最多只能有两个子节点，这样的树就成为"二叉树",几乎所有的树都可以表示为二叉树的形式（兄弟表示法）

二叉树的定义
  1. 二叉树可以为空，也就是没有节点。
  2. 若不为空，则它是由根节点 和 称为其 左子树TL和 右子树TR 的两个不相交的二叉树组成

二叉树的五种形态

image-20230304164306931

二叉树的特性
  1. 一颗二叉树第 i 层的最大节点数为：2^(i-1)，i >= 1;
  2. 深度为k的二叉树有最大节点总数为： 2^k - 1，k >= 1;
  3. 对任何非空二叉树 T，若n0表示叶节点的个数、n2是度为2的非叶节点个数，那么两者满足关系n0 = n2 + 1。
完美二叉树
完美二叉树(Perfect Binary Tree) ，也称为满二叉树(Full Binary Tree）
  1. 在二叉树中，除了最下一层的叶节点外，每层节点都有2个子节点，就构成了满二叉树。

image-20230304165041053

完全二叉树

完全二叉树(Complete Binary Tree)

  1. 除二叉树最后一层外，其他各层的节点数都达到最大个数。
  2. 且最后一层从左向右的叶节点连续存在，只缺右侧若干节点。
  3. 完美二叉树是特殊的完全二叉树。

下面不是完全二叉树，因为D节点还没有右节点，但是E节点就有了左右节点。

image-20230304165140228

二叉树的存储
二叉树的存储常见的方式是数组和链表。
数组存储

image-20230304165323706

链表存储

二叉树最常见的方式还是使用链表存储

  1. 每个节点封装成一个Node，Node中包含存储的数据，左节点的引用，右节点的引用。

image-20230304165444269

二叉搜索树
二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树
二叉搜索树是一颗二叉树，可以为空；
如果不为空，满足以下性质：
  1. 非空左子树的所有键值小于其根节点的键值。
  2. 非空右子树的所有键值大于其根节点的键值。
  3. 左、右子树本身也都是二叉搜索树。
二叉搜索树的特点
  1. 二叉搜索树的特点就是相对较小的值总是保存在左节点上，相对较大的值总是保存在右节点上。
  2. 那么利用这个特点，我们可以做什么事情呢？
  3. 查找效率非常高，这也是二叉搜索树中，搜索的来源
二叉搜索树的封装
class Node<T>{
  value:T;
  constructor(value:T){
    this.value = value;
  }
}
export default Node
复制
//引入打印树结构的工具
import { btPrint } from 'hy-algokit'
import Node from '../types/Node'
class TreeNode <T> extends Node<T>{
  left:TreeNode <T> | null = null;
  right:TreeNode <T> | null = null;
  //当前节点的父节点
  parent:TreeNode<T>|null =null;
  //判断当前节点是父节点的左右子节点
  get isLeft():boolean{
    return !!(this.parent && this.parent.left === this)
  }
  get isRight():boolean{
    return !!(this.parent && this.parent.right === this)
  }
}
//二叉搜素树封装
class BSTree<T>{
  private root:TreeNode<T> | null = null;
  //设置单层递归逻辑
  private insert(newNode:TreeNode<T>,oldNode:TreeNode<T>){
    //二叉搜素树中插入的节点值大于或者小于当前节点时
    if(newNode.value>oldNode.value){
      if(oldNode.right!==null){
        this.insert(newNode,oldNode.right)
      }else{
        oldNode.right = newNode
      }
    }else{
      if(oldNode.left!==null){
        this.insert(newNode,oldNode.left)
      }else{
        oldNode.left = newNode
      }
    }
  }
  //设置单层查找 递归查找某个值是否存在
  private searchNode(value:T):TreeNode<T>|null{
    // 1.搜索：当前是否有这个value
    let current = this.root
    let parent:TreeNode<T>|null  = null 
    while(current){
      //1.如果找到我们的current,直接返回即可
      if(current.value === value){
        return current
      }
      // 2.继续向下寻找
      parent = current
      if(value>current.value){
        current = current.right
      }else{
        current = current.left
      }
      //如果current有值，那么current保存自己的父节点
      if(current!==null)current.parent = parent
    }   
    return null
  }
  //先序遍历
  preOrderTraverse(){
    this.preOrderTraverseNode(this.root)
  }
  //中序遍历
  inOrderTraverse(){
    this.inOrderTraverseNode(this.root)
  }
  //后序遍历
  NextOrderTraverse(){
    this.NextOrderTraverseNode(this.root)
  }
  //todo 单层遍历逻辑{前 中 后 层序}
  //先序遍历
  private preOrderTraverseNode(node:TreeNode<T>|null){
    if(node===null) return
    console.log(node.value);
    this.preOrderTraverseNode(node.left)
    this.preOrderTraverseNode(node.right)
  }
  //中序遍历
  private inOrderTraverseNode(node:TreeNode<T>|null){
    if(node===null) return
    this.inOrderTraverseNode(node.left)
    console.log(node.value);
    this.inOrderTraverseNode(node.right)
  }
  //后序遍历
  private NextOrderTraverseNode(node:TreeNode<T>|null){
    if(node===null) return
    this.NextOrderTraverseNode(node.left)
    this.NextOrderTraverseNode(node.right)
    console.log(node.value);
  }
  //todo非递归{前 中 后 遍历}
  //先序遍历  
  //思路：将左节点先放入栈中 然后从栈中取出并将其右节点放入栈中 
  //判断其是否具有右节点
  preOrderTraversalNoRecursion(){
    let stack:TreeNode<T>[] = []
    let current = this.root
    while(current!==null||stack.length!==0){
      while(current!==null){
        console.log(current.value);
        stack.push(current)
        current = current.left
      }
      current = stack.pop()!
      current = current.right
    }
  }
  //中序遍历
  inOrderTraversalNoRecursion(){
    let stack:TreeNode<T>[] = []
    let current = this.root
    while(current!==null||stack.length!==0){
      while(current!==null){
        stack.push(current)
        current = current.left
      }
      current = stack.pop()!
      console.log(current.value);
      current = current.right
    }
  }
  //后续遍历 : 后续遍历的非递归比较麻烦一些
  NextOrderOrderTraversalNoRecursion(){
    let stack:TreeNode<T>[] = []
    let current:TreeNode<T>|null = this.root
    let lastVisitedNode:TreeNode<T>|null = null
    while(current!==null || stack.length!==0){
      while(current !== null){
        stack.push(current)
        current = current.left
      }
      current  = stack[stack.length-1]
      if(current.right === null && current.right === lastVisitedNode){
        console.log(current.value);
        lastVisitedNode = current
        stack.pop()
        current = null
      }else{
        current = current.right
      }
    }
  }
  //层序遍历  队列结构时间
  levelOederTraverse(){
    //如果没有根节点，那么不需要遍历
    if(!this.root) return
    //创建队列结构
    const queue:TreeNode<T>[] = []
    queue.push(this.root)
    while(queue.length>0){
      const current = queue.shift()!
      console.log(current.value);
      if(current.left!==null)queue.push(current.left)
      if(current.right!==null)queue.push(current.right)
    }
  }
  //获取最大值  获取最小值雷同
  getMaxValue(){
    if(!this.root) return null
    let current:TreeNode<T>|null = this.root 
    while(current){
      if(current.right===null) return current.value
      current = current.right  
    }
  }
  getMinValue(){
    let current:TreeNode<T>|null = this.root 
    while(current&&current.left!==null){
      current = current.left
    }
    //curent为null的时候返回null
    return current?.value??null
  }
  print(){
    btPrint(this.root)
  }
  //插入节点
  insertNode(value:T){
   let newNode = new TreeNode(value)
   if(this.root!== null){
      this.insert(newNode,this.root)
   }else{
      this.root = newNode
   }
  }
  //循环的方式查找某个节点是否存在
  search(val:T):boolean{
    return !!this.searchNode(val)
  }
  //实现current有两个节点的删除操作--->后继节点
  private getSuccessor(delNode:TreeNode<T>):TreeNode<T>{
    //1.获取右子树
    let current = delNode.right
    //2.寻找后继节点
    let successor:TreeNode<T>|null = null
    while(current){
      successor = current;
      current = current.left 
      //todo 解析：（对树结构的疑惑点）只有删除的当前节点被赋予parent值（原因是调用了查询方法） 
      //todo 其余的节点未被赋予，需要我们手动加入，不然 successor!.parent!.left = successor!.right 
      //todo 此代码不成立（successor!.parent为空） 
      if(current){
        current.parent = successor
      }
    }
    console.log("删除节点",delNode.value,"后继节点",successor?.value);
    //3.将删除节点的left（因为是后继节点），赋值给后继节点的left
    successor!.left = delNode.left 
    //拿到了后继节点
    if(successor!==delNode.right){
      successor!.parent!.left = successor!.right
      successor!.right = delNode.right
    }
    return successor!
    
  }
  //实现删除操作
  remove(value:T):boolean{
    let current =  this.searchNode(value)
    //1.未搜索到
    if(!current) return false
    //获取到 1.当前节点 2.父节点  3.属于父节点的左右节点
    // console.log("当前节点："+current.value+" 父节点："+current.parent?.value);
    //2.如果删除的叶子节点
    if(current.left===null&&current.right===null){
      if(current.parent===null)return false
      if(current.isLeft){
        current.parent.left = null
      }else{
        current.parent.right = null
      }
    }
    //3.当前节点只有一个左子节点
    else if(current.right===null){
      //根节点==>左子节点
      if(current===this.root){
         this.root =  current.left 
      }else if(current.isLeft){
        //在其父节点的左侧
        current.parent!.left = current.left
      }else{
        //在其父节点的右侧
        current.parent!.right = current.left
      }
    }
    //4.当前节点只有一个右子节点
    else if(current.left===null){
      //根节点==>左子节点
      if(current===this.root){
         this.root =  current.right 
      }else if(current.isLeft){
        //在其父节点的左侧
        current.parent!.left = current.right
      }else{
        //在其父节点的右侧
        current.parent!.right = current.right
      }
    }
    //5.有两个子节点，代码较长已经抽取
    //比 current小一点点的节点，称为current节点的前驱节点
    //大一点点的称为后继节点
    else{
      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
  }
}
let bst = new BSTree<number>()
bst.insertNode(11)
bst.insertNode(7)
bst.insertNode(15)
bst.insertNode(5)
bst.insertNode(3)
bst.insertNode(9) 
bst.insertNode(8)
bst.insertNode(10)
bst.insertNode(13)
bst.insertNode(12)
bst.insertNode(14)
bst.insertNode(20)
bst.insertNode(18)
bst.insertNode(25)
bst.insertNode(6)
// bst.insertNode(11) // 相同的节点根据个人去处理？
bst.print()
bst.remove(11)
bst.print()
bst.remove(15)
bst.print()
bst.remove(9)
bst.print()
// bst.remove(13)
bst.remove(7)
bst.print()
复制

提示：二叉搜索树的删除操作考虑的情况较多，要注意三种不同的情况

6.图结构

什么是图?
在计算机程序设计中，图结构 也是一种非常常见的数据结构。
  1. 但是，图论其实是一个非常大的话题
  2. 我们通过本章的学习来认识一下关于图的一些内容 - 图的抽象数据类型 – 一些算法实现。
什么是图?
  1. 图结构是一种与树结构有些相似的数据结构。
  2. 图论是数学的一个分支，并且，在数学的概念上，树是图的一种。
  3. 它以图为研究对象，研究 顶点 和 边 组成的图形的数学理论和方法。
  4. 主要研究的目的是事物之间的关系，顶点代表事物，边代表两个事物间的关系
我们知道树可以用来模拟很多现实的数据结构
  1. 比如： 家谱/公司组织架构等等
  2. 那么图长什么样子?
  3. 或者什么样的数据使用图来模拟更合适呢
图的术语

image-20230304171050284

顶点：
  1. 顶点刚才我们已经介绍过了，表示图中的一个节点。
  2. 比如地铁站中某个站/多个村庄中的某个村庄/互联网中的某台主机/人际关系中的人。
边：
  1. 边刚才我们也介绍过了，表示顶点和顶点之间的连线。
  2. 比如地铁站中两个站点之间的直接连线，就是一个边。
  3. 注意： 这里的边不要叫做路径，路径有其他的概念，待会儿我们会介绍到。
  4. 之前的图中： 0 - 1有一条边，1 - 2有一条边，0 - 2没有边。
相邻顶点：
  1. 由一条边连接在一起的顶点称为相邻顶点。
  2. 比如0 - 1是相邻的，0 - 3是相邻的。 0 - 2是不相邻的。

image-20230304171234030

image-20230304171320560

图的表示

怎么在程序中表示图呢?

  1. 我们知道一个图包含很多顶点，另外包含顶点和顶点之间的连线(边)
  2. 这两个都是非常重要的图信息，因此都需要在程序中体现出来
顶点的表示相对简单，我们先讨论顶点的表示。
  1. 上面的顶点，我们抽象成了1 2 3 4，也可以抽象成A B C D。
  2. 在后面的案例中，我们使用A B C D。
  3. 那么这些A B C D我们可以使用一个数组来存储起来(存储所有的顶点)
  4. 当然，A，B，C，D也可以表示其他含义的数据(比如村庄的名字).
那么边怎么表示呢?
  1. 因为边是两个顶点之间的关系，所以表示起来会稍微麻烦一些。
  2. 下面，我们具体讨论一下变常见的表示方式。
邻接矩阵
一种比较常见的表示图的方式： 邻接矩阵。
  1. 邻接矩阵让每个节点和一个整数项关联，该整数作为数组的下标值。
  2. 我们用一个二维数组来表示顶点之间的连接。
  3. 二维数组[0][2] -> A -> C
画图演示：

image-20230304171609877

图片解析：
  1. 在二维数组中，0表示没有连线，1表示有连线。
  2. 通过二维数组，我们可以很快的找到一个顶点和哪些顶点有连线。(比如A顶点，只需要遍历第一行即可)
  3. 另外，A - A，B - B(也就是顶点到自己的连线)，通常使用0表示。
邻接矩阵的问题：
  1. 邻接矩阵还有一个比较严重的问题，就是如果图是一个稀疏图
  2. 那么矩阵中将存在大量的0，这意味着我们浪费了计算机存储空间来表示根本不存在的边
邻接表
另外一种常用的表示图的方式： 邻接表。
  1. 邻接表由图中每个顶点以及和顶点相邻的顶点列表组成。
  2. 这个列表有很多种方式来存储： 数组/链表/字典(哈希表)都可以。
画图演示

image-20230304171737676

图片解析：
  1. 其实图片比较容易理解。
  2. 比如我们要表示和A顶点有关联的顶点(边)，A和B/C/D有边，
  3. 那么我们可以通过A找到对应的数组/链表/字典，再取出其中的内容就可以啦。
邻接表的问题：
  1. 邻接表计算"出度"是比较简单的(出度： 指向别人的数量，入度： 指向自己的数量)
  2. 邻接表如果需要计算有向图的"入度"，那么是一件非常麻烦的事情。
  3. 它必须构造一个“逆邻接表”，才能有效的计算“入度”。但是开发中“入度”相对用的比较少c
创建图类
class Graph<T>{
  //顶点
  private verteces:T[] = []
  //边,邻接表
  private adjList:Map<T,T[]> = new Map()
  /**添加顶点跟边的方法*/
  addVertex(vertex:T){
    //保存顶点
    this.verteces.push(vertex)
    //创建邻接表
    this.adjList.set(vertex,[])
  }
 
   /**添加边*/
  addEdge(v1:T,v2:T){
    this.adjList.get(v1)?.push(v2)
    this.adjList.get(v2)?.push(v1)
  }
 
  /**遍历*/
  traverse(){
    this.verteces.forEach((vertex)=>{
      const edges = this.adjList.get(vertex)
      console.log(`${vertex} -> ${edges?.join(" ")}`);
    }
  )}
  /**BFS*/ 
  bfs(){
    if(this.verteces[0]===0) return
    let queue:T[] = []
    queue.push(this.verteces[0])
    //访问过后的顶点插入set中
    let visited = new Set()
    visited.add(this.verteces[0])
    while(queue.length){
      //拿到队列头部元素
      const vertex = queue.shift()! 
      this.adjList.get(vertex)?.forEach(item=>{
        if(!visited.has(item)){
          visited.add(item)
          queue.push(item)
        }
      })
    }
    return visited
  }
  /**DFS*/  
  //无论是从哪个方向开始深层次挖掘最终结果是一样的
  dfs(){
    if(this.verteces[0]===0) return
    //模拟栈结构 循环
    let stack:T[] = []
    stack.push(this.verteces[0])
    //创建set结构
    let visited = new Set<T>()
    visited.add(this.verteces[0])
 
    while(stack.length){
      const vertex = stack.pop()!
      this.adjList.get(vertex)!.forEach(ele=>{
        if(!visited.has(ele)){
          stack.push(ele)
          visited.add(ele)
        }
      })
    }
    return visited
  }
}
const graph = new Graph()
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")
graph.addVertex("F")
graph.addVertex("G")
graph.addVertex("H")
 
graph.addEdge("A","B")
graph.addEdge("B","C")
graph.addEdge("C","D")
graph.addEdge("D","E")
graph.addEdge("E","F")
graph.addEdge("F","G")
// graph.traverse()
//todo 广度队列结构一层一层 深度while循环，类递归 
console.log(graph.bfs());
console.log(graph.dfs());
export {}
复制
转载请注明出处或者链接地址：https://www.qianduange.cn//article/8869.html
标签
上一篇：HTML基本结构及基本标签
评论
相关文章

前端哥

前端哥

广告位招租：QQ85750956
发布的文章

运行npm error code ENOENTnpm error syscall opennpm error path C:\Users\ultra\Desktop\Vue-Project\pac

2024-08-27 09:08:17

前端提高篇（102）：jQuery高级方法callbacks、deferred

2024-05-09 11:05:34

解决npm install 报错 “npm err code 1“

2024-06-06 10:06:47

【常见错误】npm ERR! code CERT_HAS_EXPIRED & errno CERT_HAS_EXPIRED

2024-04-22 09:04:34

vue前端页面弹出红色报错遮罩层 Uncaught runtime errors:at handleError (webpack-internal:///./node_modules/webpack

2024-03-29 15:03:20

npm ERR! code CERT_HAS_EXPIRED npm ERR! errno CERT_HAS_EXPIRED npm ERR! request to https://registry.

2024-04-20 17:04:38

JQuery中的load()、$

2024-05-10 08:05:15

《WEB前端框架开发技术》HTML5响应式旅游景区网站——榆林子州HTML CSS JavaScript (1)

2024-10-30 21:10:12

基于Java SpringBoot Vue HTML5药店管理系统(源码 LW 调试文档 讲解等)/药店管理软件/药店进销存系统/药店库存管理系统/药店销售系统/药品管理系统/药店收银系统

2024-11-10 09:11:04

基于Java SpringBoot Vue HTML5宠物健康顾问系统(源码 LW 调试文档 讲解等)/宠物健康/顾问系统/宠物护理/宠物医疗/宠物保健/宠物咨询/宠物医生/宠物健康管理/宠物健康服务

2024-11-10 09:11:50

广告位招租：QQ85750956
大家推荐的文章
1

【Echarts系列】—— 实现电池图、3D立体圆形柱状图

2024-03-03 11:03:011001
2

CSS常用属性（文本属性）

2024-11-04 09:11:111000
3

TypeScript 中的 Number 类型，Number 类型的特性、常见操作和注意事项

2024-09-30 23:09:061000
4

CSS写代码使页面划分为左右两个区域

2024-09-09 00:09:071000
5

vue使用datav echarts

2024-09-06 00:09:381000
6

使用TweenMax.js和CSS3创建冰球运动员动画效果教程

2024-09-04 23:09:411000
7

使用CDN提高jQuery加载速度

2024-08-24 23:08:211000
8

小兔鲜儿网页首页制作 黑马程序员前端基础项目自学笔记

2024-08-19 22:08:161000
9

《Vue》你的弹窗能拖动吗？Vue自定义指令实现可拖动弹窗

2024-08-19 22:08:121000
10

npm的使用

2024-08-18 00:08:131000

rss订阅 百度xml 谷歌xml 搜狗xml soxml 神马搜索xml 网站地图

Copyright © 2018-2022 前端哥 陕ICP备2023000550号-1 前端哥

讲个笑话：程序员心理活动：看别人的代码，这都写得什么玩意儿，垃圾！！看自己一个月前的代码：这TM谁写得代码，垃圾！再一看，这代码怎么这么眼熟？我自己写得？仔细一看，卧槽！还TM的真是我自己写的！！

前端技术交流源码工具分享网站

会员中心 联系我 留言建议 回顶部
复制成功！