• 前序遍历：根结点 —-> 左子树 —-> 右子树
  • 中序遍历：左子树—-> 根结点 —-> 右子树
  • 后序遍历：左子树 —-> 右子树 —-> 根结点
  • 层次遍历：仅仅需按层次遍历就可以

比如。求以下二叉树的各种遍历
Tree-树 - 图1
前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8

广度优先搜索BFS（层序遍历）队列-先进先出

深度优先遍历DFS（前序遍历）-回溯递归

B树和B+树的区别、还有hash索引的区别？

1） B树每个节点都存储了key和data，B+树的data只存储在叶子节点上。

节点不存储data，就可以存储更多的key，使得树变矮，查询操作效率更高，执行的越快。

2） 树的所有叶子节点构成了一个有序列表，可以按照关键码的次序遍历全部记录。

由于数据顺序排列并相连，所以便于区间查找和搜索。而B树需要每一层的递归遍历。

为什么不使用哈希索引：

哈希索引的绝对优势是在没有出现哈希碰撞时查询时间复杂度是O(1)，查询速度非常快，但他有很多缺点；
不支持范围查询
不支持索引完成排序

B树（为磁盘而生）

B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。
与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

B+树

也是多路平衡查找树，其与B树的区别主要在于：

B树中每个节点（包括叶节点和非叶节点）都存储真实的数据，B+树中只有叶子节点存储真实的数据，非叶节点只存储键。在MySQL中，这里所说的真实数据，可能是行的全部数据（如Innodb的聚簇索引），也可能只是行的主键（如Innodb的辅助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。
B树中一条记录只会出现一次，不会重复出现，而B+树的键则可能重复重现——一定会在叶节点出现，也可能在非叶节点重复出现。
B+树的叶节点之间通过双向链表链接。
B树中的非叶节点，记录数比子节点个数少1；而B+树中记录数与子节点个数相同。

平衡二叉树&红黑树

平衡二叉树

查找、插入和删除在平均和最坏情况下的时间复杂度都是O ( log ⁡ n )
由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。

  1. # 平衡二叉树AVL
  2. class TreeNode(object):
  3.     def __init__(self,val):
  4.         self.val = val
  5.         self.left = None
  6.         self.right = None
  7.         self.height = 1
  9. # AVL tree class 
  10. class AVL_Tree(object):
  11.     def get_height(self, root):
  12.         if not root:
  13.             return 0
  14.         return root.height
  16.     def get_balance(self, root):
  17.         """balace factor of tree"""
  18.         if not root:
  19.             return 0
  20.         return self.get_height(root.left) - self.get_height(root.right)
  22.     def right_rotate(self, root):
  23.         new_root = root.left
  24.         T3 = new_root.right
  26.         new_root.right = root
  27.         root.left = T3
  29.         # update heights
  30.         root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
  31.         new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))
  33.         return new_root
  35.     def left_rotate(self, root):
  36.         new_root = root.right
  37.         T2 = new_root.left
  39.         # rotation
  40.         new_root.left = root
  41.         root.right = T2 
  43.         # update heights
  44.         root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
  45.         new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))
  47.         return new_root
  49.     def insert(self, root, key):
  50.         # step 1. perform normal BST
  51.         if root:
  52.             print(root.val)
  53.         if not root:
  54.             return TreeNode(key)
  55.         elif key < root.val:
  56.             root.left = self.insert(root.left, key)
  57.         else:
  58.             root.right = self.insert(root.right, key)
  60.         # step 2. update the height of the ancestor node
  61.         root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
  63.         # step 3. get the balance factor
  64.         balance = self.get_balance(root)
  66.         # step 4. If the node is unbalanced, then try out the 4 cases
  67.         # case 1. left left
  68.         if balance > 1 and key < root.left.val:
  69.             return self.right_rotate(root)
  70.         #case 2. right right
  71.         if balance < -1 and key > root.right.val:
  72.             return self.left_rotate(root)
  73.         # case 3. left right
  74.         if balance > 1 and key > root.left.val:
  75.             root.left = self.left_rotate(root.left)
  76.             return self.right_rotate(root)
  77.         # case 4. right left
  78.         if balance < -1 and key < root.right.val:
  79.             root.right = self.right_rotate(root.right)
  80.             return self.left_rotate(root)
  81.         return root
  83.     def preorder(self, root, result=[]):
  84.         """Parent - left - right"""
  85.         if not root:
  86.             return result
  87.         result.append(root.val)
  88.         result = self.preorder(root.left, result)
  89.         result = self.preorder(root.right, result)
  90.         return result

红黑树

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它可以在 O ( log ⁡ n ) {\displaystyle {\text{O}}(\log n)}O(logn)时间内完成查找、插入和删除，这里的 n 是树中元素的数目。
image.png