二叉排序树、表达式树

1. 二叉排序树（BST）

1. 平衡树——AVL(不需要代码实现，熟记操作)
   (1) 定义：满足如下条件的树：
   a. 是二叉查找树
   b. 每个节点的左子树和右子树的高度差最多为1
   (2) 平衡因子：一个结点的左子树的高度减去右子树的高度，可取-1、0、1三种值
   (3) 平衡操作：

2. 不改变中序遍历，如果改变说明旋转错误（只会改变树的高度）

3. 首先从下往上找到最小不平衡子树（平衡因子大于1的）

4. 看不平衡子树的类型进行操作,旋转也是从下往上进行的

   （LL右旋，RR左旋，LR先左旋在右旋，RL先右旋再左旋）
   

   • 例子：
     
     (4)平衡数高度：log（2，n）

1. 表达式树

• 非叶结点是运算符，叶子结点是数值
• 中序遍历是表达式的正常计算顺序
• 后序遍历就是这个式子的后缀表达式，前缀表达式同理
• 做表达式树类型的题目时，问需要的顶点个数，意思就是把树中重复的结构结点删除（调用剩下唯一部分结点的值
  剩下的结点数就是

1. 考题：2011-7、2012-4、2013-3(PDF中的分析有误，以上课讲解为准)、2013-6、2015-4、2018-6、2019-4、2019-6、2020-5、2017-41

2. 给定序列不能构成二叉排序树查找的做法：

   直接根据序列画出二叉排序树，然后写出中序序列，若中序有序就是正确，否则不正确。

3. 平衡二叉树，非叶结点平衡因子为1 ，求总结点数