《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件7-05二叉排序樹的插入與生成

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：賀寧 二叉排序樹的插入與生成常州信息職業(yè)技術(shù)學(xué)院0203二叉排序樹的插入（1）插入方法在二叉排序樹中插入新結(jié)點(diǎn)，設(shè)其關(guān)鍵字域的值為key，要保證插入后仍滿足BST性質(zhì)。插入過程是：若二叉排序樹T為空，則為待插入結(jié)點(diǎn)申請(qǐng)存儲(chǔ)空間，并令其為根；若二叉排序樹T不空，則將待插入結(jié)點(diǎn)關(guān)鍵字key與根的關(guān)鍵字比較：(i)若key=T-key，則樹中已有此關(guān)鍵字key，無須插入；(ii)若keykey，則將key插入根的左子樹中；(iii)若keyT-key，則將key插入根的右子樹中。子樹中的插入過程與上述的樹中插入過程相同。如此進(jìn)行下去，直到將key作為

2、一個(gè)新的葉結(jié)點(diǎn)關(guān)鍵字插入到二叉排序樹中，或者直到發(fā)現(xiàn)樹中已有此關(guān)鍵字為止。 04二叉排序樹的插入（2）遞歸算法int InsertBSTR(BSTree *Tptr,KeyType key)/二叉排序樹插入新結(jié)點(diǎn)遞歸算法，插入成功返回1，失敗返回0if(!(*Tptr)(*Tptr)=(BSTNode *)malloc(sizeof(BSTNode);if(*Tptr =NULL) puts (內(nèi)存申請(qǐng)不成功!);return 0; (*Tptr)-key=key;(*Tptr)-lchild=NULL;(*Tptr)-rchild=NULL;elseif(*Tptr)-key=key)ret

3、urn 0;if(keykey)InsertBSTR(&(*Tptr)-lchild,key);elseInsertBSTR(&(*Tptr)-rchild,key); return 1;05二叉排序樹的生成 二叉排序樹的生成，是從空的二叉排序樹開始，每輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)，就調(diào)用一次插入算法將它插入到當(dāng)前已生成的二叉排序樹中。BSTree CreateBST(void) /輸入一個(gè)結(jié)點(diǎn)序列，建立一棵二叉排序樹，將根結(jié)點(diǎn)指針返回BSTree T=NULL;/初始時(shí)T為空樹KeyType key;scanf(%d,&key);/讀入一個(gè)關(guān)鍵字while(key)/假設(shè)key=0是輸入結(jié)束標(biāo)志InsertBSTR(&T,key);/將key插入二叉排序樹Tscanf(%d,&key);/讀入下一關(guān)鍵字return T;/返回建立的二叉排序樹的根指針 注意二叉排序樹的形態(tài)與輸入序列的順序有關(guān)，第一個(gè)輸入的結(jié)點(diǎn)一定是根結(jié)點(diǎn)。二叉排序樹的中序序列是一個(gè)有序序列。所以對(duì)于一個(gè)任意的關(guān)鍵字序列構(gòu)造一棵二叉排序樹，其實(shí)質(zhì)是對(duì)此關(guān)鍵字序列進(jìn)行排序，這種排序的平均執(zhí)行時(shí)間亦為O(nlgn)，“排序樹”的名稱也由此而來。06二叉排序樹的生成 按輸入序列（25,32,9,18,27,6,29）的順序構(gòu)造二叉排序樹T，具體過程如下圖所示。圖示 二叉排序樹生成過程6T初始為空T25插入25T