TypeScript版数据结构

数据结构

栈

栈是一个一个**==后进先出==**的数据结构
TypeScript 版数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 定义栈需要的方法
interface IStack<T> {
  push(element: T): void;
  pop(): T | undefined;
  peek(): T;
  isEmpty(): boolean;
  size(): number;
  toString(): string;
}

// 封装栈结构 基于数组实现
class Stack<T = any> implements IStack<T> {
  list: T[];

  constructor() {
    this.list = [];
  }
  // 向栈顶添加一个元素
  push(element: T) {
    this.list.push(element);
  }

  // 移除栈顶的元素并返回移除的元素
  pop(): T | undefined {
    return this.list.pop();
  }

  // 返回栈顶的元素
  peek(): T {
    return this.list[this.list.length - 1];
  }

  // 判断栈是否为空
  isEmpty(): boolean {
    return this.list.length <= 0 ? true : false;
  }

  // 返回栈元素的个数
  size(): number {
    return this.list.length;
  }

  // 使栈的数据以字符串形式打印
  toString(): string {
    return this.list.join(" ");
  }
}

十进制转二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
const stack = new Stack<number>();
// 利用栈结构实现十进制转二进制
function transform(num: number) {
  while (num >= 1) {
    stack.push(num % 2);
    num = Math.floor(num / 2);
  }
  let result = "";
  while (!stack.isEmpty()) {
    result += stack.pop();
  }
  return result;
}

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 解题思路: 遇到左括号就把对应的右括号入栈 当遇到右括号时与栈顶元素比较是否相同 并且最后栈里不能有元素
function isValid(s: string): boolean {
  const stack = new Stack<string>();
  for (let i = 0; i < s.length; i++) {
    const flag = s[i];

    if (flag === "(") {
      stack.push(")");
    } else if (flag === "{") {
      stack.push("}");
    } else if (flag === "[") {
      stack.push("]");
    } else {
      if (flag !== stack.pop()) return false;
    }
  }

  return stack.isEmpty();
}

队列

队列和栈相反是一个==先进先出==的一个数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
interface IQueue<T> {
  enqueue(element: T): void;
  dequeue(): T | undefined;
  front(): T;
  isEmpty(): boolean;
  size(): number;
}

// 封装队列结构 基于数组实现
export default class Queue<T = any> implements IQueue<T> {
  list: T[] = [];

  // 队列尾部添加一项
  enqueue(element: T) {
    this.list.push(element);
  }

  // 移除队列的第一个元素并返回
  dequeue(): T | undefined {
    return this.list.shift();
  }

  // 返回队列最先被添加的元素
  front(): T {
    return this.list[0];
  }

  // 判断队列是否为空
  isEmpty(): boolean {
    return this.list.length <= 0 ? true : false;
  }

  // 返回队列元素的个数
  size(): number {
    return this.list.length;
  }
}

击鼓传花

几个朋友一起玩一个游戏，围成一圈，开始数数，数到某个数字的人自动淘汰。使用 TypeScript 实现一个函数传入玩家的名字和数到什么数字淘汰，并返回胜利的玩家。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function hotPotato(arr: string[], num: number) {
  // 1. 创建队列
  const queue = new Queue<string>();

  // 2.将所有人入队
  for (const item of arr) {
    queue.enqueue(item);
  }

  while (queue.size() !== 1) {
    // 3.将[1~num)的人出队在入队
    for (let i = 1; i < num; i++) {
      queue.enqueue(queue.dequeue()!);
    }

    // 将数到第num的人出队
    queue.dequeue();
  }
  return queue.front();
}

优先级队列

每个元素都分配一个数字来标记其优先级，优先级小的排在前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 封装优先级队列的元素对象
class QueueElement<T> {
  element: T;
  priority: number;
  constructor(element: T, priority: number) {
    this.element = element;
    this.priority = priority;
  }
}
// 封装优先级队列
class priorityQueue<T = any> {
  list: QueueElement<T>[] = [];
  length: number = 0;

  // 队列尾部添加一项 优先级小的在前面
  enqueue(element: T, priority: number) {
    // 获取需要插入的对象元素
    const queueElement = new QueueElement<T>(element, priority);
    if (this.isEmpty()) {
      // 队列为空则直接插入
      this.list.push(queueElement);
    } else if (queueElement.priority > this.list[this.length - 1].priority) {
      // 比队列的最后优先级大则直接插入到最后
      this.list.splice(this.length, 0, queueElement);
    } else {
      for (let i = 0; i < this.length; i++) {
        if (queueElement.priority < this.list[i].priority) {
          this.list.splice(i, 0, queueElement);
          break;
        }
      }
    }
    this.length++;
  }

  // 移除队列的第一个元素并返回
  dequeue() {
    if (this.length <= 0) throw new Error("stack is empty");
    this.length--;
    return this.list.shift();
  }
  // 返回队列最先被添加的元素
  front() {
    if (this.isEmpty()) return null;
    return this.list[0];
  }
  // 判断队列是否为空
  isEmpty() {
    return this.length <= 0 ? true : false;
  }
  // 返回队列元素的个数
  size() {
    return this.length;
  }
}

单项链表

不同于数组，链表在内存中的空间不必是连续的，链表的每个元素由一个储存元素本身的节点和指向下一个元素的指针构成。

链表的优势：

  • 链表中的元素在内存中不必是连续的空间，可以充分利用计算机的内存，实现灵活的内存动态管理。
  • 链表不必在创建时就确定大小，并且大小可以无限地延伸下去。
  • 链表在插入和删除数据时，时间复杂度可以达到 O(1)，相对数组效率高很多。

链表的缺点：

  • 链表访问任何一个位置的元素时，都需要从头开始访问（无法跳过第一个元素访问任何一个元素）。
  • 无法通过下标值直接访问元素，需要从头开始一个个访问，直到找到对应的元素。
  • 虽然可以轻松地到达下一个节点，但是回到前一个节点是很难的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// 封装链表的节点类
class Node<T> {
  element: T;
  next: Node<T> | null;
  constructor(element: any) {
    // 保存元素
    this.element = element;
    // 指向下一个节点
    this.next = null;
  }
}

// 封装单向链表类
class LinkList<T = any> {
  head: Node<T> | null;
  length: number;
  constructor() {
    this.head = null;
    this.length = 0;
  }

  // 向链表中添加元素
  append(element: T) {
    const node = new Node<T>(element);
    if (this.head === null) {
      // 链表为空
      this.head = node;
    } else {
      // 链表不为空
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = node;
    }
    this.length++;
  }

  // 获取指定位置的元素
  get(position: number) {
    // 数据越界抛出错误
    if (position < 0 || position > this.length - 1) {
      throw new Error("position is error");
    }
    let i = 0;
    let current = this.head;
    while (i !== position) {
      current = current!.next;
      i++;
    }
    return current;
  }

  // 向链表特定位置插入一项
  insert(position: number, element: T) {
    // 数据越界抛出错误
    if (position < 0 || position > this.length) {
      throw new Error("position is error");
    }

    const node = new Node<T>(element);
    if (position === 0 && this.length !== 0) {
      // 如果插入是第0个位置并且链表中有元素
      const firstNode = this.head;
      this.head = node;
      node.next = firstNode;
    } else if (position === 0 && this.length === 0) {
      // 如果插入是第0个位置并且链表中没有元素
      this.append(element);
    } else {
      let current = this.get(position - 1); //获取指定位置的前一个元素
      node.next = current!.next;
      current!.next = node;
    }
    this.length++;
  }

  // 返回元素来列表中的索引 没有则返回-1
  indexOf(element: any) {
    let i = 0;
    let current = this.head;
    while (i !== this.length) {
      if (current!.element === element) {
        return i;
      } else {
        current = current!.next;
        i++;
      }
    }
    return -1;
  }

  //修改某个位置的元素
  update(position: number, element: T) {
    const current = this.get(position);
    current!.element = element;
  }

  // 根据位置移除列表中的某一项
  removeAt(position: number) {
    // 数据越界抛出错误
    if (position < 0 || position > this.length - 1) {
      throw new Error("position is error");
    }

    if (position === 0) {
      this.head = this.head!.next;
    } else {
      let frontNode = this.get(position - 1); //获取指定位置的前一个元素
      frontNode!.next = frontNode!.next!.next;
    }
    this.length--;
  }

  // 根据元素移除列表中的某一项
  remove(element: any) {
    // 不存在该元素则抛出错误
    if (this.indexOf(element) === -1) {
      throw new Error("element is not fount");
    }
    // 获取元素位置
    let position = this.indexOf(element);

    this.removeAt(position);
  }

  // 判断链表是否为空
  isEmpty() {
    return this.length === 0;
  }

  // 返回链表的元素个数
  size() {
    return this.length;
  }
}

删除链表中的节点

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

  • 给定节点的值不应该存在于链表中。

  • 链表中的节点数应该减少 1。

  • node 前面的所有值顺序相同。

  • node 后面的所有值顺序相同。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-node-in-a-linked-list

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

反转链表

循环方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 reverseList(head: ListNode | null): ListNode | null {
  // 判断链表为空或者链表只有一个元素则直接返回头节点
  if (head === null || head.next === null) return head;

  let newHead: ListNode | null = null;

  while (head) {
    let current: any = head.next;
    head.next = newHead;
    newHead = head;
    head = current;
  }

  return newHead;
}

递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
function reverseList(head: ListNode | null): ListNode | null {
  // 判断链表为空或者链表只有一个元素则直接返回头节点
  if (head === null || head.next === null) return head;

  // 拿到的是最后一个节点
  const newHead = reverseList(head?.next);

  // 这里的head会指向倒数第二个节点
  head.next.next = head;
  head.next = null;

  return newHead;
}

双向链表

双向链表：既可以从头遍历到尾，又可以从尾遍历到头。也就是说链表连接的过程是双向的，它的实现原理是：一个节点既有向前连接的引用，也有一个向后连接的引用。

双向链表的缺点：

  • 每次在插入或删除某个节点时，都需要处理四个引用，而不是两个，实现起来会困难些；
  • 相对于单向链表，所占内存空间更大一些；
  • 但是，相对于双向链表的便利性而言，这些缺点微不足道。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
// 封装链表的节点类
class Node<T> {
  element: T;
  next: Node<T> | null;
  prev: Node<T> | null;

  constructor(element: T) {
    // 保存元素
    this.element = element;
    // 指向下一个节点
    this.next = null;
    // 指向上一个节点
    this.prev = null;
  }
}

// 封装双向链表类
class DoublyLinkList<T = any> {
  head: Node<T> | null;
  tail: Node<T> | null;
  length: number;
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // 向链表中添加元素
  append(element: T) {
    const node = new Node<T>(element);
    if (this.length === 0) {
      this.head = this.tail = node;
    } else {
      let current = this.head;
      while (current!.next !== null) {
        current = current!.next;
      }
      node.prev = current;
      current!.next = this.tail = node;
    }
    this.length++;
  }

  // 获取指定位置的元素
  get(position: number) {
    // 数据越界抛出错误
    if (position < 0 || position > this.length - 1) {
      throw new Error("position is error");
    }
    let i = 0;
    let current = this.head;
    while (i !== position) {
      current = current!.next;
      i++;
    }
    return current;
  }

  // 向链表特定位置插入一项
  insert(position: number, element: T) {
    // 数据越界抛出错误
    if (position < 0 || position > this.length) {
      throw new Error("position is error");
    }

    const node = new Node(element);
    if (this.length === 0 && position === 0) {
      // 插入的位置是第一个且链表为空
      this.append(element);
    } else if (this.length !== 0 && position === 0) {
      // 插入的位置是第一个且链表不为空
      node.next = this.head!.next;
      this.head!.prev = this.head = node;
    } else if (position === this.length) {
      // 插入的位置是最后一个
      node.prev = this.tail;
      this.tail!.next = this.tail = node;
    } else {
      const frontNode = this.get(position - 1); // 获取前一个节点
      node.next = frontNode!.next;
      node.prev = frontNode;
      frontNode!.next!.prev = frontNode!.next = node;
    }

    this.length++;
  }
  // 返回元素来列表中的索引 没有则返回-1
  indexOf(element: T) {
    let i = 0;
    let current = this.head;
    while (i !== this.length) {
      if (current!.element === element) {
        return i;
      } else {
        current = current!.next;
        i++;
      }
    }
    return -1;
  }

  // 修改某个位置的元素
  update(position: number, element: T) {
    const current = this.get(position);
    current!.element = element;
  }

  // 根据位置移除列表中的某一项
  removeAt(position: number) {
    // 数据越界抛出错误
    if (position < 0 || position > this.length - 1) {
      throw new Error("position is error");
    }
    const current = this.get(position);

    if (position === 0) {
      // 移除头部
      current!.next!.prev = null;
      this.head = current!.next;
      current!.next = null;
    } else if (position === this.length - 1) {
      // 移除尾部
      current!.prev!.next = null;
      this.tail = current!.prev;
      current!.prev = null;
    } else {
      current!.next!.prev = current!.prev;
      current!.prev!.next = current!.next;
    }
    this.length--;
  }

  // 根据元素移除列表中的某一项
  remove(element: T) {
    // 不存在该元素则抛出错误
    if (this.indexOf(element) === -1) {
      throw new Error("element is not fount");
    }
    // 获取元素位置
    let position = this.indexOf(element);

    this.removeAt(position);
  }

  // 判断链表是否为空
  isEmpty() {
    return this.length === 0 ? true : false;
  }

  // 返回链表的元素个数
  size() {
    return this.length;
  }
}

哈希表

哈希表通常是基于数组实现的，但是相对于数组，它存在更多优势：

  • 哈希表可以提供非常快速的插入-删除-查找操作；
  • 无论多少数据，插入和删除值都只需要非常短的时间，即 O(1)的时间级。实际上，只需要几个机器指令即可完成；
  • 哈希表的速度比树还要快，基本可以瞬间查找到想要的元素。但是相对于树来说编码要简单得多。

哈希表同样存在不足之处：

  • 哈希表中的数据是没有顺序的，所以不能以一种固定的方式（比如从小到大 ）来遍历其中的元素。
  • 通常情况下，哈希表中的 key 是不允许重复的，不能放置相同的 key，用于保存不同的元素。

树

二叉搜索树（插入）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Node<T> {
  value: T;
  constructor(element: any) {
    this.value = element;
  }
}

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
}

class BSTree<T> {
  private root: TreeNode<T> | null = null;

  insert(number: T) {
    // 1. 创建节点
    const newNode = new TreeNode<T>(number);
    if (!this.root) {
      // 节点为空第一个元素就为根节点
      this.root = newNode;
    } else {
      // 根节点已经有值
      this.insertNode(this.root, newNode);
    }
  }

  private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    if (node.value > newNode.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);
      }
    }
  }
}

二叉搜索树（遍历）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Node<T> {
  value: T;
  constructor(element: any) {
    this.value = element;
  }
}

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
}

class BSTree<T> {
  private root: TreeNode<T> | null = null;

  // 先序遍历
  preOrderTraverse() {
    this.PreOrderTraverseNode(this.root);
  }

  PreOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      console.log(node);
      this.PreOrderTraverseNode(node.left);
      this.PreOrderTraverseNode(node.right);
    }
  }

  // 中序遍历
  inOrderTraverse() {
    this.PreOrderTraverseNode(this.root);
  }

  inOrderTraverseNode1(node: TreeNode<T> | null) {
    if (node) {
      this.PreOrderTraverseNode(node.left);
      console.log(node);
      this.PreOrderTraverseNode(node.right);
    }
  }

  // 后序遍历
  postOrderTraverse() {
    this.PreOrderTraverseNode(this.root);
  }

  postOrderTraverseNode1(node: TreeNode<T> | null) {
    if (node) {
      this.PreOrderTraverseNode(node.left);
      this.PreOrderTraverseNode(node.right);
      console.log(node);
    }
  }

  // 层序遍历
  leaverOrderTraverse() {
    if (!this.root) return;
    // 数组模拟队列
    const queue: TreeNode<T>[] = [];
    queue.unshift(this.root);

    while (queue.length !== 0) {
      const node = queue.pop();
      console.log(node?.value);

      if (node?.left) {
        queue.unshift(node!.left);
      }
      if (node?.right) {
        queue.unshift(node!.right);
      }
    }
  }
}

二叉搜索树（最值和搜索）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Node<T> {
	value: T;
	constructor(element: any) {
		this.value = element;
	}
}

class TreeNode<T> extends Node<T>  {
	left: TreeNode<T> | null = null
	right: TreeNode<T> | null = null
}

class BSTree<T> {
	private root: TreeNode<T> | null = null

	// 获取最大值
	getMaxValue(): T | null {
		if (!this.root) return null
		let maxNode = this.root
		while (maxNode?.right !== null) {

			maxNode = maxNode!.right
		}
		return maxNode.value
	}

	// 获取最小值
	getMinValue(): T | null {
		if (!this.root) return null
		let maxNode = this.root
		while (maxNode?.left !== null) {

			maxNode = maxNode!.left
		}
		return maxNode.value
	}

	// 查找树中是否有指定节点
	search(value: T): boolean {
		let current = this.root
		while (current) {
			if (current.value === value) return true
			if (current.value > value) {
				current = current.left
			} else {
				current = current.right
			}
		}
		return false
	}
}

二叉搜索树（删除）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
class Node<T> {
  value: T;
  constructor(element: any) {
    this.value = element;
  }
}

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
}

class BSTree<T> {
  private root: TreeNode<T> | null = null;

  // 根据value获取指定的节点 父节点等信息
  searchNode(value: T) {
    let current = this.root;
    let parent: TreeNode<T> | null = null;
    let flag: "left" | "right" = "left";
    while (current) {
      if (current.value === value) return { current, parent, flag };
      parent = current;
      if (current.value > value) {
        current = current.left;
        flag = "left";
      } else {
        current = current.right;
        flag = "right";
      }
    }
    return null;
  }

  // 获得后继节点 就是右子树中最小的节点
  private getSuccessor(delNode: TreeNode<T>) {
    // 右子树
    let current = delNode.right;
    // 后继节点
    let successor: TreeNode<T> | null = null;

    while (current) {
      successor = current;
      current = current.left;
    }

    // 将删除节点的left赋值给后继节点的left
    successor!.left = delNode.left;

    // 删除节点的右节点不是后继节点
    if (successor !== delNode.right) {
      // 后继节点还有右节点 需要将后继节点的右节点赋值给后继节点父节点的左节点
      const { parent } = this.searchNode(successor!.value)!;
      parent!.left = successor!.right;

      successor!.right = delNode.right;
    }

    return successor!;
  }

  // 删除节点
  delete(value: T) {
    // 树中不存在删除的节点
    if (!this.search(value)) return;

    // 获取删除的节点 父节点 以及左或者右节点
    const {
      current: deleteNode,
      parent: deleteParentNode,
      flag,
    } = this.searchNode(value)!;

    // 如果删除的节点是叶子节点
    if (!deleteNode.left && !deleteNode.right) {
      // 删除的节点为根节点
      if (deleteNode === this.root) {
        this.root = null;
      } else {
        deleteParentNode![flag] = null;
      }
    }

    // 删除的节点只有一个节点 只有左子节点
    else if (deleteNode.right === null) {
      if (deleteNode === this.root) {
        // 删除的节点为根节点
        this.root = deleteNode.left;
      } else {
        deleteParentNode![flag] = deleteNode.left;
      }
    }

    // 删除的节点只有一个节点 只有右子节点
    else if (deleteNode.left === null) {
      if (deleteNode === this.root) {
        // 删除的节点为根节点
        this.root = deleteNode.right;
      } else {
        deleteParentNode![flag] = deleteNode.right;
      }
    }

    // 删除的节点有两个子节点
    else {
      // 获取后继节点
      const successor = this.getSuccessor(deleteNode);
      if (deleteNode === this.root) {
        // 删除的节点为根节点
        this.root = successor;
      } else if (flag === "left") {
        // 删除的节点为左节点
        deleteParentNode!.left = successor;
      } else {
        // 删除的节点为右节点
        deleteParentNode!.right = successor;
      }
    }
  }
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
class Node<T> {
  value: T;
  constructor(element: any) {
    this.value = element;
  }
}

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
}

class BSTree<T> {
  private root: TreeNode<T> | null = null;

  insert(number: T) {
    // 1. 创建节点
    const newNode = new TreeNode<T>(number);
    if (!this.root) {
      // 节点为空第一个元素就为根节点
      this.root = newNode;
    } else {
      // 根节点已经有值
      this.insertNode(this.root, newNode);
    }
  }

  private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    if (node.value > newNode.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);
  }

  PreOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      console.log(node);
      this.PreOrderTraverseNode(node.left);
      this.PreOrderTraverseNode(node.right);
    }
  }

  // 中序遍历
  inOrderTraverse() {
    this.PreOrderTraverseNode(this.root);
  }

  inOrderTraverseNode1(node: TreeNode<T> | null) {
    if (node) {
      this.PreOrderTraverseNode(node.left);
      console.log(node);
      this.PreOrderTraverseNode(node.right);
    }
  }

  // 后序遍历
  postOrderTraverse() {
    this.PreOrderTraverseNode(this.root);
  }

  postOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      this.PreOrderTraverseNode(node.left);
      this.PreOrderTraverseNode(node.right);
      console.log(node);
    }
  }

  // 层序遍历
  leaverOrderTraverse() {
    if (!this.root) return;
    // 数组模拟队列
    const queue: TreeNode<T>[] = [];
    queue.unshift(this.root);

    while (queue.length !== 0) {
      const node = queue.pop();
      console.log(node?.value);

      if (node?.left) {
        queue.unshift(node!.left);
      }
      if (node?.right) {
        queue.unshift(node!.right);
      }
    }
  }

  // 获取最大值
  getMaxValue(): T | null {
    if (!this.root) return null;
    let maxNode = this.root;
    while (maxNode?.right !== null) {
      maxNode = maxNode!.right;
    }
    return maxNode.value;
  }

  // 获取最小值
  getMinValue(): T | null {
    if (!this.root) return null;
    let maxNode = this.root;
    while (maxNode?.left !== null) {
      maxNode = maxNode!.left;
    }
    return maxNode.value;
  }
  // 查找树中是否有指定节点
  search(value: T): boolean {
    let current = this.root;
    while (current) {
      if (current.value === value) return true;
      if (current.value > value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }

  // 根据value获取指定的节点 父节点等信息
  searchNode(value: T) {
    let current = this.root;
    let parent: TreeNode<T> | null = null;
    let flag: "left" | "right" = "left";
    while (current) {
      if (current.value === value) return { current, parent, flag };
      parent = current;
      if (current.value > value) {
        current = current.left;
        flag = "left";
      } else {
        current = current.right;
        flag = "right";
      }
    }
    return null;
  }

  // 获得后继节点 就是右子树中最小的节点
  private getSuccessor(delNode: TreeNode<T>) {
    // 右子树
    let current = delNode.right;
    // 后继节点
    let successor: TreeNode<T> | null = null;

    while (current) {
      successor = current;
      current = current.left;
    }

    // 将删除节点的left赋值给后继节点的left
    successor!.left = delNode.left;

    // 删除节点的右节点不是后继节点
    if (successor !== delNode.right) {
      // 后继节点还有右节点 需要将后继节点的右节点赋值给后继节点父节点的左节点
      const { parent } = this.searchNode(successor!.value)!;
      parent!.left = successor!.right;

      successor!.right = delNode.right;
    }

    return successor!;
  }

  // 删除节点
  delete(value: T) {
    // 树中不存在删除的节点
    if (!this.search(value)) return;

    // 获取删除的节点 父节点 以及左或者右节点
    const {
      current: deleteNode,
      parent: deleteParentNode,
      flag,
    } = this.searchNode(value)!;

    // 如果删除的节点是叶子节点
    if (!deleteNode.left && !deleteNode.right) {
      // 删除的节点为根节点
      if (deleteNode === this.root) {
        this.root = null;
      } else {
        deleteParentNode![flag] = null;
      }
    }

    // 删除的节点只有一个节点 只有左子节点
    else if (deleteNode.right === null) {
      if (deleteNode === this.root) {
        // 删除的节点为根节点
        this.root = deleteNode.left;
      } else {
        deleteParentNode![flag] = deleteNode.left;
      }
    }

    // 删除的节点只有一个节点 只有右子节点
    else if (deleteNode.left === null) {
      if (deleteNode === this.root) {
        // 删除的节点为根节点
        this.root = deleteNode.right;
      } else {
        deleteParentNode![flag] = deleteNode.right;
      }
    }

    // 删除的节点有两个子节点
    else {
      // 获取后继节点
      const successor = this.getSuccessor(deleteNode);
      if (deleteNode === this.root) {
        // 删除的节点为根节点
        this.root = successor;
      } else if (flag === "left") {
        // 删除的节点为左节点
        deleteParentNode!.left = successor;
      } else {
        // 删除的节点为右节点
        deleteParentNode!.right = successor;
      }
    }
  }
}

图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
	// 顶点
	verteces: T[] = []
	// 边 邻接表
	adList: Map<T, T[]> = new Map()

	// 添加顶点
	addvertex(vertex: T) {
		// 将顶点添加到数组中保保存
		this.verteces.push(vertex)
		// 添加一个邻接表
		this.adList.set(vertex, [])
	}

	// 添加顶点之间的边(无向图)
	addEdge(v1: T, v2: T) {
		this.adList.get(v1)?.push(v2)
		this.adList.get(v2)?.push(v1)
	}

	// 广度优先搜索
	bfs() {
		// 判断是否有顶点
		if (this.verteces.length === 0) return

		// 队列结构遍历访问每一个顶点
		const queue: T[] = []
		queue.push(this.verteces[0])

		// 创建set结构记录顶点是否被访问过
		const visited = new Set<T>()
		visited.add(this.verteces[0])

		while (queue.length) {
			const vertex = queue.shift()!
			console.log(vertex)

			// 获取相邻顶点
			const neighbors = this.adList.get(vertex)
			if (!neighbors) continue
			for (const nei of neighbors) {
				if (!visited.has(nei)) {
					visited.add(nei)
					queue.push(nei)
				}
			}
		}
	}

	// 深度优先搜索
	dfs() {
		// 判断是否有顶点
		if (this.verteces.length === 0) return

		// 栈结构遍历访问每一个顶点
		const stack: T[] = []
		stack.push(this.verteces[0])

		// 创建set结构记录顶点是否被访问过
		const visited = new Set<T>()
		visited.add(this.verteces[0])

		while (stack.length) {
			const vertex = stack.pop()!
			console.log(vertex)

			// 获取相邻顶点
			const neighbors = this.adList.get(vertex)
			if (!neighbors) continue

			for (let i = neighbors.length - 1; i > 0; i--) {
				const nei = neighbors[i]
				visited.add(nei)
				stack.push(nei)
			}
		}
	}
}

堆结构