最大子列和问题 --MaxSubseqSum.cpp
最大子列和-改
二分查找
同类型数据元素构成有序序列的线性结构
数据对象集：n个元素构成的有序序列
操作集：初始化、访问元素、查找位置、插入、删除、返回长度
实现方式：顺序存储、链式存储
推广：
1）广义表 其中的元素不仅可以是单元素也可以是另一个广义表
2）多重链表 链表中的节点可能同时属于多个链，节点中的指针域可能有多个
具有一定操作约束的线性表，只在一端（栈顶）做插入删除
入栈(Push),出栈（Pop） 后入先出（LIFO）
数据对象集：一个有0个或多个元素的有穷线性表
操作集：生成空堆栈、判断堆栈已满或为空、入栈、出栈
实现方式：顺序存储、链式存储
具有一定操作约束的线性表，一端插入，另一端删除
入队，出队， 先入先出（FIFO）
数据对象集：一个有0个或多个元素的有穷线性表
操作集：生成空队列、判断队列已满或为空、入队、出队
实现方式：顺序存储、链式存储
N个节点组成的有限集合
1）存在一个根节点，用r表示
2）其余节点可分为m个互不相交的有限集{T1, T2, ... , Tm}，
其中每个节点本身又是一棵树，称为原来树的子树
性质：子树是不相交的;除根节点外，每个节点有且仅有一个父节点；一棵N个节点的树有N-1条边
基本术语：
节点的度：结点的子树个数/ 树的度：树的所有节点中最大的度数
节点的层次：根节点在1层，其余节点层次类推 / 树的深度：树的所有节点中的最大层次数
路径和路径长度：从节点A至节点B所经过的节点序列为路径，路径所包含的边的个数称为路径长度
叶节点（度为0的节点）/父节点/子节点/兄弟节点/祖先节点/子孙节点
表示方法：链式存储+儿子-兄弟表示法， 旋转45度后得到二叉树
顺序存储-适用于完全二叉树
二叉树：由根节点和 左子树、右子树两个不相交的二叉树构成
二叉搜索树（Binary Search Tree）：左子树的所有键值小于其根节点的键值，右子树的所有键值大于其根节点的键值，左右子树都是二叉搜索树
操作集：查找任意元素位置，查找最大值位置，查找最小值位置，插入，删除
完全二叉树：
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。
平衡二叉树(Balanced Binary Tree)(AVL树)
-空树/任一结点左右子树高度差的绝对值不超过1
-给定节点数为n的AVL树的最大高度为 O（log2 n）
-平衡二叉树是一种特殊的二叉搜索树
平衡二叉树的调整：指插入节点后，原有的平衡二叉树失去平衡，为恢复平衡应作出的调整
分四种情况讨论：
破坏者（新插入节点）在发现者（距新插入节点最近的非平衡节点）右子树的右侧：RR旋转
右子树的左侧：RL旋转
左子树的左侧：LL旋转
左子树的右侧：LR旋转
优先队列：取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序
用完全二叉树即可以实现有限队列
堆的定义：用数组表示的完全二叉树
-堆中某个结点的值总是不大于或不小于其父结点的值（最大堆/最小堆）；
-堆总是一棵完全二叉树。
特点：从根节点到任意节点的路径是有序的（由大至小/由小至大）
最优二叉树或哈夫曼树：WPL（带权路径长度）最小的二叉树
如何构造哈夫曼树？ *每次把权值u最小的两颗二叉树合并
具体来说，假设共有5个叶节点，权值为{1,2,3,4,5}
[1] 首先挑出两个权值最小的组成一颗二叉树（1, 2），这个二叉树的根节点的值是叶节点的和（3）
[2] 拿这个根节点与之前剩下的叶节点集合做对比，取出两个最小的，重复以上操作
[3] 循环直至集合中只剩下一个元素
具体实现：这个集合可以用最小堆来实现
哈夫曼树的特点：
（1）不存在度为1的节点（每次都是两两并在一起）
（2）n个叶节点的Huffman树共有2n-1个节点
（3）哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树
（4）对同一组权值，可能存在不同构的多棵哈夫曼树