《二叉查找树.doc》由会员分享，可在线阅读，更多相关《二叉查找树.doc（46页珍藏版）》请在金锄头文库上搜索。
1、江西省省选讲稿 23二叉查找树一、二叉查找树：查找树是一种数据结构，它支持多种动态集合操作，包括search，minimum，maximum，predecessor，successor，insert以及delete。在二叉查找树上执行的基本操作时间与树的高度成正比。对于一棵含有n个结点的完全二叉树，这些操作的时间复杂度为O(log2n)。但是，如果树是含有n个结点的线性链，则这些操作的最坏情况下的运行时间为O(n)。（一）二叉查找树的概念：二叉查找树（BST，Binary Search Tree）又称二叉排序树或二叉搜索树，它或者是一棵空树，或者是一棵具有如下性质的非空二叉树：（1）若它的左子
2、树不空，则左子树上所有节点的值均不大于它的根节点的值；（2）若它的右子树不空，则右子树上所有节点的值均不小于它的根节点的值；（3）它的左、右子树也分别为二叉查找树。等价定义：若以中序遍历二叉查找树，则会产生一个所有节点关键字值的递增序列。 45 / 12 53 / 3 37 100 / / 24 61 90 / 78例如：右下图的树，中序遍历得到的数值为（3，12，24，37，45，53，61，78，90，100）。二叉查找树之所以又称为二叉排序树，因为它是“排过序”的二叉树，但并非是“用于排序”的二叉树。不难发现，二叉查找树这种数据结构的优势在于它的有序性，这是其它类似功能的数据结构无法达到
3、的。比如有序线性表虽然有序，但是插入算法的时间复杂度为O(n)；堆的插入算法虽然时间复杂度为O(log2n)，但是堆并不具有有序性。因此，我们要充分发挥二叉查找树的优势，就要充分利用其有序性和插入、查找算法的高效性。所以，如果要经常对有序数列进行“动态”的插入或查找工作，就可以采用二叉查找树来实现。依据二叉查找树的定义，我们知道：具有相同结点集的二叉查找树，可能的形态很不同。例如对于集合1，2，3所建立的二叉查找树就可能是下图所示的五种形态的任一种。123132132132132（二）二叉查找树的数据结构一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示，其中每一个结点都是一个对
4、象。结点中除了key域和卫星数据域外，还包含域left，right和p，它们分别指向结点的左儿子、右儿子和父结点。如果某个儿子结点或父结点不存在，则相应域中的值即为NIL。根结点是树中唯一父结点域为NIL的结点。一般情况下，一棵二叉查找树的存储结构如下：type node = record key : longint; 关键值 left, right, p : longint; 左儿子、右儿子、父结点 根据需要增加一些数据域 end;var bst : array1.maxn of node;（三）二叉查找树的遍历根据二叉查找树的性质，若要求按递增顺序输出树的所有关键字，只需要采用中序遍历算法
5、递归即可：procedure inorder_print(root : integer); 递归中序输出，从小到大 begin if bstroot.left0 then inorder_print(bstroot.left); write(bstroot.key, ); if bstroot.right0 then inorder_print(bstroot.right); end;也可以用广义表的形式输出：procedure out(root : integer); begin write(); if bstroot.left0 then out(bstroot.left); write(
6、bstroot.key); if bstroot.right0 then out(bstroot.right); write(); end;二叉查找树看似简单，且没有太多的规则，其实它在题目中变化无常，所以要真正要用好它，是需要下一番功夫的。首先要熟练掌握好它的各种基本操作，下面一一给出。二、查询二叉查找树对于二叉查找树，最常见的操作是查找树中的某个关键字。除了search操作外，二叉查找树还能支持诸如minimum、maximum、predecessor和successor等查询。本节就来讨论这些操作，并说明对于高度为h的树，它们都可以在O(h)时间内完成。（一）查找关键字值为k的节点从树的
7、根节点出发，查找关键字k的位置。由于二叉查找树本身的特点，所以这个查找过程总是沿着树的某条路径，逐层向下进行判断比较，或者找到匹配对象，返回k值的位置；或者找不到匹配对象，返回0。递归算法如下：function search(root, k : integer) : integer; begin if (root=0) or (k=bstroot.key) then exit(root); if kbstroot.key then search:=search(bstroot.left, k) else search:=search(bstroot.right, k); end;从算法中可以看
8、出，这个算法递归时一旦返回，就再也不会出现递归调用，这种递归叫做末尾递归。末尾递归可以写成非递归的形式，这样可以节省栈所用的空间与运行时间。相比较递归算法而言，非递归算法更加高效：function search(root, k : integer) : integer; begin while (root0) and (kbstroot.key) do if kbstroot.key then root:=bstroot.left else root:=bstroot.right; search:=root; end;（二）求最小（大）关键字值的结点要查找二叉树中具有最小关键字的结点，只要从根
9、结点出发，沿着各结点的left指针查找下去，直到遇到NIL时为止。下面给出从树的某个结点出发，查找其子树中最小关键字值的结点位置的函数。function min(x : integer) : integer; begin while bstx.left0 do x:=bstx.left; min:=x; end;二叉树的性质保证了上述函数的正确性。如果一个结点x无左子树，其右子树中的每个关键字都至少和keyx一样大，则以x为根的子树中，最小关键字就是keyx。如果结点x有左子树，因其左子树中的关键字都不大于keyx，而右子树中的关键字都不小于keyx，因此，在以x为根的子树中，最小关键字可以在
10、以leftx为根的左子树中找到。同样地，要查找二叉树中具有最大关键字的结点，只要从根结点出发，沿着各结点的right指针查找下去，直到遇到NIL时为止。这个过程与查找最小关键字的结点是对称的。下面给出从树的某个结点出发，查找其子树中最大关键字值的结点位置的函数：function max(x : integer) : integer; begin while bstx.right0 do x:=bstx.right; max:=x; end;（三）求一棵二叉查找树中结点x的后继（前趋）结点。给定一个二叉查找树中的结点，有时候要求找出在中序遍历顺序下它的后继（前驱）。如果所有的关键字都不相同，则某
11、一个结点x的后继结点即具有大于keyx中的关键字中最小者的那个结点。根据二叉查找树的结构，不用对关键字做任何比较，就可以找到某个结点的后继。查找结点x的后继时需要考虑两种情况：（1）如果结点x的右子树非空，则x的后继即右子树中的最左（小）结点，如下图中关键字是6的结点的后继结点是关键字为7的结点，关键字是15的结点的后继结点是关键字为17的结点。（2）如果结点x的右子树为空，且x有一个后继y，则y是x的最低祖先结点，且y的左儿子也是x的祖先。如下图中，关键字为13的结点的后继是关键字为15的结点。为找到y，可以从x开始往上查找，直到遇到某个结点是其父结点的左儿子结点时为止（或者某个节点的值恰好
12、比x大为止，求前趋亦同）。下面给出查找结点x的后继结点y的函数：function succ(x : integer) : integer; var y : integer; begin if bstx.right0 then y:=min(bstx.right) else begin y:=bstx.p; while (bsty.p0) and (x=bsty.right) do begin x:=y; y:=bsty.p; end; end; succ:=y; end;相应地，查找结点x的前驱与后继是对称的，也需要考虑两种情况：（1）如果结点x的左子树非空，则x的前趋即左子树中的最右（大）结
13、点，如上图中关键字是15的结点的前驱结点是关键字为13的结点。（2）如果结点x的左子树为空，且x有一个前趋y，则y是x的最低祖先结点，且y的右儿子也是x的祖先。如上图中，关键字为9的结点的前驱是关键字为7的结点。也就是要从x开始，往上找某个结点y，它的右儿子是x的祖先。其实，在没有左子树的情况下，如果x是右儿子，则前趋就是x的父结点。下面给出查找结点x的前驱结点y的函数：function pred(x : integer) : integer; var y : integer; begin if bstx.left0 then y:=max(bstx.left) else begin y:=bstx.p; while (bsty.p0) and (x=bsty.left) do begin x:=y; y:=bsty.p; end; end; pred:=y; end;三、二叉查找树的插入与删除插入和删除操作会引起以二叉查找树表示的动态集合的变化。要反应出这种变化，就要修改数据结构，但在修改的同时，还要保持二叉查找树性质。（一）二叉查找树的插入把结点z插入到二叉查找树T中，使T仍然满足二叉查找树的性质
