二叉树，二叉查找树，平衡二叉树

一.绪论:

---

二.数据结构(二叉树):

1.简介:

1)每一个节点（也叫结点）都是一个独立的对象-->当中不仅要存数据值，还要存父节点地址值，左子节点地址值，右子 节点地址值

2)没有父节点或者子节点的节点就记为null

---

2.遍历方式:(适用于所有二叉树)

a.前序遍历:按照上->中->下的方式遍历

b.中序遍历:(重点)按照左->中->右的方式遍历(也是按小到大)

c.后序遍历:

d.层序遍历:

---

3.遍历方式的总结:

---

三.数据结构(二叉查找树):

1.概念:

---

2.添加节点:

规则：

---

3.查找结点：

要从根节点*开始查找，之后根据小的在左边，大的在右边进行查找即可

---

四.数据结构(平衡二叉树)：

1.规则:

该二叉树不是平衡二叉树，因为比如节点10的左子树高度为0，节点10的右子树高度为3，高度差为2，已经超过了1

注：规则中的任意节点是指同一个节点的左右子树，不是任意两个节点

2.实例：

该二叉树是平衡二叉树

节点7的左子树高度为2，右子树高度为1，高度差为1，符合规则

其他节点同理

---

五.数据结构(树)的演变:

---

六.平衡二叉树的旋转机制->用于保持二叉树的平衡:（平衡时不用旋转）

1.规则1->左旋:

例1:

改正后为：

例2：

---

2.规则2->右旋:

例1：

例2：

---

3.触发时机:当添加一个节点后，该树不再是一颗平衡二叉树(如果添加一个节点后仍旧是平衡二叉树，则不触发旋转机制)

---

七.平衡二叉树需要旋转的四种情况:

1.左左：当根节点左子树的左子树有节点插入，导致二叉树不平衡(一次右旋即可搞定)

例如:

插入节点后：

改正：

---

2.左右：当根节点左子树的右子树有节点插入，导致二叉树不平衡(不止一次才能搞定->

先局部左旋，再整体右旋)

例如：

插入节点后：

开始旋转：

但仍未平衡，继续旋转：

先要重新进行局部旋转

---

3.右右：当根节点右子树的右子树有节点插入，导致二叉树不平衡(一次左旋即可搞定)

例如：

添加节点后：

---

4.右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡(不止一次才能搞定->

先局部右旋，再整体左旋)

例如：

添加节点后：

开始旋转：

---