查找 - 樹上的查找 - 二叉排序樹（二）

　　二叉排序樹上的運算

　　() 二叉排序樹的插入和生成

　　①二叉排序樹插入新結點的過程

　　在二叉排序樹中插入新結點要保證插入後仍滿足BST性質其插入過程是

　　(a)若二叉排序樹T為空則為待插入的關鍵字key申請一個新結點並令其為根;

　　(b)若二叉排序樹T不為空則將key和根的關鍵字比較

　　(i)若二者相等則說明樹中已有此關鍵字key無須插入

　　(ii)若key

　　(iii)若key>T→key，則將它插入根的右子樹中。

　　子樹中的插入過程與上述的樹中插入過程相同。Tw.wiNGWit.Com如此進行下去，直到將key作為一個新的葉結點的關鍵字插入到二叉排序樹中，

　　或者直到發現樹中已有此關鍵字為止。

　　②二叉排序樹插入新結點的遞歸算法

　　【參見參考書目】

　　③二叉排序樹插入新結點的非遞歸算法

　　void InsertBST(BSTree *Tptr，KeyType key)

　　{ //若二叉排序樹 *Tptr中沒有關鍵字為key，則插入，否則直接返回

　　BSTNode *f，*p=*TPtr; //p的初值指向根結點

　　while(p){ //查找插入位置

　　if(p->key==key) return;//樹中已有key，無須插入

　　f=p; //f保存當前查找的結點

　　p=(keykey)?p->lchild：p->rchild;

　　//若keykey，則在左子樹中查找，否則在右子樹中查找

　　} //endwhile

　　p=(BSTNode *)malloc(sizeof(BSTNode));

　　p->key=key; p->lchild=p->rchild=NULL; //生成新結點

　　if(*TPtr==NULL) //原樹為空

　　*Tptr=p; //新插入的結點為新的根

　　else //原樹非空時將新結點關p作為關f的左孩子或右孩子插入

　　if(keykey)

　　f->lchild=p;

　　else f->rchild=p;

　　} //InsertBST

　　④二叉排序樹的生成

　　二叉排序樹的生成，是從空的二叉排序樹開始，每輸入一個結點數據，就調用一次插入算法將它插入到當前已生成的二叉排序樹中。生成二叉排序樹的算法如下：

　　BSTree CreateBST(void)

　　{ //輸入一個結點序列，建立一棵二叉排序樹，將根結點指針返回

　　BSTree T=NULL; //初始時T為空樹

　　KeyType key;

　　scanf("%d"，&key); //讀人一個關鍵字

　　while(key){ //假設key=0是輸人結束標志

　　InsertBST(&T，key); //將key插入二叉排序樹T

　　scanf("%d"，&key);//讀人下一關鍵字

　　}

　　return T; //返回建立的二叉排序樹的根指針

　　} //BSTree

　　⑤二叉排序樹的生成過程

　　由輸入實例(5，3，7，2，4，8)，根據生成二叉排序樹算法生成二叉排序樹的過程

　　注意：

　　輸入序列決定了二叉排序樹的形態。

　　二叉排序樹的中序序列是一個有序序列。所以對於一個任意的關鍵字序列構造一棵二叉排序樹，其實質是對此關鍵字序列進行排序，使其變為有序序列。"排序樹"的名稱也由此而來。通常將這種排序稱為樹排序(Tree Sort)，可以證明這種排序的平均執行時間亦為O(nlgn)。

　　對相同的輸入實例，樹排序的執行時間約為堆排序的2至3倍。因此在一般情況下，構造二叉排序樹的目的並非為了排序，而是用它來加速查找，這是因為在一個有序的集合上查找通常比在無序集合上查找更快。因此，人們又常常將二叉排序樹稱為二叉查找樹

From:http://tw.wingwit.com/Article/program/sjjg/201311/23828.html