js实现二叉树
1. 掌握的知识
二叉树中对循环 while 和 递归使用的比较多,例如查找节点
serch(key
){
if(this.root
== null)return false;
let current
= this.root
;
while(current
.key
!= key
){
if(key
< current
.key
){
current
= current
.left
;
}else{
current
= current
.right
;
}
}
return current
;
}
二叉树的遍历二叉树的查找二叉树的插入
2. 二叉搜索树实现代码
class BST {
constructor() {
this.root
= null;
}
createNode({key
, val
}) {
return {
left
: null,
key
,
val
,
right
: null,
};
}
insert(data
){
let node
= this.createNode(data
);
if(this.root
== null){
this.root
= node
;
return;
}
this.insertNode(this.root
,node
);
}
insertNode(pNode
,newNode
){
if(pNode
.key
> newNode
.key
){
if(pNode
.left
== null){
pNode
.left
= newNode
;
}else{
this.insertNode(pNode
.left
,newNode
);
}
}else{
if(pNode
.right
== null){
pNode
.right
= newNode
;
}else{
this.insertNode(pNode
.right
,newNode
);
}
}
}
preOrderTraverse(cb
){
if(this.root
== null)return;
this.preOrderTraverseNode(this.root
,cb
);
}
preOrderTraverseNode(node
,cb
){
if(node
!= null){
cb(node
);
this.preOrderTraverseNode(node
.left
,cb
);
this.preOrderTraverseNode(node
.right
,cb
);
}
}
inOrderTraverse(){
if(this.root
== null)return;
this.inOrderTraverseNode();
}
inOrderTraverseNode(node
=this.root
){
if(node
!= null){
this.inOrderTraverseNode(this.left
);
console
.log(node
);
this.inOrderTraverseNode(this.right
);
}
}
postOrderTraverse(){
if(this.root
== null)return;
this.postOrderTraverseNode();
}
postOrderTraverseNode(node
=this.root
){
if(node
!= null){
this.postOrderTraverseNode(this.left
);
this.postOrderTraverseNode(this.right
);
console
.log(node
);
}
}
max(){
if(this.root
==null)return null;
return this.getMaxNode(this.root
);
}
getMaxNode(node
){
if( node
.right
== null ){
return node
;
}else{
return this.getMaxNode(node
.right
);
}
}
min(){
if(this.root
== null)return null;
let current
= this.root
;
while(current
.left
!= null){
current
= current
.left
;
}
return current
;
}
serch(key
){
if(this.root
== null)return false;
let current
= this.root
;
while(current
.key
!= key
){
if(key
< current
.key
){
current
= current
.left
;
}else{
current
= current
.right
;
}
}
return current
;
}
}
let bst
= new BST();
bst
.insert({key
:11,val
:3});
bst
.insert({key
:15,val
:333});
bst
.insert({key
:7,val
:3});
bst
.insert({key
:5,val
:3});
bst
.insert({key
:3,val
:3});
bst
.insert({key
:333,val
:311111});
bst
.insert({key
:9,val
:3});
bst
.insert({key
:8,val
:3});
bst
.insert({key
:1,val
:555});
console
.log(bst
.serch(5));
3.二叉树的缺点
如果插入的数字是连续的,会导致二叉树变成非平衡二叉树,严重影响性能
可以使用红黑树来解决这个问题