二叉排序樹的定義

二叉排序樹(Binary Sort Tree)或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

• 若它的左子樹非空，則在左子樹的所有結(jié)點(diǎn)的值都小于它的根結(jié)點(diǎn)的值
• 若它的右子樹非空，則在右子樹的所有結(jié)點(diǎn)的值都大于(若允許結(jié)點(diǎn)有相同的值，則大于等于)它的根結(jié)點(diǎn)的值
• 左、右子樹也分別是一棵二叉排序樹

簡(jiǎn)言之，二叉排序樹的每個(gè)結(jié)點(diǎn)的值都大于它的左子樹上的所有結(jié)點(diǎn)的值，而小于它的右子樹上所有結(jié)點(diǎn)的值。圖8-5所示就是一棵二叉排序樹。

二叉排序樹示例

二叉排序樹的性質(zhì)

中序遍歷二叉排序樹，可以得到一個(gè)由小到大的有序序列。

例如，中序遍歷如圖8-5所示的二叉排序樹，其結(jié)果序列為(26，40，50，55，58，65，68)，是一個(gè)由小到大的有序序列。

二叉排序樹的查找

若將查找表按二叉排序樹的結(jié)構(gòu)來組織，即樹中每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)記錄，所有記錄的關(guān)鍵字值滿足二叉排序樹的要求。對(duì)給定的查找值，就能針對(duì)二叉排序樹進(jìn)行查找。具體做法如下：當(dāng)二叉排序樹為空時(shí)，查找失敗；當(dāng)二叉排序樹非空時(shí)，先將給定值與根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，若相等則表示查找成功；否則，判斷給定值與根結(jié)點(diǎn)關(guān)鍵字之間的大小關(guān)系，小于根結(jié)點(diǎn)則在其左子樹中繼續(xù)查找，大于根結(jié)點(diǎn)則在其右子樹中繼續(xù)查找。很顯然，每次只需要在根結(jié)點(diǎn)的左或右子樹中的某一個(gè)分支進(jìn)行查找，因此，查找效率大大提高。

二叉排序樹中結(jié)點(diǎn)的結(jié)構(gòu)類型定義如下：

typedef struct Bnode{ int key; struct Bnode *left; struct Bnode *right;} Bnode;

二叉排序樹的查找算法

Bnode *BSearch(Bnode *bt, int k)/*在二叉樹bt中查找關(guān)鍵字值為key的記錄*/{Bnode *p;if(bt==NULL)return (bt);p=bt;while(p->key!=k) /*若沒有查找到，繼續(xù)查找過程*/{if(kkey) /*準(zhǔn)備從左子樹繼續(xù)查找*/p=p->left;else p=p->right; /*準(zhǔn)備從右子樹繼續(xù)查找*/if(p==NULL) break; /*查完能查找的最后一個(gè)關(guān)鍵字，仍未查到,結(jié)束查找*/}Return(p);} 新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的c语言判断二叉树是不是二叉排序树_C语言：数据结构-树表的查找的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。