马上要面试了，再复习下面试常见的基础概念。

二叉树，事务，TCP/UDP区别，线程调度算法，Hash和HashMap，排序建议

二叉树的定义：树有且仅有一个根节点，除根节点外，每个子节点仅有一个父节点，且最多有两个子节点（可没有或者仅有一个），子节点有左右之分。 二叉树的结构：存储可以使用顺序存储（类似数组），可使用链式存储。当然链式存储更加灵活多见。链式存储结构类似线性链表，每个节点结构包含三个要点：数据，左子节点指针，右子节点指针。（注意，并未记录父节点指针）

struct BiTreeNode{
T value;
BiTreeNode* pLeft;
BiTreeNode* pRight;
};

二叉树的遍历：因为二叉树是个递归结构，主要包含三部分：根节点（N），左子节点（L），右子节点（R）。所以对其遍历有六种方案：NLR、LNR、LRN、NRL、RNL和LNR。 但因为有对称性，只要了解三种即可，另外三种完全对称。NLR、LNR和LRN分别为“先序遍历”、“中序遍历”和“后序遍历”。 递归方式的二叉树遍历比较简单：以中序遍历为例：

//中序遍历--递归 
int traverseBiTreeInOrder(BiTreeNode *ptree,int (*visit)(int)) 
{ 
    if(ptree) 
    { 
        if(traverseBiTreeInOrder(ptree->left,visit)) 
            if(visit(ptree->c)) 
                if(traverseBiTreeInOrder(ptree->right,visit)) 
                    return 1; 
        return 0; 
    }else return 1; 
} 
// 前序则是先遍历根节点 
int traverseBiTreePreOrder(BiTreeNode *ptree,int (*visit)(int)) 
{ 
if(ptree) 
{ 
    if(visit(ptree->c)) 
        if(traverseBiTreePreOrder(ptree->left,visit)) 
            if(traverseBiTreePreOrder(ptree->right,visit)) 
                return 1; //正常返回 
        return 0; //错误返回 
    }else return 1; //正常返回 
}

还可以进行非递归的遍历，但要自行解组二叉树填充栈结构，较复杂不再赘述。

满二叉树的定义：除最后一层外，所有层上的节点数均达到最大值的二叉树。 完全二叉树的定义：除最后一层外，所有层上的节点数均达到最大值（即一定为满二叉树）；在最后一层上仅允许缺少右边的节点。 如图为合理的完全二叉树：

图解释：上三层为满层。最后一层未满。最后一层仅右侧节点缺失，左侧为完整。 二叉搜索树（又称为 二叉查找树，二叉排序树）的定义：它或者是一个空树，或者是具有以下性质的二叉树：若其左子树不为空，则其左子树上的所有节点均小于其根节点的值；若其右子树不为空，则其右子树的所有节点均大于其根节点的值；其左右子树必然也为二叉搜索树。 如图为一个合理的二叉搜索树：

意义：对二叉排序树进行中序排序可得到一个有序序列。将一个无序数组（树）排序为一个二叉排序树，即为排序过程。其操作的时间复杂度等于树高O(log(2n))

平衡二叉树（又称为 AVL树-因为是AV和L这俩人发明的）的定义：它是一颗空树，或者他的左右两个子树高度差的绝对值不超过1，并且左右子树都是一颗平衡二叉树。 如图是一颗平衡二叉树：

图解释：只有23，54和72的子节点有1的高度差，其他节点左右子树没有高度差。 意义：因为二叉搜索树，其操作的时间复杂度为O(log2n)，取决于树高。当极端情况下（想一下链表或上图中的16-17-16的节点），若二叉搜索树退化为链表状态，其时间复杂度将退化为线性的O(n)。显然这种效率不是我们期望的，于是我们可以将二叉搜索树优化为平衡二叉树，因高度可以良好维持在O(log2n)，所以可以提高其时间复杂度。 将无序树排序为二叉搜索树的算法为核心,之后将额外专文说明。

红黑树的定义：它是一个自平衡二叉查找树（也可理解为是平衡二叉树的一种算法结构），或者我们可以认为是自带颜色属性的二叉查找树，颜色为红色或者黑色。对于颜色定义有以下要求： 1：根节点必然为黑色 2：空节点必然为黑色。 3：一个红节点其两个子节点必然为黑色。 4：从任意一节点到其每个子节点的路径中必然包含相同数目的黑色。 下图为一个合理的红黑树：

因为上述4个约定的强制要求，则保证了红黑树的关键性质： 其根节点到叶节点最长高度不可能多于最短高度路径的两倍。 该性质保证了红黑树的操作时间复杂度会稳定较低，为O(log(n))。C++的STL中大量使用了红黑树。

堆排序HeapSort的定义：它是算法，是选择排序的一种。它利用数组快速定位元素的特点，将数据组成为一个二叉堆。二叉堆一定是一个完全二叉树，但其又有些定义类似二叉搜索树。 二叉堆的定义：1：父节点值，一定大于等于（小于等于）其两个子节点任一节点值。 2：每个节点左右子树一定也是一个二叉堆。（注意：必须和全树都是大根堆或者小跟堆，必须全局一致。） 二叉堆分为大根堆和小根堆。大根堆的父节点大于等于子节点值，所以，大根堆的根节点一定是最大的值。小根堆反之。 如图所示为一个小根堆：

我们一个乱序数组，目标是最终得到如下的数组堆。该过程就是堆排序。

堆排序的意义：排序时使用空间复杂度较少，时间复杂度和快排差不多。因为堆排序最终生成的是一个二叉堆（即一个有序的完全二叉树），二叉堆有其有序性，常用于A*寻路。 注意点：堆 处于半有序状态。并非完全的有序（可看上图，并非10,15,25,30,56,70的完全有序），但又并非完全无需。只需建堆，则可获得有序数列。 堆排的大致思路：如图：

1：无序数组建堆。 2：循环（条件为:堆不为空。从最后一个非叶子节点开始，自下向上的顺序迭代） { 取得堆顶元素 得到最后一个元素，将其移动到堆顶 调整使其再次成堆 } 解释： 图1：用数组建无序完全二叉树。 图1：找到最后的非叶的子节点97并调整父子位置 图2:图3图4：自下向上自右向左遍历，检查65,38,49节点 图5：因为图4的调整，则需要对调整的子节点复检，重新构子堆。 图6：得到小根堆（小顶堆）。 代码：

//堆调整算法 
void HeapAdjust (HeapType &H, int s, int m) 
{ 
    // 已知 H.r[s..m]中记录的关键字除 H.r[s] 之外 
    //均满足堆的特征，本函数自上而下调整 H.r[s] 
    //的关键字，使 H.r[s..m] 也成为一个大顶堆 
    rc = H.r[s]; // 暂存 H.r[s]
    for ( j=2*s; ;=m; j*=2 ) { 
        // j 初值指向左孩子自上而下的筛选过程; 
    } 
    // 自上而下的筛选过程 
    if ( ;m; H.r[j].key;H.r[j+1].key ) ++j; 
    // 左/右“子树根”之间先进行相互比较 
    // 令 j 指示关键字较小记录的位置 
    if ( rc.key;= H.r[j].key ) break;
    // 再作“根”和“子树根”之间的比较， 
    // 若“>=”成立，则说明已找到 rc 的插 
    // 入位置 s ，不需要继续往下调整 
    
    H.r[s] = H.r[j]; s = j; 
    // 否则记录上移，尚需继续往下调整 
    
    H.r[s] = rc; // 将调整前的堆顶记录插入到 s (注意插入的位置为s j=2*s) 
} // HeapAdjust

事务的定义：事务是一组逻辑操作单元。使数据从一种状态变化为另外一个状态，对数据的增删改查都是事务操作。 事务的使用标示：以为BEGIN TRANSACTION开始，以COMMIT或者ROLLBACK结束。事务的四大特性：ACID A原子性：事务是数据库的逻辑工作单元，事务中的众多操作要么全做，要么全部不做。不能只执行其中一部分。 C一致性：事务执行的结果必然是将数据库从一个状态转变成另一个状态。无论你对数据库建立多少链接，可以保证其获取的信息是绝对一致的。 I隔离性：一个事务的执行不允许被其他事务干扰。例如事务A读取了数据，然后事务B修改了数据，但事务A中并不了解事务B中的行为（互不干涉性），所以事务A读取的仍然书先前的数据，事务B的任何操作对事务A无影响。

D 永久性：一个事务一旦被提交，它对数据库的改变将是永久性的。事务操作均将直接写入磁盘，但注意，该写入操作并不保证是及时的，其时间不可确定。

TCP和UDP的区别，TCP的三次握手和四次分手

区别： 1：TCP是连接型协议，在数据传输前需要握手建立连接。UDP则是非连接型协议，每次数据传输时才直接发送。 2：TCP对系统资源较高，首先它要维护一个连接状态，有自己的拥挤控制算法，要维持一个连接状态表，还要自己进行包的拆分和合并，在消息报文中的信息较多，20字节。但UDP不需要这些，不维护状态表，不受算法控制，同时也不进行包的处理，直接报文发送，其消息包头只有8字节。 3：TCP包为流模式发送，UDP包为数据报模式。 4：TCP可以保证数据正确性和顺序性。UDP可能丢包，也不保证数据的顺序性。 例： ping就是UDP。我个人认为QQ聊天消息应该是UDP协议。 要保持长连接的就是TCP。 小记要点： TCP/IP协议是一个协议簇，包含了UDP和TCP协议以及IP协议。因为TCP和IP两个协议比较重要，所以如此命名。 所以“TCP/IP协议和UDP协议的区别？”这种问题是不恰当的。 另外，TCP和UDP协议不同，所以其端口号即使相同也是没有问题的。例如TCP的8080端口被占用，UDP的8080端口依然可以正常使用。

TCP三次握手： 1：A向B发送一个同步序列号SYN标示位的数据，请求链接。 2：B收到后，给A一个ACK应答和同步序列号SYN，回应收到链接，同时告知A“我的同步序列号SYN是什么”， 3：A收到后，最后给B一个收到确认。 TCP四次分手： 1：请求断开连接的主机A，在发送自己的最后一份数据之后，将控制位FIN修改为1(true)，提出分手。 2：B收到A的FIN请求后，关闭自身链接，ACK设为1。 3：B将控制位FIN修改为1(true)，向A提出分手确认。 4：A收到，将自身ACK设为1。 至此双方分手完毕。

（吐槽一句：牵手累，分手更累……）

线程调度算法: 1.先到先服务算法。若多服务的占用时间不均，则很不公平。 2.时间片轮转算法。处理器时间切分为多个时间片段，轮转的方式分配给每一个线程。当线程主动放弃或者时间段用尽，则轮转为下一个线程使用。简单高效。 3.优先级调度算法。时间片轮转算法是假设所有线程重要级别一致。但通常前台线程要求更高优先级，所以需要对上述的线程队列进行一个排序调整，高优先级的线程执行顺序优先。 但部分高优先级线程可能霸占处理器不放，所以建议变种使用动态优先级。连续执行多个时间片的线程，调低其优先级；长时间没有得到时间片的线程提高其优先级。

Windows的调度算法是抢占式的，支持多处理器的优先级调度算法。每个处理器有自己的一个链表数组，相同优先级的线程在同一个链表中。

Hash-map就是链式数组，比数组好增删，比链表好查找访问。 步骤： 1：得到Key: 2：对Key进行Hash 3：根据得到的Hash值与桶（数组）个数求模，找到数组桶，塞到数组里。 Hash的原理就是大数据转为小数据。 其核心问题有三： 1：冲突率和占用空间大小。 2：散列分布的均衡性。

3：哈希函数的执行效率。

说到排序，尽量全部优先使用shell希尔排序(时间复杂度O(n^2)属于插入排序的优化)，之后发现速度不够的话，那就快速排序，要是数据太大，空间不足，就堆排序。这就是排序的”万能选择流程”。