二叉排序树构建与平衡性判断:以示例演示
首先构造二叉排序树:
插入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,则进行旋转操作。
-
旋转操作包括左旋、右旋、双旋等,具体操作可以参考AVL树的相关知识。
原文地址: https://www.cveoy.top/t/topic/oU9p 著作权归作者所有。请勿转载和采集!