请问每个节点的平衡因子是怎么计算的?能详细说下吗?先让我入门了讲解简单易懂点,找资料一大堆就是没人讲清楚的。
就跟这张图中平衡二叉树(1):
5的树根节点为什么是3-2呢? 跟节点5的深度是3吗?那平衡因子的求法就是 :平衡因子BF=左子树深度-右子树深度.
那深度值3是根节点怎么变成左子树了?右子树的深度值2是谁?根节点5是左子树?
2的节点平衡因子为什么是1-2=-1; 请问1的深度值是哪个节点了?2的深度值又是哪个节点了?
麻烦将平衡二叉树和不平衡二叉树的平衡因子求法详细说明下吧。
所谓的左右子树,是以当前节点为父节点,其左右节点对应的树就是左右子树。
5节点的深度是4(5-2-4-3),5节点的左节点是节点2,对应的左子树深度是3(2-4-3),5节点的右节点是节点6,对应的右子树深度是2(6-7)。
其他同理。
平衡二叉树本身是一个二叉树且是一颗空树或者左右子树的高度差值(平衡因子)的绝对值小于1。
非平衡二叉树的平衡因子绝对值大于1。
平衡二叉树和非平衡二叉树计算因子公式都是一样的。