標籤: 暫無標籤

二叉排序樹(Binary Sort Tree)或者是一棵空樹;或者是具有下列性質的二叉樹:(1)若左子樹不空,則左子樹上所有結點的值均小於它的根結點的值;(2)若右子樹不空,則右子樹上所有結點的值均大於它的根結點的值;(3)左、右子樹也分別為二叉排序樹;

目錄

1 二叉排序樹 -步驟

若根結點的關鍵字值等於查找的關鍵字,成功。
否則,若小於根結點的關鍵字值,遞歸查左子樹。
若大於根結點的關鍵字值,遞歸查右子樹。
若子樹為空,查找不成功。
插入演算法:
    首先執行查找演算法,找出被插結點的父親結點。
    判斷被插結點是其父親結點的左、右兒子。將被插結點作為葉子結點插入。
   若二叉樹為空。則首先單獨生成根結點。
注意:新插入的結點總是葉子結點。
void InsertBST(t,key)
  //在二叉排序樹中插入查找關鍵字key
  {
     if(t==NULL){
         t=new BiTree;
         t->lchild=t->rchild=NULL;
         t->data=key;
         return; }
     if(keydata ) InsertBST(t->lchild,key);
        else InsertBST (t->rchild, key );
  }
void CreateBiTree(tree,d【 】,n)
//n個數據在數組d中,tree為二叉排序樹根
  {  tree=NULL;
      for(i=0;i       InsertBST(tree,d);
}

上一篇[蒲壽宬]  

相關評論

同義詞:暫無同義詞