首页 > 代码库 > javascript实现BST

javascript实现BST

思路:
1.建立节点构造函数
2.插入节点过程:先判断当前节点上是否有值,有则通过与当前节点值比较,进入左节点或者右节点,否则将值赋给当前节点
3.创建二叉树和根节点,并进行节点添加
4.遍历节点上的值,对创建的二叉树测试
function Node(){

this.value = http://www.mamicode.com/null;
this.lChild = null;
this.rChild = null;

}

function BSTInsert(node,value){
if(node.value =http://www.mamicode.com/== null)
{
node.value = http://www.mamicode.com/value; // node = new Node() 这种操作会与原始树断开
node.rChild = new Node();
node.lChild = new Node();
return true;
}

if(node.value =http://www.mamicode.com/= value){
return false;
}

if(node.value > value)
{
return BSTInsert(node.lChild,value);
}
else{
return BSTInsert(node.rChild,value);
}

}

function creatBST(arr){
var T = null;

T = new Node();
T.value = http://www.mamicode.com/0;
T.rChild = new Node();
T.lChild = new Node();
for(var i = 0;i<arr.length;i++)
{
//console.log(T);
BSTInsert(T,arr[i]);
}
inOrderTravers(T);
}

function inOrderTravers(T){
if(T.value !==null)
{
inOrderTravers(T.lChild);
console.log(T.value);
inOrderTravers(T.rChild);

}
}

var arrTmp = [1,2,3,4,5,6,7,8,9];
creatBST(arrTmp);

javascript实现BST