首先构造二叉排序树:

插入45,得到:

      45
     /  \
   null null

插入80,得到:

      45
     /  \
   null  80
         / \
       null null

插入48,得到:

      45
     /  \
   null  80
         / \
       48  null
      / \
    null null

插入40,得到:

      45
     /  \
   40   80
         / \
       48  null
      / \
    null null

插入22,得到:

      45
     /  \
   40   80
  / \
22  null
 / \
null null

插入78,得到:

      45
     /  \
   40   80
  / \   /
22  null 78
 / \
null null

判断是否为平衡二叉树,可以通过计算左右子树的高度差来判断。根据定义,平衡二叉树的任何节点的左右子树高度差不超过1。

对于根节点45,左子树高度为2,右子树高度为1,高度差为1,符合平衡二叉树的定义。

对于节点40,左子树高度为1,右子树高度为0,高度差为1,符合平衡二叉树的定义。

对于节点80,左子树高度为0,右子树高度为0,高度差为0,符合平衡二叉树的定义。

对于节点22,左子树高度为0,右子树高度为0,高度差为0,符合平衡二叉树的定义。

对于节点48,左子树高度为0,右子树高度为0,高度差为0,符合平衡二叉树的定义。

对于节点78,左子树高度为0,右子树高度为0,高度差为0,符合平衡二叉树的定义。

因此,该二叉树是一棵平衡二叉树,不需要调整。

如果该二叉树不是平衡二叉树,可以进行以下调整操作:

  1. 对于每个节点,计算其左右子树的高度差。

  2. 如果高度差超过1,则进行旋转操作。

  3. 旋转操作包括左旋、右旋、双旋等,具体操作可以参考AVL树的相关知识。

二叉排序树构建与平衡性判断:以示例演示

原文地址: https://www.cveoy.top/t/topic/oU9p 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录