二叉查找树
二叉查找树
一、二叉查找树：
查找树是一种数据结构，它支持多种动态集合操作，包括search，minimum，maximum，predecessor，successor，insert以及delete。
在二叉查找树上执行的基本操作时间与树的高度成正比。对于一棵含有n个结点的完全二叉树，这些操作的时间复杂度为O(log2n)。但是，如果树是含有n个结点的线性链，则这些操作的最坏情况下的运行时间为O(n)。
（一）二叉查找树的概念：
二叉查找树（BST，Binary Search Tree）又称二叉排序树或二叉搜索树，它或者是一棵空树，或者是一棵具有如下性质的非空二叉树：
（1）若它的左子树不空，则左子树上所有节点的值均不大于它的根节点的值；
（2）若它的右子树不空，则右子树上所有节点的值均不小于它的根节点的值；
（3）它的左、右子树也分别为二叉查找树。
等价定义：若以中序遍历二叉查找树，则会产生一个所有节点关键字值的递增序列。
例如：右下图的树，中序遍历得到的数值为（3，12，24，37，45，53，61，78，90，100）。
二叉查找树之所以又称为二叉排序树，因为它是“排过序”的
二叉树，但并非是“用于排序”的二叉树。
不难发现，二叉查找树这种数据结构的优势在于它的有序性，
这是其它类似功能的数据结构无法达到的。比如有序线性表虽然有
序，但是插入算法的时间复杂度为O(n)；堆的插入算法虽然时间复
杂度为O(log2n)，但是堆并不具有有序性。因此，我们要充分发挥
二叉查找树的优势，就要充分利用其有序性和插入、查找算法的高
效性。所以，如果要经常对有序数列进行“动态”的插入或查找工
作，就可以采用二叉查找树来实现。
依据二叉查找树的定义，我们知道：具有相同结点集的二叉查找树，可能的形态很不同。例如对于集合{1，2，3}所建立的二叉查找树就可能是下图所示的五种形态的任一种。
（二）二叉查找树的数据结构
一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示，其中每一个结点都是一个对象。结点中除了key域和卫星数据域外，还包含域left，right和p，它们分别指向结点的左儿子、右儿子和父结点。如果某个儿子结点或父结点不存在，则相应域中的值即为NIL。根结点是树中唯一父结点域为NIL的结点。
一般情况下，一棵二叉查找树的存储结构如下：
type node = record
key : longint; {关键值}
left, right, p : longint; {左儿子、右儿子、父结点}
…… {根据需要增加一些数据域} end;
var bst : array[1..maxn] of node;
（三）二叉查找树的遍历
根据二叉查找树的性质，若要求按递增顺序输出树的所有关键字，只需要采用中序遍历算法递归即可：
procedure inorder_print(root : integer); {递归中序输出，从小到大}
begin
if bst[root].left<>0 then inorder_print(bst[root].left);
write(bst[root].key, ' ');
if bst[root].right<>0 then inorder_print(bst[root].right);
end;
也可以用广义表的形式输出：
procedure out(root : integer);
begin
write('(');
if bst[root].left<>0 then out(bst[root].left);
write(bst[root].key);
if bst[root].right<>0 then out(bst[root].right);
write(')');
end;
二叉查找树看似简单，且没有太多的规则，其实它在题目中变化无常，所以要真正要用好它，是需要下一番功夫的。首先要熟练掌握好它的各种基本操作，下面一一给出。
二、查询二叉查找树
对于二叉查找树，最常见的操作是查找树中的某个关键字。除了search操作外，二叉查找树还能支持诸如minimum、maximum、predecessor和successor等查询。本节就来讨论这些操作，并说明对于高度为h的树，它们都可以在O(h)时间内完成。
（一）查找关键字值为k的节点
从树的根节点出发，查找关键字k的位置。由于二叉查找树本身的特点，所以这个查找过程总是沿着树的某条路径，逐层向下进行判断比较，或者找到匹配对象，返回k值的位置；或者找不到匹配对象，返回0。递归算法如下：
function search(root, k : integer) : integer;
begin
if (root=0) or (k=bst[root].key) then exit(root);
if k then search:=search(bst[root].left, k) else search:=search(bst[root].right, k); end; 从算法中可以看出，这个算法递归时一旦返回，就再也不会出现递归调用，这种递归叫做末尾递归。末尾递归可以写成非递归的形式，这样可以节省栈所用的空间与运行时间。相比较递归算法而言，非递归算法更加高效： function search(root, k : integer) : integer; begin while (root<>0) and (k<>bst[root].key) do if k else root:=bst[root].right; search:=root; end; （二）求最小（大）关键字值的结点 要查找二叉树中具有最小关键字的结点，只要从根结点出发，沿着各结点的left指针查找下去，直到遇到NIL时为止。 下面给出从树的某个结点出发，查找其子树中最小关键字值的结点位置的函数。 function min(x : integer) : integer; begin while bst[x].left<>0 do x:=bst[x].left; min:=x; end; 二叉树的性质保证了上述函数的正确性。如果一个结点x无左子树，其右子树中的每个关键字都至少和key[x]一样大，则以x为根的子树中，最小关键字就是key[x]。如果结点x 有左子树，因其左子树中的关键字都不大于key[x]，而右子树中的关键字都不小于key[x]，因此，在以x为根的子树中，最小关键字可以在以left[x]为根的左子树中找到。 同样地，要查找二叉树中具有最大关键字的结点，只要从根结点出发，沿着各结点的right指针查找下去，直到遇到NIL时为止。这个过程与查找最小关键字的结点是对称的。 下面给出从树的某个结点出发，查找其子树中最大关键字值的结点位置的函数：function max(x : integer) : integer; begin while bst[x].right<>0 do x:=bst[x].right; max:=x; end; （三）求一棵二叉查找树中结点x的后继（前趋）结点。 给定一个二叉查找树中的结点，有时候要求找出在中序遍历顺序下它的后继（前驱）。如果所有的关键字都不相同，则某一个结点x的后继结点即具有大于key[x]中的关键字中最小者的那个结点。根据二叉查找树的结构，不用对关键字做任何比较，就可以找到某个结点的后继。 查找结点x的后继时需要考虑两种情况： （1）如果结点x的右子树非空，则x的后继即右子树中的最左（小）结点，如下图中关键字是6的结点的后继结点是关键字为7的结点，关键字是15的结点的后继结点是关键字为17的结点。 （2）如果结点x的右子树为空，且x有一个后继y，则y是x的最低祖先结点，且y的左儿子也是x的祖先。如下图中，关键字为13的结点的后继是关键字为15的结点。为找到y，可以从x开始往上查找，直到遇到某个结点是其父结点的左儿子结点时为止（或者某个节点的值恰好比x大为止，求前趋亦同）。 下面给出查找结点x的后继结点y的函数： function succ(x : integer) : integer; var y : integer; begin if bst[x].right<>0 then y:=min(bst[x].right) else begin y:=bst[x].p; while (bst[y].p<>0) and (x=bst[y].right) do begin x:=y; y:=bst[y].p; end; end; succ:=y; end; 相应地，查找结点x的前驱与后继是对称的，也需要考虑两种情况： （1）如果结点x的左子树非空，则x的前趋即左子树中的最右（大）结点，如上图中关键字是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 bst[x].left<>0 then y:=max(bst[x].left) else begin y:=bst[x].p; while (bst[y].p<>0) and (x=bst[y].left) do begin x:=y; y:=bst[y].p; end; end; pred:=y; end; 三、二叉查找树的插入与删除 插入和删除操作会引起以二叉查找树表示的动态集合的变化。要反应出这种变化，就要修改数据结构，但在修改的同时，还要保持二叉查找树性质。 （一）二叉查找树的插入 把结点z插入到二叉查找树T中，使T仍然满足二叉查找树的性质。 例如，下图是把关键字为14的结点，插入到一棵已存在的二叉查找树中的情况。从插入后的结果中可以看出：只要从根结点开始，不断沿着树枝下降即可。用指针x跟踪这条路径，而y始终指向x的父结点。根据key[z]与key[x]的比较结果，可以决定向左或者向右。直到x成为NIL时为止。这个NIL所占位置即我们想插入z的地方。 在下面描述的插入过程中，先将插入结点z的相关信息存放在bst数组的位置i上，插入结点的关键字为t。 procedure insert(i, t : integer); var x, y : integer; begin y:=0; x:=1; while (x<>0) and (bst[x].key<>0) do begin {从上往下找位置} y:=x; if t else x:=bst[x].right; end; bst[i].p:=y; bst[i].key:=t; {插入空树时，作为根结点} if y>0 then if t else bst[y].right:=i; end; 上述过程也可以用递归过程实现。递归过程中x为空结点位置，y为父结点位置，i为查找树数组位置，t为待插入结点z的关键字： procedure insert(x, y, i, t : integer); begin if x=0 then begin bst[i].key:=t; bst[i].p:=y; if t else bst[y].right:=i; end else if t then insert(bst[x].left, x, i, t) else insert(bst[x].right, x, i, t); end; （二）二叉查找树的删除 二叉查找树的删除比它的插入要复杂一些，因为除了把某个结点删除外，还需要考虑几个限制： （1）删除后，断开的二叉树需要重新链接起来。 （2）删除后，需保证二叉查找树性质不变。 （3）二叉树的高度决定效率，所以删除某个结点后，不能增加原二叉树的高度。 综合考虑上面的三个因素，针对被删除结点z的类型，可以分3种情况讨论： （1）如果被删除结点z为叶结点，只需清空其父结点指向它的指针，再把该结点释放 或 即可，即： bst[bst[z].p].left:=0 或 bst[bst[z].p].right:=0。 （2）如果被删除结点z 只有一个儿子，则可通过在其父结点和它的儿子结点之间建立一个链接，从而删除结点z 。即若结点z 无左子树，则用结点z 右子树的根结点代替结点z ，如下左图；若结点z 无右子树，则用结点z 左子树的根结点代替结点z ，如下右图。 （3）如果被删除结点z 的左右子树均存在，那么可以在其右子树中寻找关键字最小的结点，用它来代替被删除的结点，再把这个代替结点从原来的位置上删除；也可以在其左子树中寻找关键字最大的结点，用它来代替被删除的结点，再把这个代替结点从原来的位置上删除；还可以交替地用左子树中关键字最大的结点或者右子树中关键字最小的结点来代替被删除的结点，再把这个代替结点从原来的位置上删除。 以下是一个实现删除结点z 的过程： procedure delete(z : integer); var x, y : integer; begin if (bst[z].left=0) or (bst[z].right=0) then y:=z else y:=succ(z); {找到要删除的结点y} if bst[y].left<>0 then x:=bst[y].left else x:=bst[y].right; {x是y的孩子} if x<>0 then bst[x].p:=bst[y].p; if bst[y].p=0 then root:=x {删除的是根} else if y=bst[bst[y].p].left then bst[bst[y].p].left:=x else bst[bst[y].p].right:=x; if y<>z then bst[z].key:=bst[y].key; {如果结点中还有其它域，需要一并进行复制} end; 【例1】编程输入一组不同的大于0的整数（共n个），建立一棵二叉搜索树；再输入一个整数，作为关键字，找到这个关键字所指定的结点，并将这个结点删除；最后按中序遍历输出广义表形式。 〖参考程序〗 type node = record key : integer; left, right, p : integer; end; var bst : array[1..5000] of node; n, root : integer; k, x : integer; procedure insert(i, t : integer); var x, y : integer; begin y:=0; x:=1; while (x<>0) and (bst[x].key<>0) do begin y:=x; if t else x:=bst[x].right; end; bst[i].p:=y; bst[i].key:=t; if y>0 then if t else bst[y].right:=i; end; procedure main; var i, t : integer; begin readln(n); for i:=1 to n do begin read(t); insert(i, t); end; readln; readln(k); end; function min(x : integer) : integer; begin while bst[x].left<>0 do x:=bst[x].left; min:=x; end; function succ(x : integer) : integer; var y : integer; begin if bst[x].right<>0 then y:=min(bst[x].right) else begin y:=bst[x].p; while (bst[y].p<>0) and (x=bst[y].right) do begin x:=y; y:=bst[y].p; end; end; succ:=y; end; function search(root, k : integer) : integer; begin while (root<>0) and (k<>bst[root].key) do if k end; procedure delete(z : integer); var x, y : integer; begin if (bst[z].left=0) or (bst[z].right=0) then y:=z else y:=succ(z); if bst[y].left<>0 then x:=bst[y].left else x:=bst[y].right; if x<>0 then bst[x].p:=bst[y].p; if bst[y].p=0 then root:=x else if y=bst[bst[y].p].left then bst[bst[y].p].left:=x else bst[bst[y].p].right:=x; if y<>z then bst[z].key:=bst[y].key; end; procedure out(root : integer); begin write('('); if bst[root].left<>0 then out(bst[root].left); write(bst[root].key); if bst[root].right<>0 then out(bst[root].right); write(')'); end; begin fillchar(bst, sizeof(bst), 0); main; root:=1; x:=search(root, k); if x<>0 then delete(x); out(root); end. 至此，一般的二叉查找树的基本模块介绍完毕。当然二叉查找树能帮助我们实现的远不止上述功能，我们可以通过对二叉查找树数据结构中域的改变来实现一些我们需要的操作。如查找关键字为第k大（小）的结点，我们可以增加一个count域，count[z]的值为结点z 的左右子树中共有多少个结点，这样，就可以帮助我们在O(h)的时间复杂度内找出我们要找的结点。 但是二叉查找树并不一定是平衡树，它在最坏的情况下，二叉查找树可能会退化成含有n个结点的线性链（如输入结点信息时，其关键字严格按递增或递减顺序排列），此时在二叉查找树上进行的所有操作的时间复杂度都会退化达到O(n)。 四、随机构造的二叉查找树——Treap树 Treap树的基本思想是用随机化来优化BST，当一些元素以一个给定的顺序加入BST时，我们无法保证这些元素顺序的随机性。于是，我们可以给每个元素一个随机的优先权（可以 通过系统的随机函数取得），通过这个优先权使元素的顺序也具有随机性。即我们要构造这样一棵树：这棵树上的元素，它们的值符合BST 的性质，它们的优先权符合堆（Heap ，下文中均指最小堆）的性质。这就是Treap 名字的由来，“Treap ”＝“Tree + Heap ”。 例如，用（值，优先权）来表示元素，下面的左图就是合法的Treap ；而右图是BST ，但不是合法Treap ； 我们如何给这棵树插入元素呢？大体是两个步骤，首先是按照BST 的规则插入元素；然后再通过旋转，在不影响BST 性质的同时保证它满足堆的性质。 第一步非常简单，整个算法的关键就在第二步。首先介绍一种非常简单而实用的树的旋转，看这样的两棵树（如下图）： 不难发现，不论A 、B 、C 是怎样的结构，如果其中一棵树符合BST 性质，那么另一棵树就必定也符合BST 性质。这样我们就可以在不影响A 、B 、C 的同时，完成X 、Y 的交换。基于这条性质，如果在右图中X 的优先权比Y 的小，不符合堆的性质，我们就可以通过从右往左的一次变换，使X 出现在了Y 的上方，从而恢复其堆的性质。 由此可见，要完成插入元素的调整，只要不停地在它和它的父节点之间作旋转操作，直到他的父节点的优先权比他小就可以了。 看下面的例子，假设要插入的数依次为1、2、3、4、5、6，通过随机函数得到的优先权分别为10、22、5、80、37、45，插入过程可以描述如下： 这两次插入都没有影响堆的性质，所以就不需要进行旋转维护。 (3,5)插入后，由于5比22、10都小，所以要进行两次旋转操作，把(3,5)调整到了最上面，保证了优先权的堆性质。 (4,5) / \ (1,40) (8,27) / \ (6,92) (20,73) (4,50) / \ (1,40) (8,73) / \ (6,92) (20,27) (1,10) (1,10) \ (2,22) (1,10) (1,10) (3,5) \ \ / (2,22) ? (3,5) ? (1,10) \ / \ (3,5) (2,22) (2,22) (3,5) (3,5) (3,5) / \ / \ / \ (1,2) (4,80) ? (1,2) (5,37) ? (1,2) (5,37) \ \ \ / \ / \ (2,22) (5,37) (2,22) (4,80) (2,22) (4,80) (6,45) 接着插入4、5、6，并对4，5进行了旋转调整，完成了整棵树的插入。 通过观察，不难发现：如果把每个元素按照优先权大小的顺序（在上例中，即按照3、1、2、5、6、4的顺序）依次插入BST，形成的树和以上插入调整后的结果完全一致。这就是Treap 的作用，使得数据的插入实现了无关与数据本身的随机性，其效果与把数据打乱后插入完全相同。但与此同时，它没有改变插入的顺序，这使得它几乎能应用于所有需要使用平衡BST 的地方。 Treap的实质是元素的优先权具有堆性质的BST。Treap的应用，可以降低实现AVL的编程复杂度，同时它又具有不错的时间效率。在一般情况下，Treap的所建成的树的最大高度不大于4log2n，用它实现排序，时间也仅仅为没有退化的Qsort的2倍左右，可以说是比较理想的。 附、源程序： const maxn = 100000; type point = record lc, rc, fa : longint; num, priority : longint; end; var data : array[1..maxn] of longint; tree : array[0..maxn] of point; root, top, n : longint; function randompriority : longint; begin randompriority:=random(maxint); end; procedure init; var i : longint; begin readln(n); for i:=1 to n do read(data[i]); readln; randomize; top:=1; root:=1; tree[1].num:=data[1]; tree[1].priority:=randompriority; end; procedure tree_rotation_l(x, y, b : longint); //左旋 begin if tree[y].fa>0 then if tree[tree[y].fa].lc=y then tree[tree[y].fa].lc:=x else tree[tree[y].fa].rc:=x; tree[x].fa:=tree[y].fa; tree[x].rc:=y; tree[y].fa:=x; if b>0 then begin tree[y].lc:=b; tree[b].fa:=y; end else tree[y].lc:=0; end; procedure tree_rotation_r(x, y, b : longint); //右旋 begin if tree[y].fa>0 then if tree[tree[y].fa].lc=y then tree[tree[y].fa].lc:=x else tree[tree[y].fa].rc:=x; tree[x].fa:=tree[y].fa; tree[x].lc:=y; tree[y].fa:=x; if b>0 then begin tree[y].rc:=b; tree[b].fa:=y; end else tree[y].rc:=0; end; procedure tree_adjust(k : longint); //调整，保证元素优先权的堆性质 var t : longint; begin t:=tree[k].fa; while (t>0) and (tree[t].priority>tree[k].priority) do begin if tree[t].lc=k then tree_rotation_l(k, t, tree[k].rc) else tree_rotation_r(k, t, tree[k].lc); if t=root then root:=k; t:=tree[k].fa; end; end; procedure treap_add(k, num, priority : longint); //按照BST顺序插入 begin if tree[k].num=0 then begin tree[k].num:=num; tree[k].priority:=priority; tree_adjust(k); end else if num>tree[k].num then if tree[k].rc=0 then begin inc(top); tree[top].fa:=k; tree[k].rc:=top; treap_add(top, num, priority); end else treap_add(tree[k].rc, num, priority) else if tree[k].lc=0 then begin inc(top); tree[top].fa:=k; tree[k].lc:=top; treap_add(top, num, priority); end else treap_add(tree[k].lc, num, priority); end; procedure doit; var i : longint; begin for i:=2 to n do begin treap_add(root, data[i], randompriority); end; end; procedure out(k : longint); begin if tree[k].lc>0 then out(tree[k].lc); writeln(tree[k].num); if tree[k].rc>0 then out(tree[k].rc); end; begin assign(input, 'treap.in'); reset(input); assign(output, 'treap.out'); rewrite(output); init; doit; out(root); close(input); close(output); end. 五、应用举例 【例2】魔兽争霸（war）。 【问题描述 Description】 小x正在销魂地玩魔兽，他正控制着死亡骑士和n个食尸鬼（编号1～n）去打猎。 死亡骑士有个魔法，叫做“死亡缠绕”，可以给食尸鬼补充HP，战斗过程中敌人会对食尸鬼实施攻击，食尸鬼的HP会减少。 小x希望随时知道自己部队的情况，即HP值第k多的食尸鬼有多少HP，以便决定如何施放魔法，请同学们帮助他。 小x向你发出3种信号：（下划线在输入数据中表现为空格） A_i_a 表示敌军向第i个食尸鬼发出了攻击，并使第i个食尸鬼损失了a点HP，如果它的HP<=0，那么这个食尸鬼就死了。敌军不会攻击一个已死的食尸鬼。 C_i_a 表示死亡骑士向第i个食尸鬼放出了死亡缠绕，并使其增加了a点HP。HP值没有上限。死亡骑士不会向一个已死的食尸鬼发出死亡缠绕。 Q_k 表示小x向你发出询问。 输入格式 Input Format 第一行，一个正整数n；第二行n个整数，表示n个食尸鬼的初始HP值；第三行一个正整数m；以下m行，每行一个小x发出的信号。 输出格式 Output Format 对于小x的每个询问，输出HP第k多的食尸鬼有多少HP，如果食尸鬼总数不足k个，输出-1。每个一行数。 最后一行输出一个数：战斗结束后剩余的食尸鬼数。 样例输入 Sample Input 5 1 2 3 4 5 10 Q 2 A 4 6 C 1 4 Q 2 A 2 1 A 3 3 A 1 3 Q 4 C 2 10 Q 1 样例输出 Sample Output 4 5 -1 11 3 【数据范围 Date Range】 40%的数据：n<=3000，m<=5000；70%的数据：n<=8000，m<=10000； 100%的数据：n<=30000，m<=50000。 90%的数据随机生成，食尸鬼HP没有上限，数据保证任意时刻食尸鬼的HP值在longint 范围内，数据保证A和C命令中的食尸鬼是活着的，输入数据中没有多余空格、换行。 〖算法分析〗 本题考查二叉树的应用。 修改HP时把原HP值在树中删除，再将新的HP值插入，复杂度O(logn)。同时在树的每个节点上维护以该点为根的子树上共有多少个节点，则可以在O(logn)时间内回答询问。 总复杂度为O(m*logn)。 具体实现请参考标准程序 参考程序之一： 使用二叉查找树的简单实现，可以得到90分，第8个点采用了相对极端的数据，在构造二叉搜索树时几乎形成单边的树，蜕化为一条线。 const inf='war.in'; outf='war.out'; maxn=30000; var hp, bst : array[0..maxn] of longint; l, r, count : array[0..maxn] of longint; n, m : longint; root, size, free : longint; function insert(i, x : longint) : longint; begin if i=0 then begin if free=0 then begin inc(size); i:=size; end else begin i:=free; free:=0; end; bst[i]:=x; l[i]:=0; r[i]:=0; count[i]:=1; exit(i); end; if x then begin inc(count[i]); l[i]:=insert(l[i], x); end else begin inc(count[i]); r[i]:=insert(r[i], x); end; insert:=i; end; function find_min(i : longint) : longint; begin while l[i]<>0 do i:=l[i]; find_min:=bst[i]; end; function remove(i, x : longint) : longint; begin dec(count[i]); if x then l[i]:=remove(l[i], x) else if x>bst[i] then r[i]:=remove(r[i], x) else if (l[i]>0) and (r[i]>0) then begin bst[i]:=find_min(r[i]); r[i]:=remove(r[i], bst[i]); end else begin free:=i; if l[i]=0 then exit(r[i]) else exit(l[i]); end; remove:=i; end; function query(k : longint) : longint; var i : longint; begin i:=root; while i<>0 do begin if k>count[r[i]]+1 then begin dec(k, count[r[i]]+1); i:=l[i]; end else if k<=count[r[i]] then i:=r[i] else exit(bst[i]); end; end; procedure main; var i, k, x : longint; ch : char; begin readln(n); for i:=1 to n do begin read(hp[i]); root:=insert(root, hp[i]); end; readln(m); for i:=1 to m do begin read(ch); case ch of 'A' : begin readln(k, x); root:=remove(root, hp[k]); dec(hp[k], x); if hp[k]>0 then root:=insert(root, hp[k]) else dec(n); end; 'C' : begin readln(k, x); root:=remove(root, hp[k]); inc(hp[k], x); root:=insert(root, hp[k]); end; 'Q' : begin readln(k); if k>n then writeln(-1) else writeln(query(k)); end; end; end; end; begin assign(input, inf); reset(input); assign(output, outf); rewrite(output); main; writeln(n); close(input); close(output); end. 参考程序之二： 使用treap树实现，借助随机产生的数据，可以避免树蜕化为一条线的情况。 const inf='war.in'; ouf='war.out'; maxn=30000; var hp, treap : array[0..maxn] of longint; l, r, aux : array[0..maxn] of longint; count : array[0..maxn] of longint; n, m : longint; size : longint; root : longint; free : longint; procedure rotate_r(var i:longint); var j : longint; begin j:=l[i]; l[i]:=r[j]; r[j]:=i; count[j]:=count[i]; count[i]:=count[l[i]]+count[r[i]]+1; i:=j; end; procedure rotate_l(var i:longint); var j : longint; begin j:=r[i]; r[i]:=l[j]; l[j]:=i; count[j]:=count[i]; count[i]:=count[l[i]]+count[r[i]]+1; i:=j; end; procedure insert(var i:longint; x:longint); begin if i=0 then begin if free=0 then begin inc(size); i:=size; end else begin i:=free; free:=0; end; treap[i]:=x; aux[i]:=random(65535); count[i]:=1; l[i]:=0; r[i]:=0; exit; end; if x then begin insert(l[i], x); inc(count[i]); if aux[l[i]]>aux[i] then rotate_r(i); end else begin insert(r[i], x); inc(count[i]); if aux[r[i]]>aux[i] then rotate_l(i); end; end; procedure init; var i : longint; begin readln(n); 沈阳航空航天大学 课程设计报告 课程设计名称：数据结构课程设计课程设计题目：二叉排序树算法 院（系）：计算机学院 专业：计算机科学与技术 班级：04010103 学号：2010040101097 姓名：郭胜龙 指导教师：丁一军 此页为任务书 目录 1 课程设计介绍 (1) 1.1课程设计内容 (1) 1.2课程设计要求 (1) 2 课程设计原理 (2) 2.1课设题目粗略分析 (2) 2.2原理图介绍 (2) 2.2.1 功能模块图 (2) 2.2.2 main（主函数） (2) 2.2.3 SearchBST（查找） (3) 2.2.4 InsertBST（插入） (4) 2.2.5 CreatBST（建立） (4) 2.2.6 DeleteBST（删除） (4) 2.2.7 PreOrder（先序遍历） (5) 2.2.8 InOrder（中序遍历） (5) 3 数据结构分析 (7) 3.1存储结构 (7) 3.2算法描述 (7) 4 调试与分析 (12) 4.1调试过程 (12) 4.2程序执行过程 (12) 参考文献 (15) 附录（关键部分程序清单） (16) 沈阳航空航天大学课程设计报告 1 课程设计介绍 1.1 课程设计内容 题目内容: 1.构造二叉排序树; 2.输出该二叉排序树的先序、中序遍历序列； 3.删除该二叉排序树的任意一个结点； 4.输出删除后的二叉排序树的先序、中序遍历序列。 1.2课程设计要求 题目要求： 1.按要求建立不同的二叉排序树； 2.数据自定 3.独立完成课程设计任务 2 课程设计原理 2.1 课设题目粗略分析 根据课设题目要求，拟将整体程序分为七大模块。以下是七个模块的大体分 析： main （）：主函数模块 SearchBST （）：查找相应的结点 InsertBST1（）：插入一个新的结点 CreatBST （）：创建一棵二叉排序树 DeleteNode （）：删除结点 PreOrder （）对二叉排序树进行先序遍历 InOrder （）对二叉排序树进行中序遍历 2.2 原理图介绍 2.2.1 功能模块图 图2.2.1 功能模块结构图 2.2.2 main （主函数） 功能：连接各个函数，确定他们的执行顺序和条件。 二叉排 序树算法 主模块 查找模块 插入模块 建立模块 删除模块 先序遍历模块 中序遍历模块 #include 二叉排序树的基本操作的实现 ————————————————————————————————作者: ————————————————————————————————日期: 二叉排序树的基本操作的实现 一设计要求 1.问题描述 从磁盘读入一组数据,建立二叉排序树并对其进行查找、、遍历、插入、删除等基本操作。 2.需求分析 建立二叉排序树并对其进行查找,包括成功和不成功两种情况。 二概要设计 为了实现需求分析中的功能,可以从以下3方面着手设计。 1.主界面设计 为了方便对二叉排序树的基本操作，设计一个包含多个菜单选项的主控制子程序以实现二叉排序树的各项功能。本系统的主控制菜单运行界面如图1所示。 图1二叉排序树的基本操作的主菜单 2.存储结构的设计 本程序主要采二叉树结构类型来表示二叉排序树。其中二叉树节点由1个表示关键字的分量组成,还有指向该左孩子和右孩子的指针。 3.系统功能设计 本程序设置了5个子功能菜单，其设计如下。 1)建立二叉排序树。根据系统提示,输入节点的关键字,并以0作为结束的标识符。 该功能由Bｓtｒee Creａte（)函数实现。 2)插入二叉排序新的节点信息。每次只能够插入一个节点信息，如果该节点已 经存在,则不插入。该功能由Bstree Inｓerｔ(y)函数实现。 3)查询二叉排序树的信息。每次进行查询,成功则显示“查询到该节点”,不成功 则“显示查询不到该节点“该功能由Ｂsｔree Seaｒcｈ()函数实现。 4)删除二叉排序树的节点信息。可以对二叉排序树中不需要的节点进行删除， 删除的方式是输入关键字，查询到该节点后删除。该功能由ＢｓtreeＤelete() 函数实现。 5)遍历二叉排序树。遍历二叉排序树可以显示该二叉排序树的全部节点信息。 该功能由ｖoｉd Ｔraveｒse()实现。 三模块设计 1.模块设计 本程序包含两个模块:主程序模块和二叉排序树操作模块。其调用关系如图2 wyf 实现二叉排序树的各种算法 一.需求分析 (1)系统概述： 本系统是针对排序二叉树设计的各种算法，提供的功能包括有：（1）插入新结点（2）前序、中序、后序遍历二叉树（3）中序遍历的非递归算法（4）层次遍历二叉树（5）在二叉树中查找给定关键字(函数返回值为成功1,失败0) 二.总体设计 (1)系统模块结构图 (2)数据结构设计 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild;//左右孩子指针} BiTNode,*BiTree; typedef BiTree SElemType; typedef BiTree QElemType; typedef struct { QElemType *base; // 初始化的动态分配存储空间 int front; // 头指针,若队列不空,指向队列头元素 int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置 }SqQueue; typedef struct { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }SqStack; // 顺序栈 Status InitStack(SqStack &S) { // 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE // 请补全代码 S.base = (SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base) return (ERROR); S.top = S.base ; 二叉树查找 //树表的查找 #include bstnode * search_bst(bstnode *p,int k) { if(p==NULL||p->key==k) return p; if(k 平衡二叉树（AVL）查找、插入和删除 小组成员： 陈静101070009 陈丹璐101070006 陈娇101070008 目录 平衡二叉树（AVL） (1) 查找、插入和删除 (1) 问题描述 (2) 设计说明 (3) （一）ADT (3) （二）算法思想 (5) （三）数据结构 (12) （四）程序结构与流程 (13) 运行平台及开发工具 (15) I/O格式 (15) 算法复杂度分析 (18) 源代码 (18) 小结 (37) 问题描述 利用平衡二叉树实现一个动态查找表。 （1）实现动态查找表的三种基本功能：查找、插入和删除。 （2）初始时，平衡二叉树为空树，操作界面给出创建、查找、插入和删除和退出五种操作供选择。每种操作均要提示输入关键字。创建时，根据提示输入数据，以-1为输入数据的结束标志，若输入数据重复，则给出已存在相同关键字的提示，并不将其插入到二叉树中。在查找时，如果查找的关键字不存在，则显示不存在查找的关键字，若存在则显示存在要查找的关键字。插入时首先检验原二叉树中是否已存在相同第3 页共38 页- 3 -的关键字，若没有则进行插入并输出二叉树，若有则给出已有相同关键字的提醒。删除时首先检验原二叉树中是否存在要删除的关键字，若有则进行删除后并输出二叉树，若没有则给出不存在要删除的关键字的提醒。 （3）平衡二叉树的显示采用中序遍历的方法输出，还可以根据输出数据是否有序验证对平衡二叉树的操作是否正确。 设计说明 （一）ADT ADT BalancedBinaryTree{ 数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标志的数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： void R_Rotate(BSTree &p); 初始条件：二叉树存在，且关键字插入到以*p为根的二叉树的左子树的左孩子上； 操作结果：对以*p为根的二叉排序树作右旋处理 《算法分析与设计》 实验报告 题目： 姓名： 班级： 学号： 指导教师： 完成时间： 一、实验题目 给定一系列键值和权重，构造最优二叉排序树，使得总的查找次数最少。 二、实验目的 1. 理解时间复杂度的概念。 2. 深入地掌握C语言编程。 3. 通过编程直观地理解算法分析的意义 三、实验要求 给定一系列键值和权重，构造最优二叉排序树，使得总的查找次数最少。要求的输出格式为：第一行为最优的查找次数，第二行为最优二叉排序树的前序遍历得到的序列，然后一个空行，随后为源代码。算法的输入如下(冒号前为键值，冒号后为权重)：1:0 2:56 3:19 4:80 5:58 6:47 7:35 8:89 9:82 10:74 11:17 12:85 13:71 14:51 15:30 16:1 17:9 18:36 19:14 20:16 21:98 22:44 23:11 24:0 25:0 26:37 27:53 28:57 29:60 30:60 31:16 32:66 33:45 34:35 35:5 36:60 37:78 38:80 39:51 40:30 41:87 42:72 43:95 44:92 45:53 46:14 47:46 48:23 49:86 50:20 51:77 52:84 53:99 54:99 55:61 56:39 57:26 58:29 59:84 60:2 61:37 62:9 63:67 64:5 65:0 66:91 67:27 68:27 69:58 70:69 71:83 72:72 73:48 74:20 75:74 76:46 77:45 78:94 79:74 80:10 81:59 82:38 83:73 84:60 85:57 86:36 87:15 88:22 89:42 90:80 91:51 92:98 93:75 94:34 95:16 96:65 97:49 98:6 99:69 100:50 101:14 102:94 103:14 104:90 105:69 106:30 107:42 108:7 109:96 110:68 111:15 112:87 113:82 114:58 115:19 116:17 课程设计任务书 2011 —2012 学年第一学期 电子与信息工程系计算机专业09计算机一班班级 课程设计名称：数据结构课程设计 设计题目：排序二叉树的遍历 完成期限：自2012 年 1 月 2 日至2012 年 1 月 6 日共 1 周 设计依据、要求及主要内容（可另加附页）： 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩； （3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表； （4）认真编写课程设计报告。 三、设计内容 排序二叉树的遍历（用递归或非递归的方法都可以） 1)问题描述 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 2)基本要求 (1)用菜单实现 (2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。 四、参考文献 1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社 #include 二叉查找树（BST，Binary Search Tree），又名二叉搜索树或二叉检索树，是一颗满足如下条件的树： 1、每个节点包含一个键值 2、每个节点有最多两个孩子 3、对于任意两个节点x和y，它们满足下述搜索性质: a、如果y在x的左子树里，则key[y] <= key[x] b、如果y在x的右子树里，则key[y] >= key[x] 最优二叉查找树（Optimal BST，Optimal Binary Search Tree） 最优二叉查找树是使查找各节点平均代价最低的二叉查找树。具体来说就是：给定键值序列K = 《数据结构》实验报告 姓名： 班级： 学号： 一、算法简介 简单二叉树的创建，删除，查找 二、基本原理 定义节点的结构体，内部成员包括数据data，父节点指针*parent，左子节点指针*lchild，右子结点指针*rchild，以及指针next，然后通过add()和move()函数建立一个二叉树；最后通过del()删除整个二叉树。 三、实现步骤 第一，创建二叉树结点 第二，创建构造二叉树的函数add()和move().在add()中调用move()；然后在主函数中初始化二叉树为7个结点（通过建立二叉树的函数）。 创建的二叉树如图： 1 2 3 4 5 6 第三，最后一个个通过查找的方式进行删除结点。该方式不局限于顺序删除，可以 从任何一个结点开始删除，删除后会通过move重新构建，直到删除为止。 四、实验结果如下图 五、结论 本套算法在创建二叉树同时增加了有序检查，通过创建和删除一棵完全二叉树，还可以实现查找结点的功能，未实现遍历、插入、修改、替换等算法，程序较为简单，但是代码工整严谨，时间复杂度和空间复杂度可忽略不计。 六、源程序 #include void move(struct node *p,struct node *s) { while(0) { if(s->data > p->data ) { if(p->rchild==NULL) { p->rchild=s; break; } else { p=p->rchild; } } else { if(p->lchild==NULL) { p->lchild=s; break; } } } } void add(int x) { struct node *s=malloc(sizeof(struct node)),*p=malloc(sizeof(struct node)); s->data=x; s->lchild=NULL; s->rchild=NULL; s->parent=NULL; if(head==NULL) { head=s; } else { p=head; move(p,s); } 实验三二叉排序树的建立和查找 一、实验目的 1．掌握二叉排序树的建立算法 2．掌握二叉排序树查找算法。 二、实验环境 操作系统和C语言系统 三、预习要求 复习二叉排序树的生成及查找算法，编写完整的程序。 四、实验内容 实现二叉排序树上的查找算法。具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。 五、参考算法 #include else return SearchBST(T->rchild,key); /*继续在右子树中查找*/ } void InsertBST(BSTree *T,int key) { /*插入一个值为key的节点到二叉排序树中*/ BSTNode *p,*q; if((*T)==NULL) { /*树为空树*/ (*T)=(BSTree)malloc(sizeof(BSTNode)); (*T)->key=key; (*T)->lchild=(*T)->rchild=NULL; } else { p=(*T); while(p) { q=p; if(p->key>key) p=q->lchild; else if(p->key 二叉树查找-二分法查找二叉树 二分法查找二叉树方法：左大右小，找不到的时候就分支限定的查找#include 6.5 二叉排序树★3◎4 1．二叉排序树定义 二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。 （2）左右子树也都是二叉排序树，如图6-2所示。 2．二叉排序树的查找过程 由其定义可见，二叉排序树的查找过程为： （1）若查找树为空，查找失败。 （2）查找树非空，将给定值key与查找树的根结点关键码比较。 （3）若相等，查找成功，结束查找过程，否则： ①当给值key小于根结点关键码，查找将在以左孩子为根的子树上继续进行，转（1）。 ②当给值key大于根结点关键码，查找将在以右孩子为根的子树上继续进行，转（1）。 3．二叉排序树插入操作和构造一棵二叉排序树 向二叉排序树中插入一个结点的过程：设待插入结点的关键码为key，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，该插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。构造一棵二叉排序树则是逐个插入结点的过程。对于关键码序列为：｛63，90，70，55，67，42，98，83，10，45，58｝，则构造一棵二叉排序树的过程如图6-3所示。 4．二叉排序树删除操作 从二叉排序树中删除一个结点之后，要求其仍能保持二叉排序树的特性。 设待删结点为*p（p为指向待删结点的指针），其双亲结点为*f，删除可以分三种情况，如图6-4所示。 （1）*p结点为叶结点，由于删去叶结点后不影响整棵树的特性，所以，只需将被删结点的双亲结点相应指针域改为空指针，如图6-4（a）所示。 （2）*p结点只有右子树或只有左子树，此时，只需将或替换*f结点的*p子树即可，如图6-4（b）、（c）所示。 （3）*p结点既有左子树又有右子树，可按中序遍历保持有序地进行调整，如图6-4（d）、（e）所示。 设删除*p结点前，中序遍历序列为： ① P为F的左子女时有：…，Pi子树，P，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…。 ②P为F的右子女时有：…，F，Pi子树，P，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，…。 则删除*p结点后，中序遍历序列应为： ①P为F的左子女时有：…，Pi子树，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…。 ② P为F的右子女时有：…，F，Pi子树，Pj，S子树，Pk，Sk子树，…，P2，S2子树， 基于二叉排序树的商品信息查询算法的设计与实现 数据结构实验报告五 信计162班 刘禹熙· 160279 【实验学时】6学时 【实验目的】 熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。 【问题描述】 查找表是数据处理的重要操作，试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树，并比较两者的平均查找长度。 【基本要求】 （1）以链表作为存储结构，实现二叉排序树的建立、查找和删除。 （2）根据给定的数据建立平衡二叉树。 （3）比较二叉排序树和平衡二叉树的平均查找长度。 【测试数据】 随机生成。 【实现提示】 （1）初始，二叉排序树和平衡二叉树都为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每 次插入或删除一个结点后，应更新平衡二叉树或二叉排序树的显示。 （2）平衡二叉树或二叉排序树的显示可以采用凹入表形式，也可以采用图形界面画出树形。 【概要设计】 1.定义二叉树存储结构类型 ADT BiTree{ int data//每个树结点存放的数据值 BiTree *lchild,*rchild;//分支结点 函数类型： Bool searchBST（T,key,f,p） 操作结果：查找树T中是否有值为key的结点并让指针p指向该树根结点。 Bool insertBST(T,key) 操作结果：在树中插入尚未存在的结点权值为key的结点，若已有该节点则不插入。 Bool deleteBST(T,key) 操作结果：在树T中删除结点权值为key 的结点，若结点不存在则，返回false。 Void Tree_printing(T,ss) 操作结果，在距屏幕左侧ss的地方凹入法打印已经存储的二叉树。 } 2.main函数说明 功能包括：R:用伪随机发生成100个结点的商品二叉树，并用凹入法打印新生成的二叉树 C:创建二叉树，可以批量添加结点； I:创建一个二叉树结点，若结点存在则不插入，若不存在则插入，并打印插入后的二叉树 二叉搜索树 锁定 本词条由“科普中国”百科科学词条编写与应用工作项目审核。 在二叉排序树b中查找x的过程为： 若b是空树，则搜索失败，否则： 若x等于b的根结点的数据域之值，则查找成功；否则： 若x小于b的根结点的数据域之值，则搜索左子树；否则： 查找右子树。 Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &*p){ //在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，//则指针p指向该数据元素结点，并返回TRUE，否则指针指向查找路径上访问的最后//一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL if(!T){ p=f; return FALSE;} //查找不成功 else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功 else if LT(key,T->data.key) return SearchBST(T->lchild, key, T, p); //在左子树中继续查找 else return SearchBST(T->rchild, key, T, p); //在右子树中继续查找 pascal语言实现 type Link = ^tree; Tree = record D :longint; Left :link; Right :link; End; function search(n :longint;t :link):boolean; Begin If t^.d < n then begin If t^.right = nil then exit(false) else exit(search(n,t^.right)); End; If t^.d > n then begin If t^.left = nil then exit(false) else exit(search(n,t^.left)); End; Exit(true); End; 插入算法 向一个二叉排序树b中插入一个结点s的算法，过程为： 若b是空树，则将s所指结点作为根结点插入，否则： 若s->data等于b的根结点的数据域之值，则返回，否则： 若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：把s所指结点插入到右子树中。 #include } cursor = cursor->lchild; } else { if (NULL == cursor->rchild) { cursor->rchild = node; break; } cursor = cursor->rchild; } } } return; } /* 查找指定值*/ BSTree Search(BSTree tree, ElemType item) { BSTree cursor = tree; while (cursor) { if (item == cursor->data) return cursor; else if ( item < cursor->data) cursor = cursor->lchild; else cursor = cursor->rchild; } return NULL; } 线索二叉树的运算 1．查找某结点*p在指定次序下的前趋和后继结点 （1）在中序线索二叉树中，查找结点*p的中序后继结点 在中序线索二叉树中，查找结点*p的中序后继结点分两种情形： ①若*p的右子树空(即p->rtag为Thread)，则p->rchild为右线索，直接指向*p的中序后继。 【例】下图的中序线索二叉树中，结点D的中序后继是A。 ②若*p的右子树非空(即p->rtag为Link)，则*p的中序后继必是其右子树中第一个中序遍历到的结点。也就是从*p的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有左孩子的结点为止，该结点是*p的右子树中"最左下"的结点，即*P的中序后继结点。 【例】上图的中序线索二叉树中： A的中序后继是F，它有右孩子； F的中序后继是H，它无右孩子； B的中序后继是D，它是B的右孩子。 在中序线索二叉树中求中序后继结点的过程可【参见动画演示】，具体算法如下：BinThrNode *InorderSuccessor(BinThrNode *p) {//在中序线索树中找结点*p的中序后继，设p非空 BinThrNode *q； if (p->rtag==Thread) //*p的右子树为空 Return p->rchild；//返回右线索所指的中序后继 else{ q=p->rchild；//从*p的右孩子开始查找 while (q->ltag==Link) q=q->lchild；//左子树非空时，沿左链往下查找 return q；//当q的左子树为空时，它就是最左下结点 } //end if } 该算法的时间复杂度不超过树的高度h，即O(h)。 （2）在中序线索二叉树中查找结点*p的中序前趋结点 中序是一种对称序，故在中序线索二叉树中查找结点*p的中序前趋结点与找中序后继结点的方法完全对称。具体情形如下： ①若*p的左子树为空，则p->1child为左线索，直接指向*p的中序前趋结点； 【例】上图所示的中序线索二叉树中，F结点的中序前趋结点是A ②若*p的左子树非空，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。该结点是*p的左子树中"最右下"的结点，它是*p的左子树中最后一个中序遍历到的结点，即*p的中序前趋结点。 【例】上图所示中序线索二叉树中，结点E左子树非空，其中序前趋结点是I 在中序线索二叉树中求中序前趋结点的过程可【参见动画演示】，具体算法如下：BinThrNode *Inorderpre(BinThrNode *p) 北京理工大学珠海学院计算机学院课程设计 动态查找表 摘要 数据结构是研究与数据之间的关系 我们称这一关系为数据的逻辑结构 简 称数据结构。当数据的逻辑结构确定以后 数据在物理空间中的存储方式 称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构 因而有不同的算法。本次课程设计 程序中的数据采用“树形结构”作为其数据结构。具体采用 的是“二叉排序树” 并且使用“二叉链表”来作为其存储结构。本课程设计实现了二叉排序树的创建、中序遍历、插入、查找和删除二叉排序树中某个结点。本课程主要实现动态查找表的功能 通过“二叉排序树”的算法和“二叉链 表”的存储结构来实现。本课程设计说明书重点介绍了系统的设计思路、总体设计、各个功能模块的设计与实现方法。 关键词 数据结构 C语言二叉排序树动态二叉链表 1 2 目录 摘要 (1) 1ABSTRACT (3) 2 3抽象数据类型动态查找表定义 (4) 4 3 系统总体分析 (5) 3.1系统模块划分 (5) 3.2 二叉树的生成过程 (5) 3.3 主要功能模块设计 (5) 3.4 系统详细设计 (7) 3.4.1 主函数菜单模块 (7) 3.4.2 查找模块 (10) 3.4.3 删除模块 (11) 3.4.4 插入模块 (13) 3.4.5 中序输出模块 (15) 参考文献 (17) 心得体会 (18) 教师评语 (19) 附录 (20) 2 1 Abstract(摘要) Data structure is the relationship between research and data, we call this relationship as a logical data structure, referred to as data structures. When the data logical structure is determined, the data stored in the physical space, is known as the data storage structure. The same logical structure can have different storage structure, which has a different algorithm. The curriculum design, program data is "tree" as its data structure. Specific uses "binary sort tree" and use "binary list" as its storage structure. The course is designed to achieve a binary sort tree creation, in-order traversal, insert, find and delete a binary sort tree nodes. This course is mainly the function of dynamic look-up table, through the "binary search tree" algorithm and "binary list" of storage structures. This course is designed to highlight the system design concept, overall design, each functional module design and implementation. Keywords: C Language Data Structure Dynamic Binary Search Tree, Binary List 3二叉排序树算法
二叉树的建立,查找,删除,遍历
二叉排序树的基本操作的实现
实现二叉排序树的各种算法
二叉树查找
平衡二叉树(AVL)的查找、插入和删除
《算法设计与分析》--最优二叉排序树
数据结构课程设计二叉树遍历查找
最优二叉查找树
简单二叉树的创建,删除,查找
实验报告 实验三 二叉排序树的建立和查找
二叉树查找-二分法查找二叉树
二叉排序树
基于二叉排序树的商品信息查询算法的设计与实现-final
二叉搜索树
二叉排序树的查找
二叉树前驱后继的查找
动态查找表(二叉排序树)
- 最优二叉查找树
- 第9章-查找第3讲-动态查找表(二叉排序树)
- 二叉排序树的实现
- 在二叉排序树中查找关键字为key地记录簿
- 二叉排序树用于动态查找
- 二叉排序树
- 22 9 查找2-二叉排序树
- 第9章-查找第3讲-动态查找表(二叉排序树)
- 二叉排序树的基本操作的实现
- 二叉排序树查找算法
- 二叉排序树的建立及查询
- 二叉搜索树(BinarySearchTree).
- 最优二叉查找树(动态规划)
- 二叉排序树(BST)、二叉查找树的建立
- 实验报告 实验三 二叉排序树的建立和查找
- (完整word版)在二叉排序树中查找关键字为key地记录簿
- 最优二叉查找树算法c++实现
- 二叉排序树的建立插入删除和查找
- 二叉排序树的查找实验报告
- 动态查找表(二叉排序树)