資源簡介
二叉排序樹。用二叉鏈表作存儲結(jié)構(gòu)。
要求：
(1)以回車('\n')為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排序樹T；
(2)對二叉排序樹T作中序遍歷，輸出結(jié)果；
(3)計算二叉排序樹T查找成功的平均查找長度,輸出結(jié)果；
(4)輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序
歷(執(zhí)行操作2)；否則輸出信息“無x”。
代碼片段和文件信息
#include
#include
#include
#include
typedef?struct?Tnode
?{
???int???data;?/*輸入的數(shù)據(jù)*/
???struct?Tnode?*lchild*rchild;?/*結(jié)點(diǎn)的左右指針，分別指向結(jié)點(diǎn)的左右孩子*/
?}*nodeBSTnode;
?int?searchBST（node?tint?keynode?fnode?*p）?/*查找函數(shù)*/
{
????if（!t）??{*p=f;return?（0）;}?/*查找不成功*/
????else????if（key==t->data）
????{
?????*p=t;return?（1）;
????}?/*查找成功*/
????else????if（key<=t->data）
????searchBST（t->lchildkeytp）;?/*在左子樹中繼續(xù)查找*/
????else
????searchBST（t->rchildkeytp）;/*在右子樹中繼續(xù)查找*/
}
int?insertBST（node?*tint?key）??/*插入函數(shù)*（t為根節(jié)點(diǎn)）*/
{
????node?p=NULLs=NULL;//p為當(dāng)前結(jié)點(diǎn)，s為要插入的結(jié)點(diǎn)
????if（!searchBST（*tkeyNULL&p））?/*查找不成功*/
????{
???????s=（node）malloc（sizeof（BSTnode））;//malloc?向系統(tǒng)申請分配指定的內(nèi)存空間
???????s->data=key;
???????s->lchild=s->rchild=NULL;
???????評論
共有 條評論