列。这方面的内容,需要用图片进行形象的展示。 (6)二叉搜索树 叉搜索树是一类满足以下属性的特殊二叉树:二叉搜索树中的每个非空结点表示 一个记录:某结点左子树不空,则左子树上所有结点的值均小于该结点的关键码值;若 其右子树不为空,则右子树上所有结点的值均大于该结点的关键码值。二叉搜索树可以 是一棵空树,任何结点的左右子树都是二叉搜索树。按照中序周游整个二叉树得到一个 由小到大有序排列。 叉搜索树的检索过程:将给定值key与根结点的关键码比较,如果key小于根结 点的值,则只需要检索左子树;如果key大于根结点的值,就只检索右子树。这个过程 一直持续到key被匹配成功或者遇到叶结点为止。如果遇到叶结点仍没有发现key,那 么key就不在这棵二叉搜索树中。 二叉搜索树插入操作:将待插入结点的关键码与根结点的关键码相比较,若待插入 的关键码小于根结点的关键码,则进入左子树,否则进入右子树。按照同样的方式沿检 索路径直到叶结点,确定插入位置,把待插入结点作为一个新叶结点插入到二叉搜索树 中 改进的二叉搜索树结点删除算法的思想为:若结点 pointer没有左子树,则用 pointer 右子树的根代替被删除的结点 pointer;若结点 pointer有左子树,则在左子树里找到按 中序周游的最后一个结点 temppointer(即左子树中的最大结点)并将其从二叉搜索树 里删除,由于 temppointer没有右子树,删除该结点只需用 temppointer的左子树代替 temppointer,然后用 temppointer结点代替待删除的结点 pointer. (7)霍夫曼树的构造方法 霍夫曼树的构造过程是 (1)对于给定的n个权值wo,w,…,wn-(n≥2),构成n棵二叉树的集合T={To Tn-},使得每一棵扩充二叉树只具有一个带权为w;的根结点。 (2)构造一棵新的扩充二叉树,在集合T中找出两个权值最小的树作为新树根结点 的左右子树,把新树根结点的权值赋为其左右子树根结点的和。 (3)在集合T中删除这两棵树,并把得到的新扩充二叉树加入到集合中 (4)重复步骤(2)、(3)的操作,直到集合T中只含有一棵树为止。 对于构造过程的讲解,最好是通过自定义动画进行逐步展示,这样更形象一些。从 Huffman树的构建过程也可以看出,结点的权值越大,那么它到根结点的路径就越短; 权值越小,结点就会放到离根结点较远的位置上。4 列。这方面的内容，需要用图片进行形象的展示。 （6）二叉搜索树 二叉搜索树是一类满足以下属性的特殊二叉树：二叉搜索树中的每个非空结点表示 一个记录；某结点左子树不空，则左子树上所有结点的值均小于该结点的关键码值；若 其右子树不为空，则右子树上所有结点的值均大于该结点的关键码值。二叉搜索树可以 是一棵空树，任何结点的左右子树都是二叉搜索树。按照中序周游整个二叉树得到一个 由小到大有序排列。 二叉搜索树的检索过程：将给定值 key 与根结点的关键码比较，如果 key 小于根结 点的值，则只需要检索左子树；如果 key 大于根结点的值，就只检索右子树。这个过程 一直持续到 key 被匹配成功或者遇到叶结点为止。如果遇到叶结点仍没有发现 key，那 么 key 就不在这棵二叉搜索树中。 二叉搜索树插入操作：将待插入结点的关键码与根结点的关键码相比较，若待插入 的关键码小于根结点的关键码，则进入左子树，否则进入右子树。按照同样的方式沿检 索路径直到叶结点，确定插入位置，把待插入结点作为一个新叶结点插入到二叉搜索树 中。 改进的二叉搜索树结点删除算法的思想为：若结点 pointer 没有左子树，则用 pointer 右子树的根代替被删除的结点 pointer；若结点 pointer 有左子树，则在左子树里找到按 中序周游的最后一个结点 temppointer（即左子树中的最大结点）并将其从二叉搜索树 里删除，由于 temppointer 没有右子树，删除该结点只需用 temppointer 的左子树代替 temppointer，然后用 temppointer 结点代替待删除的结点 pointer。 （7）霍夫曼树的构造方法 霍夫曼树的构造过程是： (1) 对于给定的 n 个权值 w0，w1，„，wn－1(n≥2)，构成 n 棵二叉树的集合 T = { T0， T1，T2，„，Tn－1}，使得每一棵扩充二叉树只具有一个带权为 wi的根结点。 (2) 构造一棵新的扩充二叉树，在集合 T 中找出两个权值最小的树作为新树根结点 的左右子树，把新树根结点的权值赋为其左右子树根结点的和。 (3) 在集合 T 中删除这两棵树，并把得到的新扩充二叉树加入到集合中。 (4) 重复步骤(2)、(3)的操作，直到集合 T 中只含有一棵树为止。 对于构造过程的讲解，最好是通过自定义动画进行逐步展示，这样更形象一些。从 Huffman 树的构建过程也可以看出，结点的权值越大，那么它到根结点的路径就越短； 权值越小，结点就会放到离根结点较远的位置上