本文共 2385 字，大约阅读时间需要 7 分钟。

二叉树

1. 二叉树由节点组成，每个节点有左右子节点，子节点可为空，节点和节点之间有父子节点，兄弟节点，根节点，叶子节点；

2. 树的高度，从下往上度量，树的深度，从上往下度量，层和深度类似，不过是从 1 计数；

   

3. 如果叶子节点全在最底层，并且除叶子节点外，其他节点都有左右两个子节点，这种二叉树就叫做满二叉树；

   

4. 如果叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都达到最大，这种二叉树叫作完全二叉树；

   

二叉树的存储

1. 链式存储，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针，是大部分二叉树的存储方式；

2. 顺序存储法，即使用数组存储，如果一个节点存储在下标 i 的位置，那么左子节点存储在下标 2* i 的位置，右子节点存储在 2* i + 1 的位置，相反一个下标 i 的位置，其父节点就在 i/2 的位置；

3. 顺序存储，适合用在完全二叉树中，根节点存储在 i = 1 的位置，如果是非完全二叉树，数组中元素不连续，造成很多浪费；

二叉树的遍历

1. 有前序，中序，后序遍历，前中后是针对根节点的位置，如中序遍历，就是先输出根节点，后输出左子树，最后输出右子树；

2. 前序，中序，后序遍历，都是一种递归的概念，很容易用递归实现；

// 前序遍历	void preOrder(Node* root) {
     		if (root == null){
    			return;  		}		print root // 伪代码，表示打印root节点  		preOrder(root->left);  		preOrder(root->right);	}

3. 遍历的时间复杂度是 o( n )，因为每个节点都是常数次的访问；

4. 按层遍历，可以从第一层开始，将根节点放入队列中，然后循环从队列中取出元素，每取出一个元素输出，并将其左子节点和右子节点分别放入队列中，直到队列为空；

5. 给定一组数据，如 1，3，5，6，9，10，可以构建出多少种不同的完全二叉树；

完全二叉树可以用数组存储，那么即 6 个元素，如何排列组合，即 6! 个组合

6. 给定一棵二叉树，求其确切高度；

一种方式，层序遍历，遍历一层 + 1	第二种方式，二叉树高度 = max（左子树高度，右子树高度） + 1

二叉查找树

1. 要求任意一个节点，左子树任意节点值都小于该节点，右子树任意节点值都大于该节点，支持快速的数据插入，删除和查找；

查找：先在根节点查找，如果小于根节点，在左子树递归查找，如果大于根节点，在右子树递归查找	插入：通用从根节点开始比较，如果插入元素比节点值大，且其右子节点为空，那么将插入元素，赋值给其右子节			点，如果右子节点不为空，继续在其右子树遍历查找，直到满足，插入元素比其大，且其右子节点为空		如果插入元素比节点小，且其左子节点为空，同样新插入元素为其左子节点，如果左子节点不为空，遍历左子树继续查找	删除：如果要删除的节点，没有子节点，直接将其父节点的子节点赋值为 null 即可		如果要删除的节点，只有一个子节点，那么将其父节点的子节点赋值为该子节点即可		如果要删除的节点，有两个子节点，需要在其右子树，找到最小节点（肯定没有左子树了），将其移动到要删除节点的位置

2. 二叉查找树的删除操作，也可以不真正删除，只标记删除，这样多占用一定内存空间，但对查找，插入操作无影响；

3. 二叉查找树，查找最大节点，最小节点，前驱节点，后继节点的算法操作；

4. 二叉查找树，一个特性是，将其中序遍历，得到的就是树节点的有序排列，时间复杂度 o( n )，在排序算法中，非常高效；

5. 以上讨论的都是，没有相同元素的二叉查找树，如果允许二叉查找树中，存在相同元素，一种方案是相同元素组成一个链表存放在同一位置，另一种解决方案是将相同元素当作大于该元素处理；

第二种方案中，需要对插入，查找，删除操作进行改写	插入操作中，碰到相同元素，在其右子树中找位置插入	查找操作中，碰到相同元素，不停止查找，继续在右子树查找，直到遇到叶子节点，这样可以得到所有相同元素	删除操作中，先通过查找，找到所有相同元素，然后每一个都按照之前的删除策略删除

6. 二叉查找树的插入，删除，查找的最好时间复杂度是 o( logn )，logn 表示完全二叉树的高度，极度不平衡的二叉查找树时间复杂度会退化到 o( n )；

完全二叉树，n 个节点，假设层数是 L	最后一层只有一个元素：n >= 1+2+4+8+...+2^(L-2)+1		最后一层元素达到最大：n <= 1+2+4+8+...+2^(L-2)+2^(L-1)	得到 L 的范围是[log2(n+1), log2n +1]	所以完全二叉树的高度小于等于 logn

二叉查找树和散列表

1. 二叉查找树，在 o( n )可以排序，而散列表是无序；

2. 二叉平衡树，插入，查找，删除元素的性能非常稳定 o( logn )，而散列表如果扩容，或散列冲突，性能都不太稳定，且 o( 1 ) 常量级，在一定数据规模，并不一定比 o( logn ) 高效很多；

3. 散列表需要考虑散列函数，冲突解决，扩缩容，平衡二叉树，只需要考虑保持平衡性，解决方案也成熟可靠；

红黑树

1. 平衡二叉树，要求任意节点的左子树和右子树高度相差不大于1，红黑树，不是严格的平衡二叉树，但基本平衡，树高度是对数级；

2. 红黑树，节点被标记为黑色或者红色，根节点是黑色，叶子节点都是黑色的空节点，不存储数据，任何相邻节点不能都是红色，每个节点，到达叶子节点的所有路径，都包含相同数目的黑色节点；

3. 红黑树，是通过左旋，右旋进行平衡；

递归算法的时间复杂度

1. 递归算法的时间复杂度，可以借助递归树来分析，将算法分解为递归树，将每一层的时间消耗，乘以递归树的高度，就得到了总的时间复杂度；

转载地址：http://rsfin.baihongyu.com/