第三十一課
本課主題： 動態查詢表
教學目的： 掌握二叉排序樹的實現方法
教學重點： 二叉排序樹的實現
教學難點： 構造二叉排序樹的方法
授課內容：
一、動態查詢表的定義
動態查詢表的特點是：
表結構本身是在查詢過程中動態生成的，即對於給定值key,若表中存在其關鍵字等於key的記錄，則查詢成功返回，否則插入關鍵字等於key的記錄。以政是動態查詢表的定義：
adt dymanicsearchtableadt dynamicsearchtable
二、二叉排序樹及其查詢過程
二叉排序樹或者是一棵空樹；或者是具有下列性質的二叉樹：
１、若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
２、若它的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
３、它的左、右子樹了分別為二叉排序樹。
如果取二叉鍊錶作為二叉排序樹的儲存結構，則上述查詢過程如下：
bitree searchbst(bitree t,keytype key)//searchbst
三、二叉排序樹的插入和刪除
二叉排序樹是一種動態樹表，其特點是，樹的結構通常不是一資生成的，面是在查詢過程中，當樹中不存在關鍵字等於給定值的結點時再進行插入。新插入的結點一定是乙個新新增的葉子結點，並且是查詢不成功時查詢路徑上訪問的最後乙個結點的左孩子或右孩子結點。
status searchbst(bitree t,keytype key,bitree f,bitree &p)
else if eq(key,t-> p=t;return true;}
else if lt(key,t-> searchbst(t->lchild,key,t,p);
else searchbst(t->rchild,key,t,p);
}//searchbst
插入演算法：
status insertbst(bitree &t,elemtype e)
else return false;
}//insertbst
在二叉排序樹中刪除乙個節點的演算法：
status deletebst(bitree &t,keytype key)
}void delete(bitree &p)
else if(!p->lchild)
else//轉左，然後向右到盡頭
p->data=s->data; //s指向被刪結點的"前驅"
if(q!=p)q->rchild=s->lchild; //重接*q的右子樹
else q->lchild=s->lchild;//重接*q的左子樹 （方法一結束）
//或可用方法二：
//q=s=(*p)->l;
//while(s->r) s=s->r;
//s->r=(*p)->r;
//free(*p);
//(*p)=q; }}
請看乙個示例源程式。
#include <>
#define error 0;
#define false 0;
#define true 1;
#define ok 1;
typedef int elemtype;
typedef int status;
typedef int keytype;
#define eq(a,b) ((a)==(b))
#define lt(a,b) ((a)< (b))
#define lq(a,b) ((a)<=(b))
typedef struct binarytree
*bitree,binode;
binode * new()
createsubtree(bitree *t,elemtype *all,int i)
*t=new();
if(*t==null) return error;
(*t)->data=all[i];
createsubtree(&((*t)->l),all,2*i);
createsubtree(&((*t)->r),all,2*i+1);
}createbitree(bitree *t)
; createsubtree(t,all,1);
}printelem(elemtype d)
preordertr**erse(bitree t,int (*visit)(elemtype d))
else return ok;
}inordertr**erse(bitree t,int (*visit)(elemtype d))
else return ok;
}status searchbst(bitree t,keytype key,bitree f,bitree *p)
else if eq(key,t->data)
else if lt(key,t->data) searchbst(t->l,key,t,p);
else searchbst(t->r,key,t,p);
}status insertbst(bitree *t,elemtype e)
else return false;
}void delete(bitree *p)
else if(!(*p)->l)
else
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;
}}status deletebst(bitree *t,keytype key)
else{
if ( eq(key,(*t)->data)) delete(t);
SQL基本表查詢
資料庫實驗報告 實驗三實驗題目 sql 基本表查詢 指導老師 實驗型別 驗證 實驗室 軟體實驗室二 專業班級 電腦科學與技術 網路工程方向 班 姓名2013年 10月20 日 一 實驗題目 二 實驗目的和要求 熟練掌握查詢語句的一般格式，熟練掌握連線 巢狀和集合查詢的使用。三 實驗內容 1 查詢st...
約會動機查詢表
揭秘 1 這是乙個有誠意的開始，表明他是早有計畫和你約會的。至少，也說明他有相當的社交禮貌。2 這個男人可能只是一時寂寞了，如果你也碰巧寂寞，同時也不介意乾柴碰烈火的結果，那就去赴約吧。3 遇到這種情況的看著個男人的性格 如果這個男人是老實木訥型的，那就說明他還沒有單獨約會的把握，因此彼此都打個安全...
員工動態表改
陝西竹園村餐飲有限責任公司 分公司200 年月員工動態統計表 統計區間 月26日 月25日 分公司經理簽字日期 關於填報員工動態統計表的說明 為充分掌握員工動態，規範公司的基礎人力資源管理，從2007年元月起，建立員工動態統計報表報告機制。首先由各分公司 配送中心每月定期填報本分公司的員工動態統計表...