二叉树这个数据结构的好处
目前在我的脑海中还是局限于
收入与查找数据的
条理性和
高速性。
以前是用C写的，现在忘得差不多了，好像是用指针p->leftChildren ， p->rightChildren
现在我们用JS来模拟一下。
开始的时候，用什么数据结构来模拟tree呢。。。bingo，用
{} object
文章比较长，有耐心的童鞋可以看下，木有耐心的童鞋可以看其他的文章~~~
1) 初始的Tree数据：
10
/ \
6 15
/ \ / \
3 8 14 20
\ /
4 7
/*
tree都有value和left，right值，如果为空的话，3者都为null
*/
var tree={
value:10,
left:{
value:6,
left:{
value:3,
left:{
value:null,
left:null,
right:null
},
right:{
value:4,
left:null,
right:null
}
},
right:{
value:8,
left:{
value:7,
left:null,
right:null
},
right:{
value:null,
left:null,
right:null
}
}
},
right:{
value:15,
left:{
value:14,
left:null,
right:null
},
right:{
value:20,
left:null,
right:null
}
}
};
2) 首先是二叉树的遍历，有3种遍历方式：前序遍历，中序遍历，后序遍历。
/*
* 二叉树的遍历
*/
var readTree=(function(){
var
//存储结果集合
r = [],
//遍历读取二叉树的函数
rt = function(tree, type){
// 'f' 先序遍历,first
// 'm' 中序遍历,middle
// 'a' 后序遍历,after
var t = typeof type === 'undefined'?'f': type;
switch (t) {
case "f":
if (tree !== null) {
if (tree.value !== null) {
r.push(tree.value);
}
rt(tree.left, "f");
rt(tree.right, "f");
}
break;
case "m":
if (tree !== null) {
rt(tree.left, "m");
if (tree.value !== null) {
r.push(tree.value);
}
rt(tree.right, "m");
}
break;
case "a":
if (tree !== null) {
rt(tree.left, "a");
rt(tree.right, "a");
if (tree.value !== null) {
r.push(tree.value);
}
}
break;
}
},
getResult=function(tree, type){
rt(tree, type);
return r;
};
return getResult;
})();
3) 写二叉树：
var writeTree=(function(){
var cloneTree={},
//克隆{}
cloneObject=function(tree){
var o={}
for(var i in tree){
o[i]=tree[i];
}
return o;
},
wt=function(tree,num){
if(tree!==null){
if(num==tree.value){
alert(num+"已经在树里面了");
return;
}else if(num lt;tree.value){
if(tree.left!==null){
//找到了左节点
if(num >tree.left.value){
//clone左边的剩余节点
var tempLeft=cloneObject(tree.left);
tree.left={
value:num,
left:tempLeft,//保持连接
right:null
}
return;
}else{
wt(tree.left,num);
}
}else{
tree.left={
value:num,
left:null,
right:null
};
return;
}
}else if(num > tree.value){
if(tree.right!==null){
if(num <tree.right.value){
var tempRight=cloneObject(tree.right);
tree.right={
value:num,
left:null,
right:tempRight
}
return;
}else{
wt(tree.right,num);
}
}else{
tree.right={
value:num,
left:null,
right:null
};
return;
}
}
}
};
var getNewTree=function(tree,num){
cloneTree=cloneObject(tree);
wt(cloneTree,num);
return cloneTree;
};
return getNewTree;
})();
3）示例
var tt=writeTree(tree,9);
alert( readTree(tt,"f") );
上面的会弹出：
10,9,6,3,4,8,7,15,14,20
--------------------------割--------------------------------
当然，大家也可以自己把代码copy回去，自己测试下
前序，中序与后序。
