资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授：,贺宁,二叉排序树的查找,常州信息职业技术学院,02,03,二叉排序树的查找,在二叉排序树上进行查找，先将,key,与根结点关键字,T-key,进行比较，若相等便找到，若,keykey,就在左子树中查找，若,keyT-key,就在右子树中查找。,递归算法,BSTNode *SearchBST(BSTree T,KeyType key),/,在二叉排序树,T,上查找关键字为,key,的结点，成功时返回该结点位置，否则返回,NULL,if,(T=NULL|key=T-key),/,递归的终结条件,return,T;,/,查找失败或成功，返回,NULL,或找到的结点位置,if,(keykey),return,SearchBST(T-lchild,key);,/,继续在左子树中查找,else,return,SearchBST(T-rchild,key);,/,继续在右子树中查找,04,二叉排序树的查找,说明,：在二叉排序树上进行查找时，若查找成功，则是从根结点出发走了一条从根到待查结点的路径。若查找不成功，则是从根结点出发走了一条从根到某个叶子的路径。,05,二叉排序树的查找,4,、算法分析,平均查找长度,在等概率假设下，二叉排序树查找成功的平均查找长度为,O(lgn),。,与二分查找类似，与关键字比较的次数不超过树的深度。,在二叉排序树上进行查找时的平均查找长度与二叉树的形态有关。,THANKS,
展开阅读全文