在初始化一棵二叉树时,每次将插入的结点和父结点进行对比,比父结点小的子结点插到左子树中,比父结点大的子结点插到右子树中。当需要查找最小值时从左子树中递归查找,当需要查找最大值时从右子树中递归查找。
例如:存在一个数组,其值为[8 3 10 1 6 14 4 7 13],需要从中找出最大值和最小值。
(1)查找最小值。
构造一棵二叉树,8为根结点,存在左子树和右子树;当根结点8和子结点3比较时,8大于3,将子结点插入左子树中;在插入左子树时还要判断根结点下的左子树是否已存在结点,如果为空结点则直接插入结点,若不是空结点则将父结点和新结点做对比;若父结点大于子结点则插入左子树中,否则插入右子树。注意:如果存在父结点和子结点相等,那么不用插入或进行其他操作。初始化对比过程如图1所示。
经多次遍历对比后,得到的结果如图2所示。
图1 新结点的插入过程 图2 最终的二叉树 这样保证了左子树保存的永远是较小值,求最小值时,只需对左子树遍历,判断父结点下的左子树是否存在结点,若不存在结点则该父结点就是最小值。
(2)查找最大值。
与查找左子树同理,在最初插入结点时已经将每个根结点和新结点进行了对比,保证了插入到右子树的结点都是最大值。当要求找出最大值时,只需对右子树进行遍历,判断父结点下的右子树是否存在结点,若不存在结点则该父结点就是最大值。代码实现如下所示。
function Node(key, left, right){
this.key=key;
this.left=left;
this.right=right;
}
function BinaryTree(){
this.root=null;
}
BinaryTree.prototype={
insertNode: function (node, newNode){ //插入结点
if(node.key<newNode.key){
//如果父结点小于子结点,插到右边
node.right? this.insertNode(node.right,newNode):(node.right=newNode);
}else if(node.key>newNode.key){
//如果父结点大于子结点,插到左边
node.left? this.insertNode(node.left, newNode): (node.left=newNode);
}
},
insert: function (key){
var newNode=new Node(key);
if(this,root){
this.insertNode(this.root,newNode);
}else{
this.root=newNode;
}
},
findMin: function(){ //寻找最小值
//不断查找它的左予树,直到这个左子树的结点为叶子结点
if(this.root){
this.findMinNode(this.root);
}
},
findMinNode: function (node){
if(node.left){
this.findMinNode(node.left);
}else{
console.log("这个二叉树的最小值为:",node.key);
}
},
findMax: function(){ //寻找最大值
if(this.root){
this.findMaxNode(this.root);
}
},
findMaxNode: function (node){
if(node.right){
this.findMaxNode(node.right);
}else{
console.log("这个二叉树的最大值为:",node.key);
}
}
};
var tree=new BinaryTree(),
nodes=[8,3,10,1,6,14,4,7,13],
txt="";
nodes.forEach(function (value, key){
tree.insert(value);
txt+=value+"";
});
console.log("二叉树的结构:",txt), //8 3 10 1 6 14 4 7 13
tree.findMin(); //1
tree.findMax(); //14
根据以上代码,求最小值时,需要对左子树进行多次递归判断,如果左子树的父结点下有结点则需判断该结点下是否还有结点,如果没有则该结点就是最小值,否则需要继续遍历下去。求最大值时同理,对右子树递归判断右结点时,如果右结点下面没有子结点则该结点就是最大值,否则需要继续遍历右结点下的结点,直至找到右子树的最后一个右结点。