二叉排序樹的定義,平衡二叉樹和某接點的平衡因子的定義？　　二叉排序樹也稱二叉查找樹。它或者是一棵空樹；或者有性質(zhì)：（1）若其左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值。（2）若其右子樹不空，則

二叉排序樹的定義,平衡二叉樹和某接點的平衡因子的定義？

　　二叉排序樹也稱二叉查找樹。它或者是一棵空樹；或者有性質(zhì)：（1）若其左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值。（2）若其右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值。（3）左右子樹也為二叉排序樹。

　　平衡二叉樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉排序樹：(1)左、右子樹都是平衡二叉樹；(2)左、右子樹高度差的絕對值

　　若把左子樹與右子樹高度之差稱為結(jié)點x的平衡因子(balance factor)，用bf(x)表示。

　　則由平衡二叉樹定義知:Bf(x)=x左子樹深度-x右子樹深度

二叉查找樹和二叉排序樹有什么區(qū)別？

二叉樹和二叉排序樹區(qū)別為：子樹結(jié)點不同、鍵值相等不同、子樹樹型不同。

一、子樹結(jié)點不同

1、二叉樹：二叉樹的左/右子樹上所有結(jié)點的值可以大于、等于和小于它的根結(jié)點的值。

2、二叉排序樹：二叉排序樹若左/右子樹不空，則左/右子樹上所有結(jié)點的值均小于它的根結(jié)點的值。

二、鍵值相等不同

1、二叉樹：二叉樹可以有鍵值相等的結(jié)點。

2、二叉排序樹：二叉排序樹沒有鍵值相等的結(jié)點。

三、子樹樹型不同

1、二叉樹：二叉樹的左、右子樹也分別為二叉樹。

2、二叉排序樹：二叉排序樹的左、右子樹也分別為二叉排序樹