S9.3.1二叉查找树(BST) S9.3.1二叉查找树(BST) 5, ·举例 ⑤ 1.查找 ② ⑦ :都本思想 处督德商开的喜生肉牌棉控把冲技我 功，返回该点的指 查结点，则失数宇某个空指针上。 ■存储结构： ■算法 typedef struct node BSTNode*SearchBST(BSTree T,KeyType key K 在T上查找k@y=K的节点，成功时逗回该节点，否刚远回NULL KeyType key; if (T==NULLI key=T-key)return TT为空，意找失香刚功 InfoType otherinfo if(kay<T->kay】 return SearchBST(T->ichild,key方童找左子侧 struct node"lchild,"rchild; else }BSTNode,'BSTree; return SearchBST(T->rchild,.kay片责找右子铜 S93.1二叉查找树(BST) ⑤ 2、BST的插入和生成 ③ T 1.查找 ■插入 ② ④ ⑨ ■时间 ◆算法思想保正新结点插入后满足BST性质，基本思想如 下， 若成功，则走了一条从根到待查节点的路径 若T为空，则为特播入的Ky申请一个新结点，并令其为 若失败，则走了一条从根到叶子的路径？（不一定） 报： ◆上界：O(h) ,否则，从根开始向下查找插入位置，直到发现树中已有 K©y,或找到=个空指针为止： ◆分析：与树高相关 ①最坏情况：单支树，S=(+1)/2,与顺序查找相同 ,将新结点作为叶子插入空指针的位量。 查找过程是一个关输字的比较过程，易于写出递归或非递 ②最好情况：ASL≈gm,形态与折半查找的判定制相似 归算法，也可以调用查找操作。 ®平均情况：假定n个koys所形成的nl种排列是等摄率的， 则可正明由这n!个序列产生的n!棵sT(其中有的形态相 同)的平均高度为O(1gn),故查找时间仍为O(1gn ◆算法实现 2、BST的插入和生成 2、BST的插入和生成 void InsertBST(BSTree*T,KeyType key){rT是根 ■生成 BSTNode*f,“p=T;p指向粮结点 while(p)(∥当时排空时，查找报入位夏 ◆算法：从空树开始，每输入一个数据蚊调用一次插入算法， 许(p->kay=kay)retur;树中已有key,不允许置复须入 BSTree CreateBST(void ) f=p!∥和p为父子关暴 BSTree T=NULL;物始时r为空 p=(key <p>key )p->lchild;p>rchild; KeyType key; }加注意：制为空时，无须童找 scanf("%d",&key ) p=(BSTNode*)malloc(sizeof(BSTNode)); whie(key)(餐设key=0豪示输入结家 p->kay=key;p->lchild=p>rchild=NULL;性减新罐点 InsertBST(&T,key):将key擂入树T中 计(T=NUL儿L)·T=p;原树为空新储点为根 scanf(“%d”,&key ):I婆入下一个关输字 es白川原制排空，新神点作为的左或右孩子霜入 } if key <f->key f->lchild=p; return T:∥返回餐物针 else f->rchild=p; )时同为0() 33 13 § 9.3.1 二叉查找树（BST） „ 举例 „ 存储结构： typedef struct node { KeyType key; InfoType otherinfo; struct node *lchild, *rchild; } BSTNode, *BSTree; 5 3 7 2 4 9 14 § 9.3.1 二叉查找树（BST） 1.查找 „ 基本思想 从根结点开始比较，若当前结点的key与待查的key相等，则查找成 功，返回该结点的指针；否则在左子树或右子树中继续查找。若树中没有待 查结点，则失败于某个空指针上。 „ 算法 BSTNode *SearchBST( BSTree T, KeyType key ){ //在T上查找key=K的节点，成功时返回该节点，否则返回NULL if ( T==NULL || key==T->key ) return T; //若T为空，查找失败；否则成功 if ( key < T->key ) return SearchBST ( T->lchild, key ); //查找左子树 else return SearchBST ( T->rchild, key ); //查找右子树 } 5 3 7 2 4 9 15 § 9.3.1 二叉查找树（BST） 1.查找 „ 时间 若成功，则走了一条从根到待查节点的路径 若失败，则走了一条从根到叶子的路径？（不一定） ™上界：O(h) ™分析：与树高相关 ①最坏情况：单支树，ASL=(n+1)/2,与顺序查找相同 ②最好情况：ASL≈lgn，形态与折半查找的判定树相似 ③平均情况：假定n个keys所形成的n!种排列是等概率的， 则可证明由这n!个序列产生的n!棵BST（其中有的形态相 同）的平均高度为O(lgn)，故查找时间仍为O(lgn) 5 3 7 2 4 9 16 2、BST的插入和生成 „ 插入 ™算法思想 保证新结点插入后满足BST性质，基本思想如 下： ¾若T为空，则为待插入的Key申请一个新结点，并令其为 根； ¾否则，从根开始向下查找插入位置，直到发现树中已有 Key，或找到一个空指针为止； ¾将新结点作为叶子插入空指针的位置。 查找过程是一个关键字的比较过程，易于写出递归或非递 归算法，也可以调用查找操作。 ™ 算法实现 17 2、BST的插入和生成 void InsertBST( BSTree *T, KeyType key ) { //*T是根 BSTNode *f, *p=*T; //p指向根结点 while( p ) { //当树非空时，查找插入位置 if ( p->key==key ) return; //树中已有key，不允许重复插入 f＝p；// f和p为父子关系 p＝( key < p->key ) ? p->lchild; p->rchild; } //注意：树为空时，无须查找 p = (BSTNode *) malloc(sizeof(BSTNode)); p->key=key; p->lchild=p->rchild=NULL; //生成新结点 if ( *T ==NULL ) * T=p; //原树为空,新结点为根 else //原树非空, 新结点作为*f的左或右孩子插入 if ( key < f->key ) f->lchild=p; else f->rchild=p; } //时间为O（h） 18 2、BST的插入和生成 „ 生成 ™ 算法： 从空树开始，每输入一个数据就调用一次插入算法。 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；// 返回根指针 }