树

树的先序遍历

先处理当前节点再遍历子树

树的后序遍历

先遍历子树再处理当前节点

二叉树

每个节点最多有2个子节点

表达式树

用来描述算术表达式

表达式树.jpg

中序遍历（中缀表达式）

中缀表达式： 运算符在中间 (a + b) * c + d * e

后序遍历（后缀表达式）

后缀表达式： 运算符在后面 ab+c * de * +

先序遍历（前缀表达式）

前缀表达式： 运算符在前面 + * +abc * de

二叉查找树

• 有序的二叉树
• 左子树的节点值都小于当前节点
• 右子树的节点值都大于当前节点。

MakeEmpty
Find FindMax FindMin
Insert
Delete

AVL树（带平衡条件的二叉查找树）

每个节点的左子树和右子树的高度最多差1的二叉查找树

单旋转

双旋转

伸展树（动态二叉查找树）

每次查找后通过一系列的旋转把这个节点搬移到树根处

二叉树的遍历

中序遍历 先序遍历（计算树高度） 层序遍历

B-树

M阶B-树定义：

• 树的根要么是树叶要么儿子数在2和M之间
• 除去根节点，所有非叶子节点的儿子数在M/2和M之间
• 所有的树叶都有相同的深度