JS二叉树的简单实现方法示例

本文实例讲述了JS二叉树的简单实现方法。分享给大家供大家参考，具体如下：今天学习了

本文实例讲述了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;
 }
}