数据结构与算法之初体验(一)
在软考中，需要掌握的数据结构和算法基础主要包括如下几点：
知识点赏析：
线性表：
线性表分为顺序表和链表。（以图代文）
①循序表：
1
2
3
4
5
6
7
8
②链表：
单链表
循环链表
双链表
③链表的插入与删除
单链表
删除：
插入：
双链表
删除：
插入：
栈：先进后出
队列：先进先出
循环队列
队满：head=tail+1
对空：head=tail
树和二叉树
①基础掌握
1、该树的度为3
2、叶子节点：3、5、6、7、9、10节点都是叶子节点：度为0的节点。
3、分支节点：除了叶子节点就是分支节点，包括根节点。
4、内部节点：分支节点除了根节点之外的就是内部节点。
5、父节点：
6、子节点：
7、兄弟节点：
8、层次：如图表示1层，2层。
9、n（个节点）=k（度）+1——所有节点度的总和加一就是所有的节点数
10、n0（叶子节点数）=n2（度为2的节点数）+1
②二叉树的遍历
1、前序遍历：先根后节点：1、2、3
2、中序遍历：2、1、3
3、后序遍历：2、3、1
4、层次遍历：按层遍历
③二叉排序树：左子树小于根节点，右子树大于根节点。
·一些操作：
查找：给定一个值key，和节点（Node）进行比较：key>Node,去和左子树比较；key<Node，去和右子树比较，直到key=Node。
插入：先查找，后插入，符合查找规则。
删除：叶子节点直接删除；要删除的根节点只有一个子节点，则该子节点荣升为原来根节点的位置；要删除的根节点有两个子节点，在其左子树上中序遍历最大值，大的荣升为根节点，小的保持原位。
④最优二叉树（哈夫曼树）：
⑤线索二叉树
⑥平衡二叉树：它或者是一棵空树，或者是一棵树中任一节点的左、右子树的深度不相差不超过1。
8、图：
①有向图
②无向图
③图的存储用邻接矩阵和邻接表
④图的遍历
1、深度优先遍历：类似树的先根遍历
2、广度优先遍历：类似树的层次遍历。
