数据结构分为：逻辑结构（对象/数据元素之间的关系）、存储结构/物理结构（数据存储结构）
定义抽象数据类型包含：操作对象、关系、操作（增删改查），抽象数据类型可用三元组表示ADT（D，S，P），D表示数据对象，S表示关系，P表示操作
基本术语：
数据：输入到计算机并能被处理的符号总称，分为数值型、非数值行数据
数据元素：数据的基本单位，通常作为整体考虑处理，分为原子型（基本数据类型元素），复合型（结构体类型元素，由若干数据项组成）
数据项：数据结构中讨论的最小单位
数据对象：性质相同的数据元素集合
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。结构：数据元素之间的关系
数据结构分为：
集合（数据元素属于同一种类型，无其他关系）、线性（一对一）、树型（一对多）、图（多对多）
数据结构形式化定义：数据结构是一个二元组Data_Structure = (D,S)，D是数据元素，S是D的关系
元素/结点：存储数据元素的一个位串，数据元素在计算机中的映像
数据域：存储数据元素数据项的地方
数据结构物理结构分为：
顺序存储（相对存储位置反应逻辑关系）和链式存储（增加一个存放存储位置的指针，表示逻辑关系）
数据类型：变量、常量、表达式，作用：约束取值范围和操作。数据类型=值集合+值操作
数据类型值：非结构的原子数据类型（基本数据类型）、结构操作（若干数据项组成）
算法由一个控制结构和若干个原操作组成，控制结构包括：顺序，循环，分支。原操作：对固有数据类型的操作，算法执行之间是所有原操作执行时间之和
数据元素之间的四种基本结构：集合结构、线性结构、树型结构、图形结构
线性结构：线性表、栈、队列、串、数组
基本特点：第一个元素无直接前驱，最后一个元素无直接后继
线性表：n个数据特征相同的元素构成的有限序列，n为线性表的长度，n=0时，线性表为空表
非空线性结构和线性表特点：
存在唯一一个被称作“第一个”的数据元素和被称作“最后一个”的数据元素。除第一个元素外，每个元素均只有一个前驱，除最后一个元素外，每个元素均只有一个后继。
顺序表的特点：以物理位置相邻表示逻辑位置相邻；优点：任意存取任意元素；缺点：插入、删除操作时需要移动大量元素
链表：任意地址存储单元存储元素，可连续可不连续，线性链表由头指针唯一确定
头结点：在单链表第一个结点之前人为设置一个结点，头结点分为指针域（存放第一个指针的地址）和数据域（不存放任何数据，存放附加信息，如链表的结点个数）。
头结点作用：对链表进行操作时，可以对空表、非空表的情况对首元结点统一处理
头指针存放头结点的地址
栈：先进后出FILO ，非空栈的栈顶指针始终指向栈顶元素的下一个位置
栈满：top - base = stacksize 栈空：top=base
队列：只能在一端进行插入（入队），另一端删除（出队）的线性表
判断队列队满：rear+1 % maxsize = front 队空：rear = front
队列长度：（rear- front+maxsize)% maxsize
树：n个结点的有限集T
n=0时，为空树
n>0时，有且仅有一个结点称为根root
n>1时，其余结点可分为m个互不相交的集合，这些集合可称为子树
树和非树区别：
任何两棵子树不相交，除根节点外每个结点有且仅有一个父节点，一棵n个结点的树，共有n-1条边
树的存储结构：
双亲表示法：存储结点的数据和双亲
孩子表示法：每个结点的孩子用单链表存储，再用n个元素的结构数组指向每个孩子链表
带双亲的孩子链表：在元素的结构数组中存储孩子的双亲
孩子兄弟表示法：在每个结点设置两个指针，一个指向孩子结点，一个指向兄弟结点
二叉树：有n个结点的有限集
n=0时，为空树
n>0时，有且仅有一个结点称之为根root
n>1时，由一个根节点和两棵互不相交的左子树和右子树构成
特点：每个结点至多有两棵树，左子树和右子树，顺序不能颠倒
二叉树的序号：从上到下，从左到右依次排序
特殊二叉树：满二叉树（除叶结点外，每个结点都有两个叶节点），完全二叉树（除最下面一层的节点（叶节点）不是满的，其他节点时满的)
二叉树性质：
第i层上面至多有2的i次方-1个节点（i>1）
深度为k的二叉树至多有2的k次方-1个节点（K>=1)
对任意一个二叉树，叶节点为n0，度数为2的节点为n2，则n0 = n2 + 1
n个节点的二叉树深度为(log2 n )+1
二叉树的顺序存储：
从上到下，从左到右依次进行存储
特点：
节点i的父节点为[i/2]取整，根节点除外
节点i的左孩子为2i，右孩子为2i + 1
顺序存储适用于：完全二叉树和满二叉树；一般二叉树也可用顺序存储，但是很容易造成空间浪费（深度为k且k个结点的单支树，需要长度2的k次方 - 1的一维数组）
链式存储：二叉链接一个结点包含3个域（lchild,data ,rchild），三叉链接（lchild,data , parent,rchild）
二叉树的遍历：
先序遍历（先根节点，在左右子树），中序遍历（先左子树，在根节点，在右子树），后序遍历（先左右子树，在根节点）以根节点为参照物，通过栈实现
二叉树遍历的时间、空间复杂度都是O(n)
二叉树的层序遍历（通过队列实现）：从上到下，从左到右，依次遍历
二叉树遍历的应用：
1、统计二叉树中叶节点的个数（先序遍历）
2、求二叉树深度（后续遍历）
3、由两种遍历（必须还有中序遍历，才能唯一确定二叉树）序列确定二叉树
树如何转变成二叉树：
加线（兄弟相连） 抹线（长兄为父，保留最左边孩子的连线，抹去其它孩子的连线） 旋转（孩子靠左，将同一孩子的连线旋转45度）
二叉树转变成树：
逆操作，把所有有孩子转变成兄弟
森林如何转变成二叉树：兄弟相连，长兄为父， 头树为根，孩子靠左
法一：森林直接变为兄弟，在转为二叉树
法二：各森林各自转变成二叉树，依次连接到前一个二叉树的右子树上
法一法二得到的都是完全相同且唯一的二叉树
二叉树还原成森林：把右边的子树变为森林，其余右子树变为兄弟
树的先根遍历于二叉树的先序遍历相同，树的后根遍历相当于二叉树的中根遍历，树没有中序遍历，因为树无左右子树之分
哈夫曼树（最优二叉树，带权路径长度最短的树）
基本术语：
路径：由一个结点到另一个结点间的分支构成
带权路径：路径上的分支数目
带权路径长度（WPL）：结点到根的路径长度于结点上的权的积
树的带权路径长度：所有叶结点的带权路径长度之和
哈夫曼树：带权路径长度最小的树
构造哈夫曼树算法：
每次从给定权值选取两个最小权值求和（构成一个二叉树，从下向上生成），剩下权值和得到的权值进行比较，继续选出两个最小权求和，一直循环，知道构造除哈夫曼树（从下向上生成）
哈夫曼编码：
通过字符出现的次数记为权值，构造出哈夫曼树，通过二叉树得出哈夫曼编码（左0 ，右1）
特点：
每一码都不是任意码的前缀，译码时可唯一复原
哈夫曼树特点:
没有度为1的结点；n个叶结点的哈夫曼树共有2n-1个结点；哈夫曼树任意非叶节点的左右子树交换过后任为哈夫曼树；同一组权值存在不同哈夫曼树
查找操作：静态查找和动态查找
静态查找：二分法（折半查找）（对元素进行有序排序，查找中间元素，然后通过比较进行选择查找前半部分或者后半部分，一直循环，直到找到结果）
二叉搜索树：
一棵二叉搜索树可以为空，如不为空，则满足：
每个结点都有一个作为搜索依据的关键码 ，且关键码互不相同
左子树（如果存在）上面的关键码均小于根结点
右子树（如果存在）上面的关键码均大于根结点
根结点的左右子树均是二叉搜索树
二叉搜索树基本操作：
二叉搜索树的最大和最小查找：
最大元素一定是二叉树的最右端节点，最小元素一定是二叉树的最左端节点
二叉搜索树插入、删除：
插入操作：
进行搜索操作，如果有相同值，则插入失败，搜索位置就是插入位置。
新插入结点一定是叶结点，并且是查找不成功时，查找路径上的最后一个结点的左孩子或者右孩子。
二叉树的删除操作：
先进行查找操作，查找成功，执行删除操作，要求删除某个节点后，任保持二叉搜索树特性
删除操作分为三种情况：
删除叶结点；被删除的结点只有左子树或者右子树；被删除的结点既有左子树又有右子树
属的查找效率取决于树的高度：
含有n个结点的二叉搜索树的平均查找长度和树的形态有关
蜕变成单分支树的平均查找长度为（N+1）/2
只有二叉树蜕变成平衡二叉树时，其平均查找长度为log2(N+1)
平衡二叉树（AVL）：
他除了是空树，或者是具有：左右子树都是平衡二叉树，和|左深度-右深度|<=1
平衡因子BF：任意结点BF＝左子树深度－右子树深度
平衡二叉树上所有结点的平衡因子只可能是－１ 、０、１
平衡因子从先向上数，及叶结点的平衡因子为０，其余结点的平衡因子通过左子树深度－右子树深度计算
只要二叉树上的任一结点的平衡因子的绝对值不为１，则该树不为平衡二叉树
平衡二叉树的调整：
