熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

查找 - 樹上的查找 - 二叉排序樹(二)

2013-11-15 15:42:16  來源: 數據結構 

  二叉排序樹上的運算

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

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

  在二叉排序樹中插入新結點要保證插入後仍滿足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
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.