本文实例讲述了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程序设计有所帮助。