二叉查找树讲稿

《二叉查找树讲稿》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、江西省省选讲稿23p二叉查找树一、二叉查找树：查找树是一种数据结构，它支持多种动态集合操作，包括search，minimum，maximum，predecessor，successor，insert以及delete。在二叉查找树上执行的基本操作时间与树的高度成正比。对于一棵含有n个结点的完全二叉树，这些操作的时间复杂度为O(log2n)。但是，如果树是含有n个结点的线性链，则这些操作的最坏情况下的运行时间为O(n)。（一）二叉查找树的概念：二叉查找树（BST，BinarySearchTree）又称二叉排序树或二叉搜索树，它或者是一棵空树，或者是一棵具有如下性质的非空二叉树：（1）若它

2、的左子树不空，则左子树上所有节点的值均不大于它的根节点的值；（2）若它的右子树不空，则右子树上所有节点的值均不小于它的根节点的值；（3）它的左、右子树也分别为二叉查找树。等价定义：若以中序遍历二叉查找树，则会产生一个所有节点关键字值的递增序列。45/1253/\337100//246190/78例如：右下图的树，中序遍历得到的数值为（3，12，24，37，45，53，61，78，90，100）。二叉查找树之所以又称为二叉排序树，因为它是“排过序”的二叉树，但并非是“用于排序”的二叉树。不难发现，二叉查找树这种数据结构的优势在于它的有序性，这是其它类似功能的数据结构无法达到的。比

3、如有序线性表虽然有序，但是插入算法的时间复杂度为O(n)；堆的插入算法虽然时间复杂度为O(log2n)，但是堆并不具有有序性。因此，我们要充分发挥二叉查找树的优势，就要充分利用其有序性和插入、查找算法的高效性。所以，如果要经常对有序数列进行“动态”的插入或查找工作，就可以采用二叉查找树来实现。依据二叉查找树的定义，我们知道：具有相同结点集的二叉查找树，可能的形态很不同。例如对于集合{1，2，3}所建立的二叉查找树就可能是下图所示的五种形态的任一种。123132132132132（二）二叉查找树的数据结构江西省省选讲稿23一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示

4、，其中每一个结点都是一个对象。结点中除了key域和卫星数据域外，还包含域left，right和p，它们分别指向结点的左儿子、右儿子和父结点。如果某个儿子结点或父结点不存在，则相应域中的值即为NIL。根结点是树中唯一父结点域为NIL的结点。一般情况下，一棵二叉查找树的存储结构如下：typenode=recordkey:longint;{关键值}left,right,p:longint;{左儿子、右儿子、父结点}……{根据需要增加一些数据域}end;varbst:array[1..maxn]ofnode;（三）二叉查找树的遍历根据二叉查找树的性质，若要求按递增顺序输出树的所有关键字，只需

5、要采用中序遍历算法递归即可：procedureinorder_print(root:integer);{递归中序输出，从小到大}beginifbst[root].left<>0theninorder_print(bst[root].left);write(bst[root].key,'');ifbst[root].right<>0theninorder_print(bst[root].right);end;也可以用广义表的形式输出：procedureout(root:integer);beginwrite('(');ifbst[root].left<>0thenout(bst[roo

6、t].left);write(bst[root].key);ifbst[root].right<>0thenout(bst[root].right);write(')');end;二叉查找树看似简单，且没有太多的规则，其实它在题目中变化无常，所以要真正要用好它，是需要下一番功夫的。首先要熟练掌握好它的各种基本操作，下面一一给出。二、查询二叉查找树对于二叉查找树，最常见的操作是查找树中的某个关键字。除了search操作外，二叉查找树还能支持诸如minimum、maximum、predecessor和successor等查询。本节就来讨论这些操作，并说明对于高度为h的树，它们都可以在O(

7、h)时间内完成。江西省省选讲稿23（一）查找关键字值为k的节点从树的根节点出发，查找关键字k的位置。由于二叉查找树本身的特点，所以这个查找过程总是沿着树的某条路径，逐层向下进行判断比较，或者找到匹配对象，返回k值的位置；或者找不到匹配对象，返回0。递归算法如下：functionsearch(root,k:integer):integer;beginif(root=0)or(k=bst[root].key)thenexit(root);ifk