Java知识【二叉树&二叉查找树&平衡二叉树】

青旅半醒 2023-10-02 21:46 53阅读 0赞

#### 1，二叉树 ####

*  二叉树的特点
    
     *  二叉树中,任意一个节点的度要小于等于2
        
         *  节点: 在树结构中,每一个元素称之为节点
         *  度: 每一个节点的子节点数量称之为度
 *  二叉树结构图![6e35fcc7899b455ca2e7ded7e4d03b9c.png][]

#### 2，二叉查找树 ####

![02ed1a958cbd4c2dbb019ca3d1b860f7.png][]

*  二叉查找树的特点
    
     *  二叉查找树,又称二叉排序树或者二叉搜索树
     *  每一个节点上最多有两个子节点
     *  左子树上所有节点的值都小于根节点的值
     *  右子树上所有节点的值都大于根节点的值
 *  二叉查找树结构图![213744222d9943928f87cbc5d4b3e45c.png][]
    
    二叉查找树和二叉树对比结构图 ![9480384aca4e44f998ac9c284d107cb2.png][]
    
    二叉查找树添加节点规则
 *  小的存左边
 *  大的存右边
 *  一样的不存

#### 3，平衡二叉树 ####

*  平衡二叉树的特点
    
     *  二叉树左右两个子树的高度差不超过1
     *  任意节点的左右两个子树都是一颗平衡二叉树
 *  平衡二叉树旋转
    
     *  旋转触发时机
        
         *  当添加一个节点之后,该树不再是一颗平衡二叉树
     *  左旋
        
         *  就是将根节点的右侧往左拉,原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点

![1bf23dcacbed4080b4b06173d86559ae.png][] ![3a566568ed5f4e89ae87f42057122815.png][]

右旋

*  就是将根节点的左侧往右拉,左子节点变成了新的父节点,并把多余的右子节点出让,给已经降级根节点当左子节点

![577d3639a0b14404bde595015d30d791.png][]

![e684fac7c57b4b479831bcba9e91d5f3.png][] 平衡二叉树和二叉查找树对比结构图 ![b8314fdab7ef4660be4d0031cbec7e51.png][]

平衡二叉树旋转的四种情况

*  左左
    
     *  左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡
     *  如何旋转: 直接对整体进行右旋即可

![40526f9f6ef54bf0a157b1c3353983d6.png][]

左右

*  左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡
 *  如何旋转: 先在左子树对应的节点位置进行左旋,在对整体进行右旋

![f0fd5d853cd149dca9cb3d521274d7f7.png][]

右右

*  右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡
 *  如何旋转: 直接对整体进行左旋即可

![5c486a2a620a4de3a3da86c29d03ab6d.png][]

右左

*  右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡
 *  如何旋转: 先在右子树对应的节点位置进行右旋,在对整体进行左旋

![0f6a117461fa424cae2426eba0183c2a.png][]

[6e35fcc7899b455ca2e7ded7e4d03b9c.png]: https://img-blog.csdnimg.cn/6e35fcc7899b455ca2e7ded7e4d03b9c.png
[02ed1a958cbd4c2dbb019ca3d1b860f7.png]: https://img-blog.csdnimg.cn/02ed1a958cbd4c2dbb019ca3d1b860f7.png
[213744222d9943928f87cbc5d4b3e45c.png]: https://img-blog.csdnimg.cn/213744222d9943928f87cbc5d4b3e45c.png
[9480384aca4e44f998ac9c284d107cb2.png]: https://img-blog.csdnimg.cn/9480384aca4e44f998ac9c284d107cb2.png
[1bf23dcacbed4080b4b06173d86559ae.png]: https://img-blog.csdnimg.cn/1bf23dcacbed4080b4b06173d86559ae.png
[3a566568ed5f4e89ae87f42057122815.png]: https://img-blog.csdnimg.cn/3a566568ed5f4e89ae87f42057122815.png
[577d3639a0b14404bde595015d30d791.png]: https://img-blog.csdnimg.cn/577d3639a0b14404bde595015d30d791.png
[e684fac7c57b4b479831bcba9e91d5f3.png]: https://img-blog.csdnimg.cn/e684fac7c57b4b479831bcba9e91d5f3.png
[b8314fdab7ef4660be4d0031cbec7e51.png]: https://img-blog.csdnimg.cn/b8314fdab7ef4660be4d0031cbec7e51.png
[40526f9f6ef54bf0a157b1c3353983d6.png]: https://img-blog.csdnimg.cn/40526f9f6ef54bf0a157b1c3353983d6.png
[f0fd5d853cd149dca9cb3d521274d7f7.png]: https://img-blog.csdnimg.cn/f0fd5d853cd149dca9cb3d521274d7f7.png
[5c486a2a620a4de3a3da86c29d03ab6d.png]: https://img-blog.csdnimg.cn/5c486a2a620a4de3a3da86c29d03ab6d.png
[0f6a117461fa424cae2426eba0183c2a.png]: https://img-blog.csdnimg.cn/0f6a117461fa424cae2426eba0183c2a.png