数据结构图的遍历_常用数据结构

八大数据结构分类：

目录

1. 数组
2. 栈
3. 队列
4. 链表
5. 树
6. 散列表
7. 堆
8. 图

1、数组(略)

优点：
1、按照索引查询元素速度快
2、按照索引遍历数组方便

缺点：
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加，删除的操作慢，因为要移动其他的元素。

2、栈

定义：栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。

//可以用js模拟栈： 
let stack = new Array(1,2,3);  
stack.pop();//3   出栈
stack.pop();//2   出栈
stack.pop();//1   出栈

3、队列

定义：队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队，示例图如下：

//可以用js模拟队列： 
let queue = new Array('A','B','C');    
queue.shift();//A 
queue.shift();//B
queue.shift();//C

4、树(已二叉树为例)

定义：树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；

1）二叉树的遍历

1.1）深度优先遍历(Depth-First-Search)

• 前序遍历：访问根–>遍历左子树–>遍历右子树;
• 中序遍历：遍历左子树–>访问根–>遍历右子树;
• 后序遍历：遍历左子树–>遍历右子树–>访问根;

1.2）广度遍历(Breadth-First-Search)：按照层次一层层遍历

// 前序遍历(根左右)：[ '-', '+', 'a', '*', 'b', 'c', '/', 'd', 'e' ]
// 中序遍历(左根右)：[ 'a', '+', 'b', '*', 'c', '-', 'd', '/', 'e' ]
// 后序遍历(左右根)：[ 'a', 'b', 'c', '*', '+', 'd', 'e', '/', '-' ]
// 广度遍历(按层遍历)：[ '-', '+', '/', 'a', '*', 'd', 'e', 'b', 'c' ]
解法有2种，代码太长，放github上。
(1)、递归
(2)、非递归

例子：github地址

5、链表

定义：链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

/**
 * 一、单项链表 
 * */
// 节点
function Node(data) {
    this.data = data;//存储数据
    this.next = null;//指向链表中下一个节点的指针
}
 
// 链表
function SinglyList() {
    this._length = 0;//用于表示链表中的节点数量
    this.head = null;//分配一个节点作为链表的头
}
 
 
/**
 * 二、双项链表 
 * */
//节点
function Node(value){
    this.data = value;//存储数据
    this.previous = null;//前指针
    this.next = null;//后指针
}
//链表
function DoublyList(){
    this._length = 0;//链表长度
    this.head = null;//头指针
    this.tail = null;//尾指针
}

例子：github地址

6、散列表

定义：散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。

7、堆

定义：堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

8、图

定义：图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

参考文章：