首先，树的一些基本概念是：节点，父节点，子节点，兄弟节点，根节点，叶节点；height（从叶节点向上），depth（从根节点向下到0^(n-1)），layer（从根节点开始1~n）；n为层数；2、二叉树的一些基本概念：左子节点，右子节点；二叉树要求每个节点最多只能有两个子节点，但不要求有两个子节点，可以单独有一个左子节点或者一个右子节点；满二叉树是指所有叶子节点都在底部，除了叶子节点，每个节点都有左右两个子节点；完全二叉树是指所有的叶子节点都在下面两层，最后一层的叶子节点从左到右依次排列，中间不能有空隙，其他层的节点个数必须达到最大值，不能有差距；存储方式包括链式存储方式和顺序存储方式。大多数二叉树都可以用下面的链式存储方式表示，左右节点空间必须指向各自的左右子节点；二叉树链式存储的顺序存储方式是用数组将当前节点存储在下标为i的地址中，然后左子节点存储在2i的地址中，右子节点存储在地址中2i+1；反之，已知某节点的位置为k，则其父节点的位置为k/2；但是当二叉树不是完全二叉树时，会浪费数组的存储空间；因此，当二叉树是完全二叉树时，使用顺序存储是最优的；完全二叉树的顺序存储和非完全二叉树的顺序存储遍历分为前序遍历、中序遍历和后序遍历；前序遍历，先self，再left，最后right；中序遍历，先向左，再向自身，最后向右；后续遍历，先向左，再向右，最后向自身；3、二叉查找树基于二叉树，满足如下条件：对于任意一个节点，其左子树上的每个节点的值必须小于当前节点的值，并且每个节点的值其右子树的值必须大于当前节点的值；搜索，目标元素target与当前节点比较，如果小于当前节点，则在左子树中如果小于当前节点且当前节点没有左子树，则作为左子节点插入。如果有左子树，则继续向左遍历；如果比当前节点大，且当前节点没有右子树，则将其作为右子节点插入，如果有右子树，则继续向右遍历；删除，先找到目标元素，如果目标没有子节点，直接删除即可；如果目标有子节点（左右子节点均可），则只需将目标节点的父节点指向目标节点的子节点即可；如果目标节点同时有左子树和右子树，那么需要在子树中找到最小值替换when前端节点；（如果想提高删除的性能，还是可以使用标记删除的方式，用空间换时间）二叉搜索树的删除操作是找最大值和最小值；找到给定元素的前驱节点和后继节点；中序遍历输出一个完全有序的序列，时间复杂度为O(n)，与前面提到的八种排序算法相比，是最好的排序算法；重复数据的存储；相同的值存储在同一个节点中；相同的值存储在右子树中；但是在查找和删除的时候，需要遍历到叶子节点，找到所有相同的元素；时间复杂度分析，在最坏的情况下，二叉搜索树退化为一个链表，那么所有操作的时间复杂度都是O(n)，但是在一棵完全二叉树中，时间复杂度取决于树的高度，这是O(logn)；4、如何平衡二叉搜索树，让二叉搜索树尽可能保持平衡，将时间复杂度保持在O(logn)，这就是平衡二叉搜索树要做的事情。那么什么样的二叉搜索树才能称为平衡二叉搜索树呢？严格的定义是：任意节点的左右子树的高度差不能大于1；比如AVL树，就是一种高度平衡，完全符合平衡二叉树的定义。然而，更严格的平衡二叉树的实现有点复杂，需要消耗太多的资源。在天平高差不超过1的情况下，就大材小用了。所以，我们只要能设计出一棵二叉搜索树，使得所有节点的左右子树看起来比较平衡，也可以称为符合要求的平衡二叉搜索树，比如下面的红黑树。5、红黑树红黑树是一种松平衡的二叉查找树，它有如下要求：根节点为黑色；每个叶子节点都是黑色的空节点，不存储任何数据；任何相邻的所有节点都不能同时为红色，红色节点由黑色节点隔开；从每个节点到其所有叶节点的路径包含相同数量的黑色节点；插入的节点必须是红色的，新插入的节点都放在叶节点上；在红黑树中插入节点时，如果父节点为黑色，则直接插入；如果插入的节点是根节点，则将其变为黑色；否则无论如何，上述红黑树的要求都会被破坏。这时候就需要左转，右转，或者改变颜色，再次满足红黑树的要求。红黑树的实现过程和平衡过程比较复杂，大致了解一下即可。红黑树性能稳定，插入、删除、查找时可以稳定在O(logn)。同时也不会浪费过多的资源进行均衡的操作。因此，在工业应用中，它优于严格平衡的二叉搜索树。为了更受欢迎。6.递归树递归树主要可以用来分析复杂算法的时间复杂度；比如前面提到的归并排序的时间复杂度是O(logn)。如何使用递归树对此进行分析？归并排序的递归树归并排序过程是每次分解1/2直到每个节点只有一个元素，然后从下到上对相邻节点进行合并排序，直到合并成一个序列。分解过程耗时比较小，因为可以利用数组的随机访问特性一分为二，所以时间可以记为常量C；合并时，每一层需要比较n个元素，所以时间复杂度为O(n)，假设树的高度为h，则时间复杂度为O(hn)，如何计算高度？当二叉树满时，树的高度可以表示为logn，所以合并过程的时间复杂度约为O(nlogn)，那么整个分解合并的时间复杂度为O(C+nlogn)，去掉低阶，最后归并排序的时间复杂度为O(logn)。7、总结一下二叉树比哈希表有什么优势？哈希表中的数据是乱序存储的。如果我们需要一个有序的序列，我们必须先对它进行排序。时间复杂度取决于你使用的排序算法和无序数据的排列方式，但肯定不会比O(n)好，但是二叉查找树，也就是二叉排序树，自然是有序的，如只要按照中序遍历输出，时间复杂度稳定在O(n)；哈希表有扩容操作，哈希计算操作，会存在冲突重新哈希的问题，时间效率不稳定；而平衡二叉树可以使查找、插入、删除的时间复杂度稳定在O(logn)；当数据量很大时，二叉树的平衡优势和性能将远远超过哈希表；哈希表的实现比较复杂，需要考虑哈希函数的设计、加载因子的设计、扩缩容方案、如何解决冲突和重新哈希等；而平衡二叉树只需要考虑平衡的问题就比较简单，方案也比较成熟。
