二叉排序樹的定義,平衡二叉樹和某接點(diǎn)的平衡因子的定義？二叉排序樹也稱為二叉搜索樹。它要么是空樹，要么具有以下屬性：（1）如果其左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值。（2） 如果右子樹不

二叉排序樹的定義,平衡二叉樹和某接點(diǎn)的平衡因子的定義？

二叉排序樹也稱為二叉搜索樹。它要么是空樹，要么具有以下屬性：（1）如果其左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值。（2） 如果右子樹不為空，則右子樹中所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值。（3） 左右子樹也是二叉排序樹。

平衡二叉樹是具有以下屬性的空樹或二叉排序樹：（1）左右子樹都是平衡二叉樹；（2） 左右子樹高差的絕對(duì)值

如果左右子樹的高差稱為節(jié)點(diǎn)x的平衡因子，則用BF（x）表示。

從平衡二叉樹的定義可知：BF（x）=x左子樹深度-x右子樹深度

二叉樹與二叉排序樹的區(qū)別在于：不同的子樹節(jié)點(diǎn)、不同的鍵值和不同的子樹類型。

1、 1. 二叉樹：二叉樹左/右子樹上所有節(jié)點(diǎn)的值可以大于、等于或小于其根節(jié)點(diǎn)的值。

2. 二叉排序樹：如果二叉排序樹的左/右子樹不為空，則左/右子樹上所有節(jié)點(diǎn)的值都小于其根節(jié)點(diǎn)的值。

2、二叉樹：二叉樹可以有具有相等鍵值的節(jié)點(diǎn)。

2. 二叉排序樹：二叉排序樹沒有具有相等鍵值的節(jié)點(diǎn)。

3、 1. 二叉樹：二叉樹的左右子樹也是二叉樹。

2. 二叉排序樹：二叉排序樹的左右子樹也是二叉排序樹