二叉排序树的定义,平衡二叉树和某接点的平衡因子的定义

发布网友发布时间：2022-05-20 21:35

共2个回答

热心网友时间：2024-03-05 12:12

某个节点的平衡因子就是那个节点左子树的高度减去右子树的高度，你可以对照左边的图检查一下是不是这样
比如a节点的因子就是它左边的子树的高度，这里是3，减去右子树的高度，这里是2，所以=1
对于b节点，左子树高度为1，右边为2，所以1-2=-1就是b节点的平衡因子

热心网友时间：2024-03-05 12:13

　　二叉排序树也称二叉查找树。它或者是一棵空树；或者有性质：（1）若其左子树不空，则左子树上所有结点的值均小于根结点的值。（2）若其右子树不空，则右子树上所有结点的值均大于根结点的值。（3）左右子树也为二叉排序树。
　　平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：(1)左、右子树都是平衡二叉树；(2)左、右子树高度差的绝对值<=1。
　　若把左子树与右子树高度之差称为结点x的平衡因子(balance factor)，用bf(x)表示。
　　则由平衡二叉树定义知:Bf(x)=x左子树深度-x右子树深度