二叉查找树和二叉搜索树_二叉树的高度

二叉树和二叉查找树 　　1.二叉树和二叉查找树 　　1）什么是树？ 　　树由一组以边连接的节点组成，一棵树最上面的节点称为 根节点，如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子 节点。一个节点可以有 0 个、1 个或多个子节点。没有任何子节点的节点称为叶子节点。

　　图 10-2：一棵树的局部 　　2）二叉树和二叉查找树 　　二叉树是一种特殊的树，它的子节点个数不超过两个。二叉树具有一些特殊的计算性质， 使得在它们之上的一些操作异常高效。 　　沿着一组特定的边，可以从一个节点走到另外一个与它不直接相连的节 点。从一个节点到另一个节点的这一组边称为路径，在图中用虚线表示。以某种特定顺序 访问树中所有的节点称为树的遍历。 　　树可以分为几个层次，根节点是第 0 层，它的子节点是第 1 层，子节点的子节点是第 2 层，以此类推。树中任何一层的节点可以都看做是子树的根，该子树包含根节点的子节 点，子节点的子节点等。我们定义树的层数就是树的深度。最后，每个节点都有一个与之相关的值，该值有时被称为键。 　　满足以下性质： 　　1）没有键值相等的节点。 　　2）一个父 节点的两个子节点分别称为左节点和右节点，特点：由上至下，由左至右。 　　3）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 　　4）.若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 　　5）每层都被塞满时，查找效率最高，最高为O(log n)。当二叉查找树退化为单链表时，查找效率最低，最低为O(n)。 　　2 .1遍历 　　这里讲解前序遍历、中序遍历、后序遍历3种方式。 　　2.11 前序遍历若二叉树非空，则执行以下操作：(01) 访问根结点；(02) 先序遍历左子树；(03) 先序遍历右子树。 　　前序遍历代码 　　2.12 中序遍历 　　若二叉树非空，则执行以下操作：(01) 中序遍历左子树；(02) 访问根结点；(03) 中序遍历右子树。 　　中序遍历代码 　　2.13 后序遍历 　　若二叉树非空，则执行以下操作：(01) 后序遍历左子树；(02) 后序遍历右子树；(03) 访问根结点。 　　后序遍历代码 　　看看下面这颗树的各种遍历方式：http://images.cnitblog.com/i///2177.jpg

　　对于上面的二叉树而言， 　　(01) 前序遍历结果： 3 1 2 5 4 6(02) 中序遍历结果： 1 2 3 4 5 6 (03) 后序遍历结果： 2 1 4 6 5 3 　　2.2 查找最小值和最大值 　　查找 BST 上的最小值和最大值非常简单。因为较小的值总是在左子节点上，在 BST 上查 找最小值，只需要遍历左子树，直到找到最后一个节点。 　　2.21 最小值 　　getMin() 方法查找 BST 上的最小值，该方法的定义如下： 　　function getMin() { 　　var current = this.root; 　　while (!(current.left == null)) { 　　current = current.left; 　　} 　　return current.data; 　　} 　　该方法沿着 BST 的左子树挨个遍历，直到遍历到 BST 最左边的节点，该节点被定义为： 　　current.left = null; 　　这时，当前节点上保存的值就是最小值。 　　2.22 最大值 　　在 BST 上查找最大值，只需要遍历右子树，直到找到最后一个节点，该节点上保存的值即 为最大值。 　　getMax() 方法的定义如下： 　　function getMax() { 　　var current = this.root; 　　while (!(current.right == null)) { 　　current = current.right; 　　} 　　return current.data; 　　} 　　2.23 例 10-3 使用前面用过的 BST 数据测试了 getMin() 和 getMax() 方法。 　　var nums = new BST(); 　　nums.insert(23); 　　nums.insert(45); 　　nums.insert(16); 　　nums.insert(37); 　　nums.insert(3); 　　nums.insert(99); 　　nums.insert(22); 　　var min = nums.getMin(); 　　print(“The minimum value of the BST is: ” + min); 　　print(“\n”); 　　var max = nums.getMax(); 　　print(“The maximum value of the BST is: ” + max); 　　程序输出如下： 　　The minimum value of the BST is: 3 　　The maximum value of the BST is: 99 　　这两个方法返回最小值和最大值，但有时，我们希望方法返回存储最小值和最大值的节 点。这很好实现，只需要修改方法，让它返当前回节点，而不是节点中存储的数据即可 　　3. 查找给定值 　　在 BST 上查找给定值，需要比较该值和当前节点上的值的大小。通过比较，就能确定如果 给定值不在当前节点时，该向左遍历还是向右遍历。 　　find() 方法用来在 BST 上查找给定值，定义如下： 　　function find(data) { 　　var current = this.root; 　　while (current != null) { 　　if (current.data == data) { 　　return current; 　　} else if (data < current.data) { 　　current = current.left; 　　}else { 　　current = current.right; 　　} 　　} 　　return null; 　　} 　　如果找到给定值，该方法返回保存该值的节点；如果没找到，该方法返回 null。 　　例 10-4 提供了一段代码来测试 find() 方法。使用 find() 方法查找给定值 　　load(“BST”); 　　var nums = new BST(); 　　nums.insert(23); 　　nums.insert(45); 　　nums.insert(16); 　　nums.insert(37); 　　nums.insert(3); 　　nums.insert(99); 　　nums.insert(22); 　　inOrder(nums.root); 　　print(“\n”); 　　putstr(“Enter a value to search for: “); 　　var value = parseInt(readline()); 　　var found = nums.find(value); 　　if (found != null) { 　　print(“Found ” + value + ” in the BST.”); 　　} else { 　　print(value + ” was not found in the BST.”); 　　} 　　输出如下： 　　3 16 22 23 37 45 99 　　4.插入 　　首先要创建一个 Node 对象，将数据传入该对象保存。 　　其次检查 BST 是否有根节点，如果没有，那么这是棵新树，该节点就是根节点，这个方法 到此也就完成了；否则，进入下一步。 　　如果待插入节点不是根节点，那么就需要准备遍历 BST，找到插入的适当位置。该过程类 似于遍历链表。用一个变量存储当前节点，一层层地遍历 BST。 　　(1) 设根节点为当前节点。 　　(2) 如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反 之，执行第 4 步。 　　(3) 如果当前节点的左节点为 null，就将新的节点插入这个位置，退出循环；反之，继续 执行下一次循环。 　　(4) 设新的当前节点为原节点的右节点。 　　(5) 如果当前节点的右节点为 null，就将新的节点插入这个位置，退出循环；反之，继续 执行下一次循环。 　　下面是插入动画效果：

　　例 10-1　BST 类和 Node 类 　　function Node(data, left, right) { 　　this.data = data; 　　this.left = left; 　　this.right = right; 　　this.show = show; 　　} 　　function show() { return this.data; } 　　function BST() { 　　this.root = null; 　　this.insert = insert; 　　this.inOrder = inOrder; 　　} 　　function insert(data) { 　　var n = new Node(data, null, null); 　　if (this.root == null) { 　　this.root = n; 　　} else { 　　var current = this.root; 　　var parent; 　　while (true) { 　　parent = current; 　　if (data < current.data) { 　　current = current.left; 　　if (current == null) { 　　parent.left = n; 　　break; 　　} 　　} else { 　　current = current.right; 　　if (current == null) { 　　parent.right = n; 　　break; 　　} 　　} 　　} 　　} 　　} 　　5. 从二叉查找树上删除节点 　　从 BST 上删除节点的操作最复杂，其复杂程度取决于删除哪个节点。如果删除没有子节点 的节点，那么非常简单。如果节点只有一个子节点，不管是左子节点还是右子节点，就变 得稍微有点复杂了。 　　1）从 BST 中删除节点的第一步是判断当前节点是否包含待删除的数据，如果包含，则删除该 节点；如果不包含，则比较当前节点上的数据和待删除的数据。如果待删除数据小于当前 节点上的数据，则移至当前节点的左子节点继续比较；如果删除数据大于当前节点上的数 据，则移至当前节点的右子节点继续比较。 　　2）如果待删除节点是叶子节点（没有子节点的节点），那么只需要将从父节点指向它的链接 指向 null。

　　3）如果待删除节点只包含一个子节点，那么原本指向它的节点就得做些调整，使其指向它的 子节点。

　　4）如果待删除节点包含两个子节点，正确的做法有两种：要么查找待删除节点左子树 上的最大值，要么查找其右子树上的最小值。

　　如：这里我们选择后一种方式。我们需要一个查找子树上最小值的方法，后面会用它找到的最小值创建一个临时节点。将 临时节点上的值复制到待删除节点，然后再删除临时节点。 　　图 10-7：删除包含两个子节点的节点 　　整个删除过程由两个方法完成。remove() 方法只是简单地接受待删除数据，调用 removeNode() 删除它，后者才是完成主要工作的方法。两个方法的定义如下：

　　此文原著，若觉得有不符的地方欢迎指出，谢谢！