算法框架之数组&链表&二叉树

一、数据结构的存储方式

1. 数据结构的基本存储方式：【数组】（顺序存储）和【链表】（链式存储）

但实际上朗朗上口的数据结构还有很多【栈】【队列】【散列表】但其实实际上都是基于【数组/链表】实现的。

下面举两个例子

　　1.散列表：

　　　　通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。

　　2.栈/队列：

　　　　这两种数据结构既可以使用链表也可以使用数组实现。用数组实现，就要处理扩容缩容的问题；用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。

　　3.堆/树：

　　　　堆：可以被看做一棵完全二叉树的数组对象。

　　　　树：用链表实现【衍生出各种巧妙的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。】

　　4.图：

　　　　邻接表：链表实现。　　 邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。

　　　　邻接矩阵：二维数组实现。邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间。

二、数据结构的基本操作

1.对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增删查改。

2.各种数据结构的遍历 + 访问无非两种形式：线性的【迭代】和非线性的【递归】。

三、数据结构操作的基本框架

以下给出几种常见的遍历操作方式

1. 数组遍历框架，典型的线性迭代结构：

/**
* @param {number[]} arr
*/
function go(arr) {
    for (var i = 0; i < arr.length; i++) {
        // 迭代访问 arr[i]
    }
}

2. 链表遍历框架，兼具迭代和递归结构：

/**
 * Definition for ListNode.
 * function ListNode (val) {
 *     this.val = val;
 *     this.next= null;
 * }
 */
/**
 * @param {ListNode } head
 */
　//go1迭代
function go1(head) {
//方式一 for循环
    for (let p = head; p != null; p = p.next) {
        // 迭代访问 p.val 【迭代操作】
    }
//方式二 while循环
    while(head){
       // 迭代访问 head.val 【迭代操作】
        head=head.next
    }
}
　//go2递归
function go2(head) {
    // 递归访问 head.val 【迭代操作】
    go2(head.next)
}

3. 二叉树遍历框架，典型的非线性递归遍历结构：【扩展树的遍历】

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

function go(root) {
//递归时 操作可在任意位置放置
//例如【前、中、后序 遍历】 只需分别将root.val 放于递归操作 前 中 后即可

　　 //root.val 【前序遍历】
    go(root.left)
　　 //root.val 【中序遍历】
    go(root.right)
　　 //root.val 【后序遍历】
}

3.1 由上面看出N叉树遍历只需按照子节点顺序遍历即可

/**
 * Definition for a tree node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
/**
 * @param {Node} root
 */
function go(root) {
//递归时 操作可在任意位置放置

    for(let i of root.children)
        go(i)
}