#博学谷IT学习技术支持#
- 一、二叉树
- 1、什么是树
- 2、什么是节点、度和树高
- 3、什么是二叉树
- 4、二叉树的结构图
- 二、二叉查找树
- 1.、什么是二叉查找树
- 2、二叉查找树的特点
- 3、二叉查找树节点添加规则
- 三、平衡二叉树
- 1、什么是平衡二叉树
- 2、二叉平衡树的特点
- 3、二叉平衡树的旋转
- 1.产生旋转的原因
- 2.旋转
- 3、平衡二叉树的四种旋转情况
树是一种非线性结构。树有一个特殊的节点，叫做根节点。根节点是一个树的起点，除根节点外，它下面的节点被分为很 多的分支。由这些分支和根节点共同组成，形状像倒挂的树，根在上，叶子在下的结构就叫做“树”。2、什么是节点、度和树高
- 在树的结构中，每一个元素称为节点。
- 每一个节点的子节点数量就叫做度。
- 从根节点到最长路径末端子节点的个数
一个有序树的任意节点的度不超过2的树就称为二叉树。4、二叉树的结构图
图示树高为3，左子树树高为2，右子树树高为2。二、二叉查找树 1.、什么是二叉查找树
具有一定查找规则的二叉树就称为二叉查找树，也称二叉排序树或者二叉搜索树。2、二叉查找树的特点
-
它具有二叉树的特点，每个节点的度不超过2
-
左子树的所有节点的值都小于根节点
-
右子树的所有节点的值都大于根节点
左图中根节点9右边存储的2，1小于9，明显不符合二叉查找树规则，所以为普通二叉树。而右图满足。
- 大的存左边
- 小的存右边
- 数据重复则不存
因为二叉查找树如果添加大量大于(小于)根节点的数据，会导致一端的子树过于臃肿，为了解决这个问题，在满足二叉 查找树的条件下，满足一定的特点的二叉查找树便称为二叉平衡树。2、二叉平衡树的特点
- 二叉树左右两个子树的高度差的绝对值不超过1
- 任意节点的左右两个子树都是一颗平衡二叉树
当平衡二叉树添加了结点之后，该树便不再是平衡二叉树了。为了使添加后的树依旧保持使二叉平衡树，就需要进行旋 转来维持。2.旋转
- 左旋：就是将根节点的右侧向左侧移动，原来根节点的右节点变为根节点，根节点降级变为新根节点的左子节点。左旋时，根节点的右节点如果有左子节点，则将该左子节点让给降级的根节点作为它的右子节点。
- 右旋：将根节点的左侧向右侧移动，原根节点的左节点变为根节点，根节点降级为新根节点的右子节点。右旋时，根节点的左节点如果有右子节点，则将该右子节点让给降级的根节点作为它的左子节点。
-
左左：当根节点的左子树的左子树有节点插入时，直接进行整体的右旋即可。
-
右右：当根节点的右子树的右子树有节点插入时，直接进行整体的左旋即可。
-
左右：当根节点的左子树的右子树有节点插入时
解决方法：先将插入节点对应的左子树进行左旋，再对整体进行右旋即可。
-
右左：当根节点的右子树的左子树有节点插入时
解决方法：先将插入节点对应的右子树进行右旋,在对整体进行左旋即可。
这是我学习中遇到的问题和解决方案，发该博客是为了记录遇到的这些情况，希望可以给看到的你有所帮助，如有不足，请指出。
