本文实例讲述了JS二叉树的简单实现方法。分享给大家供大家参考，具体如下：
今天学习了一下 二叉树的实现，在此记录一下
简单的二叉树实现，并且实现升序和降序排序输出
function Node(data , left,right){
this.data = data;
this.left = left;
this.right = right;
this.show = show;
function show(){
return this.data;
}
};
function Bst(){
this.root = null;
this.insert = insert;//插入
this.inOrder = inOrder;//中序遍历(升序)
this.inOrderDesc = inOrderDesc;//中序遍历(降序)
this.preOrder = preOrder;//先序遍历
this.postOrder = postOrder;//后续遍历
this.getMin = getMin;//最大值
this.getMax = getMax;//最小值
this.find = find;//查找值
this.remove = remove;//删除节点
this.count = count;//获取节点数量
function insert(data){
//创建一个新的节点
var newNode = new Node(data,null,null);
//判断是否存在根节点，没有将新节点存入
if(this.root == null){
this.root = newNode;
}else{
//获取根节点
var current = this.root;
var parent;
while(true){
//将当前节点保存为父节点
parent = current;
//将小的数据放在左节点
if(data < current.data){
//获取当前节点的左节点
//判断当前节点下的左节点是否有数据
current = current.left;
if(current == null){
//如果没有数据将新节点存入当前节点下的左节点
parent.left = newNode;
break;
}
}else{
current = current.right;
if(current == null){
parent.right = newNode;
break;
}
}
}
}
}
function inOrder(node){
var data = [];
_inOrder(node,data);
return data;
}
function inOrderDesc(node){
var data = [];
_inOrderDesc(node,data);
return data;
}
function preOrder(node){
var data = [];
_preOrder(node,data);
return data;
}
function postOrder(node){
var data = [];
_postOrder(node,data);
return data;
}
function _inOrder(node,data){
if(!(node == null)){
_inOrder(node.left,data);
data.push(node.show());
_inOrder(node.right,data);
}
}
function _inOrderDesc(node,data){
debugger;
if(!(node == null)){
_inOrderDesc(node.right,data);
data.push(node.show());
_inOrderDesc(node.left,data);
}
}
function _preOrder(node,data){
if(!(node == null)){
data.push(node.show());
_preOrder(node.left,data);
_preOrder(node.right,data);
}
}
function _postOrder(node,data){
if(!(node == null)){
_postOrder(node.left,data);
_postOrder(node.right,data);
data.push(node.show());
}
}
function getMin(){
var current = this.root;
while(!(current.left == null)){
current = current.left;
}
return current.data;
}
function getMax(){
var current = this.root;
while(!(current.right == null)){
current = current.right;
}
return current.data;
}
function find(data){
var current = this.root;
while(current != null){
if(data == current.data){
return current;
}else if(data < current.data){
current = current.left;
}else{
current = current.right;
}
}
return null;
}
function getSmallest(node){
var current = node;
while(!(current.left == null)){
current = current.left;
}
return current;
}
function remove(data){
root = removeNode(this.root,data);
}
function removeNode(node,data){
if(node == null){
return null;
}
if(data == node.data){
//如果没有只节点
if(node.left == null && node.right){
return null;
}
//如果没有左节点
if(node.left == null){
return node.right;
}
//如果没有右节点
if(node.right == null){
return node.left;
}
//有两节点
var tempNode = getSmallest(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;
}
}
function count(){
var counts = 0;
var current = this.root;
if(current == null){
return counts;
}
return _count(current,counts);
}
function _count(node,counts){
debugger;
if(!(node == null)){
counts ++;
counts = _count(node.left,counts);;
counts = _count(node.right,counts);
}
return counts;
}
}
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：notice#nhooo.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。