数据结构-二叉查找树和平衡二叉树简介
二叉树
特点
二叉树中,任意一个节点的度要小于等于2
- 节点: 在树结构中,每一个元素称之为节点
- 度: 每一个节点的子节点数量称之为度
二叉树结点结构
二叉树结点结构共存储了四个数据，中间值为此节点存储的数据，父节点地址、左子节点地址和右子节点地址分别指向父节点左子节点地址和右子节点。二叉树中度的概念表示一个结点拥有子节点个个数，如一个结点拥有2个子节点，其度为2，没有子节点其度为0。
如上图树中最顶层的为根节点，与根节点7直接相连的4结点为7结点的左子节点，与根节点7直接相连的10结点为7结点的右子节点。图中蓝色框线区域为根节点7的左子树，而绿色框线区域为根节点右子树
二叉查找树
特点
二叉查找树,又称二叉排序树或者二叉搜索树；每一个节点上最多有两个子节点；左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值
二叉查找树示意图：
图中每个节点(只要存在)数据值其左子树值都是小于自己的，右子树值都是大于自己的
二叉查找树和二叉树对比结构图
如图中间二叉树存储的数据是无序的，而最右侧二叉查找树就是按照规则进行有序存储。
二叉查找树添加结点
添加节点原则：小的存左边，大的存右边，一样的不存
示例：
给定4个数据按照二叉查找树规则进行存储
存储后
第一步：首先拿到的节点为数据7节点，将数据7作为树的根节点
第二步：第二个数据4存储时会与7进行比较，小于7则作为7的左节点，大于7作为7的右节点，等于7则不存。此时4小于7则将4作为7的左节点
第三步：同第二步方式第三个数据10存到了节点7的右边
第四步：当拿到数据5时，会先于7比较，小于7会作为7的左节点，此时7已经有左节点，则再与7的左子节点4进行比较，5大于4则作为4的右子节点。此时，四个数据全部存储完毕
左旋右旋触发条件
当一个平衡二叉树因添加元素后不再是一个平衡二叉树时，则会通过旋转方式使其达到一颗平衡二叉树，旋转分为左旋和右旋
左旋
就是将根节点的右侧往左拉,原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点
右旋
就是将根节点的左侧往右拉,左子节点变成了新的父节点,并把多余的右子节点出让,给已经降级根节点当左子节点
平衡二叉树旋转的四种情况
左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡
如何旋转: 直接对整体进行右旋即可
左右：当根节点左子树的右子树有节点插入,导致二叉树不平衡
如何旋转: 先在左子树对应的节点位置进行左旋,在对整体进行右旋
右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡
如何旋转: 直接对整体进行左旋即可
右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡
如何旋转: 先在右子树对应的节点位置进行右旋,在对整体进行左旋