数据结构

• 栈-stack
• 队列-queue
• 堆-heap
• 链表-linked list
• 树-tree
• 散列-hash table
• 图-graph

📌 二叉树

🎗 特性

• 第一层节点小于第二层节点，依此类推。
• 树左边的节点小于右边的节点，依此类推。
• 前序遍历：根左右；中序遍历：左根右；后序遍历：左右根。
• 二叉树的第k层的节点数最多为：2的(k-1)次方。
• 有一个完全二叉树的叶子节点个数为1234个，那么它最多有(1234 + 1233 = 2467)个节点。

📌 堆

🎗 特性

• 堆中某个节点的值总是不大于（最大堆）或不小于（最小堆）其父节点的值。
• 堆总是一棵完全二叉树，即除了最后一层节点以外，其他层的节点数量都是最大值，最后一层的节点都排列在左边。

🎗 分类

• 最大堆（大根堆）：根节点的值是所有节点中最大的，并且每个父节点的值都大于或等于其子节点的值。
• 最小堆（小根堆）：根节点的值是所有节点中最小的，并且每个父节点的值都小于或等于其子节点的值。

🎗 操作

• 插入元素：通常需要比较新元素与父节点的值，并通过交换元素来保持堆的性质。
• 删除元素：从堆中删除元素（通常是根节点），并用最后一个元素替换根节点，然后重新调整堆以保持其性质。

📌 链表

由一系列节点（Node）组成，每个节点包含两个部分：数据部分和指向下一个节点的指针部分。

链表的结构允许在内存中非连续的位置存储数据，并通过指针将这些位置连接起来。

🎗 优点

• 动态分配内存：链表不需要预先分配固定大小的内存空间，可以根据需要动态地添加或删除节点。

• 插入和删除操作高效：在链表中插入或删除节点通常只需要修改相关节点的指针，而不需要移动大量数据。

🎗 缺点

• 访问元素慢：与数组相比，链表中的元素没有固定的索引，访问特定位置的元素通常需要从头节点开始遍历链表。

• 需要额外的空间存储指针：链表中的每个节点都需要额外的空间来存储指向下一个节点的指针。