二叉搜索樹(shù)的特點(diǎn)有哪些

本篇文章為大家展示了二叉搜索樹(shù)的特點(diǎn)有哪些，代碼簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過(guò)這篇文章的詳細(xì)介紹希望你能有所收獲。

二叉搜索樹(shù)的特點(diǎn)是對(duì)于樹(shù)中的每個(gè)節(jié)點(diǎn)X，它的左子樹(shù)中所有關(guān)鍵字值小于X的關(guān)鍵字值，而它的右子樹(shù)中所有關(guān)鍵字值大于X的關(guān)鍵字值；根據(jù)這個(gè)性質(zhì)，對(duì)一個(gè)二叉樹(shù)進(jìn)行中序遍歷，如果是單調(diào)遞增的，則可以說(shuō)明這個(gè)樹(shù)是二叉搜索樹(shù)。

二叉搜索樹(shù)的特點(diǎn)

二叉搜索樹(shù)的特點(diǎn)：對(duì)于樹(shù)中的每個(gè)節(jié)點(diǎn)X，它的左子樹(shù)中所有關(guān)鍵字值小于X的關(guān)鍵字值，而它的右子樹(shù)中所有關(guān)鍵字值大于X的關(guān)鍵字值。

根據(jù)這個(gè)性質(zhì)，對(duì)一個(gè)二叉樹(shù)進(jìn)行中序遍歷，如果是單調(diào)遞增的，則可以說(shuō)明這個(gè)樹(shù)是二叉搜索樹(shù)。

二叉搜索樹(shù)的查找

過(guò)程：首先和根節(jié)點(diǎn)進(jìn)行比較，如果等于根節(jié)點(diǎn)，則返回。如果小于根節(jié)點(diǎn)，則在根節(jié)點(diǎn)的左子樹(shù)進(jìn)行查找。如果大于根節(jié)點(diǎn)，則在根節(jié)點(diǎn)的右子樹(shù)進(jìn)行查找。

/* 查找以t為根節(jié)點(diǎn)的樹(shù)中，是否包含x */
Position Find(ElementType x, SearchTree t)
{
    if (t == NULL) {
        return NULL;
    } else if (x < t->element) {
        return Find(x, t->left);
    } else if (x > t->element) {
        return Find(x, t->right);
    } else {
        return t;
    }
}

上述內(nèi)容就是二叉搜索樹(shù)的特點(diǎn)有哪些，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注億速云行業(yè)資訊頻道。