<!DOCTYPE html>
<html>
<head>
<title></title>
</head>
<body>
<script type="text/javascript">
function Node(data,left,right){
this.data = data;
this.left = left;
this.right = right;
}
function Btree(){
this.root = null;
}
Btree.prototype.inOrder = function(node){
if(node != null){
this.inOrder(node.left)
console.log(node.data)
this.inOrder(node.right)
}
}
Btree.prototype.getMin = function(root){
var current = this.root || root;
while(current.left != null){
current = current.left;
}
return current
}
Btree.prototype.getMax = function(root){
var current = this.root || root;
while(current.right != null){
current = current.right;
}
return current
}
Btree.prototype.insert = function(data){
var node = new Node(data,null,null);
if(this.root == null){
this.root = node
}else{
var current = this.root;
var parent;
while(true){
parent = current;
if(data<current.data){
current = current.left
if(current == null){
parent.left = node;
break;
}
}else{
current = current.right
if(current == null){
parent.right = node;
break;
}
}
}
}
}
Btree.prototype.find = function(data){
var current = this.root;
while(current != null){
if(data<current.data){
current = current.left
}else if(data>current.data){
current = current.right
}else{
return current
}
}
return null
}
Btree.prototype.remove = function(data){
removeNode(this.root,data)
}
function removeNode(node,data){
if(node == null){
return null
}
if(data == node.data){
if(node.left == null && node.right == null){
node = null
return null
}
if(node.left == null){
node = node.right
return node.right
}
if(node.right == null){
node = node.left
return node.left
}
var tempNode = new Btree().getMin(node.right)
node.data = tempNode.data
node.right = removeNode(node.right,tempNode.data)
return node
}else if(data<node.data){
node.left = removeNode(node.left,data)
return node
}else{
node.right = removeNode(node.right,data)
return node
}
}
var tree = new Btree();
tree.insert(5);
tree.insert(3);
tree.insert(4);
tree.insert(7);
tree.insert(6);
tree.insert(8);
tree.insert(1);
tree.insert(2);
// tree.inOrder(tree.root)
// console.log(tree.find(1))
// console.log('-----------')
tree.remove(5)
tree.inOrder(tree.root)
</script>
</body>
</html>
二叉树
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 树 在计算机科学中，树（英语：tree）是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构...
- [toc] 树 二叉树 定义 ： 每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有...
- 1. 树结构示意图 补充： 兄弟节点：具有相同父节点的节点互称为兄弟节点。 树的深度：从根节点开始（其深度为0）自...
