原创 左子树上的所有节点值均小于根节点值 右子树上的所有节点值均大于根节点值 左右子树也满足上述两个条件。 遍历(Traversal)，就是沿着某条搜索路线，依次对树中每个结点均做一
左子树上的所有节点值均小于根节点值
右子树上的所有节点值均大于根节点值
左右子树也满足上述两个条件。
遍历(Traversal)，就是沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。
通过中序遍历, 可以输出各结点的键值为递增排序的结果
最小键值是根节点左子树的最左侧子节点的键值
最大键值是根节点右子树的最右侧子节点的键值
+++++++++++++++
测试代码：
<script>
var input= new Array(45,12,53,10,37,24,90,61,99,98);
var tree = new Node(45);
for (var i=1;i<input.length;i++)
insert(tree, input[i]);
document.write("前序遍历：");
preorder(tree);
document.write("<br>中序遍历 (输出为递增排序的结果) : ");
inorder(tree);
document.write("<br>后序遍历: ") ;
postorder(tree);
document.write("<br>");
document.write("最大值： " + maximum(tree));
document.write("<br>");
document.write("最小值: " + minimum(tree));
remove(tree, 99);
document.write("<br>中序遍历 (输出为递增排序的结果) : ");
inorder(tree);
</script>
+++++++++++++++++++++++
测试输出：
前序遍历：45 12 10 37 24 53 90 61 99 98
中序遍历 (输出为递增排序的结果) : 10 12 24 37 45 53 61 90 98 99
后序遍历: 10 24 37 12 61 98 99 90 53 45
最大值： 99
最小值: 10
中序遍历 (输出为递增排序的结果) : 10 12 24 37 45 53 61 90 98
1. [图片] tree.png
2. [代码][JavaScript]代码
<! protrammer: Xu Tongchun, July 22, 2016>
<html>
<head>
<title>二叉查询树 Binary Search Tree</title>
<meta charset="utf-8">
<script type="text/javascript">
function Node(key){ // 创建一个结点的构造方法
this.key = key;
this.left = null;
this.right = null;
}
function insert(root,k){
/*在二叉树 root 中, 若没有键值 key 为 k 的结点, 则插入这个结点*/
var f=root;
var p=root;
while( p ) {//找出即将插入的结点的父结点 f
if(p.key==k) //如果在现存树之中，已经有键值为 k 的结点，
return; // 则无需再插入新结点，应立刻终止方法调用
f=p;
p=(k < p.key)? p.left : p.right;
}
p=new Node(k); //创建键值为 k 的新结点 p
if(!root) root=p; //若树没有根，则新结点为树的根
else//按键值 k 的大小，使 p 成为其父结点 f 的 左孩子或右孩子
if (k<f.key) f.left=p; else f.right=p;
}
function remove(root, key) {/*二叉树 root 中删去关键字为 key 的结点*/
var parent = null, p = root, q, child;
var isleft = false;
while(p) { //开始找待删除的结点 p
if (p.key == key) // 如果发现关键字为 key 的结点，
break; // 则待删除结点 p 找到，故终止while 循环
parent = p; // 标记父结点
// 往下继续找 待删除结点 p
if (key < p.key){ //若待删除的结点的键值 key 小于当前结点的键值，
p=p.left; //则顺左子树继续找
isleft = true; // 是左孩子
} else { //若待删除的结点的键值 key 大于当前结点的
p=p.right;//则右子树继续找
isleft =false; // 不是左孩子
}
}
if (!p) return; //找不到要删除的点，则终止remove() 方法
q = p; // 换成 q 来标记待删除结点 p
/* 若 q 有右孩子, 则要找到 q 的右子树中的最小值的结点 p 取代之.
* 此时 p 称为 q 的中序后继 */
if ( q.right)
for (parent=q, p=q.right; p.left; parent=p, p=p.left);
// 标记 p 的孩子， 若 chil d为空， 则 p 是叶子
child = (p.left) ? p.left : p.right;
/* 删除 q 的中序后继结点 p , 然后将 p 的键值，赋予 q,
* 这样，待删除结点的键值, 就不复存在
*/
if( !parent) //若 p 没有父结点，说明 p 是 根
root = child; //根变为 dhild
else { //若 p 有父结点(即不是根), 则将p的孩子结点与p的父结点链接
if (p==parent.left)
parent.left=child;
else
parent.right = child;
/* 将待删除结点 q 的键值，变为中它的中序后继结点 p 的键值,
这样，待删除结点就不复存在 */
if (p != q)
q.key = p.key;
}
}
function minimum(root) { //在二叉树 root 中找出最小 key值
var current, last;
current = root;
while(current) {
last = current;
current = current.left;
}
return last.key;
}
function maximum(root) {//在二叉树 root 中找出最大 key值
var current, last;
current = root;
while(current) {
last = current;
current = current.right;
}
return last.key;
}
function search_recursion(root, k) { //递归法 查询
if (root == null)
return(null);
else {
if (root.key == k) return(root);
else if (k < root.key)
return(search_recursion(root.left, k));
else
return (search_recursion(root.right,k));
}
}
function search_Iteration(root, k) {//迭代法 查询
while (root != NULL) {
if (root.key == k) return(root);
else if (k < root.key)
root = root.left;
else
root = root.right;
}
return(null);
}
function inorder(root) {//中序遍历
var p=root;
if (p==null) return;
inorder(p.left);
document.write( p.key + " ");
inorder(p.right);
}
function preorder(root) {//前序遍历
var p=root;
if (p==null) return;
document.write(p.key + " ");
preorder(p.left);
preorder(p.right);
}
function postorder(root) {//后序遍历
var p=root;
if (p==null) return;
postorder(p.left);
postorder(p.right);
document.write( p.key + " ");
}
</script>
<style>
</style>
</head>
<body>
<script>
var input= new Array(45,12,53,10,37,24,90,61,99,98);
var tree = new Node(45);
for (var i=1;i<input.length;i++)
insert(tree, input[i]);
document.write("前序遍历：");
preorder(tree);
document.write("<br>中序遍历 (输出为递增排序的结果) : ");
inorder(tree);
document.write("<br>后序遍历: ") ;
postorder(tree);
document.write("<br>");
document.write("最大值： " + maximum(tree));
document.write("<br>");
document.write("最小值: " + minimum(tree));
remove(tree, 99);
document.write("<br>中序遍历 (输出为递增排序的结果) : ");
inorder(tree);
</script>
</body>
</html>