JavaScript二叉树添加/删除节点 JavaScript数据结构与算法之二叉树添加/删除节点操作示例
白杨-M 人气:0本文实例讲述了JavaScript数据结构与算法之二叉树添加/删除节点操作。分享给大家供大家参考,具体如下:
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.getMin = getMin; this.getMax = getMax; this.find = find; this.remove = remove; } function insert(data) { var n = new Node(data,null,null); if(this.root == null) { this.root = n; }else { var current = this.root; var parent; while(current) { parent = current; if(data < current.data) { current = current.left; if(current == null) { parent.left = n; break; } }else { current = current.right; if(current == null) { parent.right = n; break; } } } } } // 中序遍历 function inOrder(node) { if(!(node == null)) { inOrder(node.left); console.log(node.show()); inOrder(node.right); } } // 先序遍历 function preOrder(node) { if(!(node == null)) { console.log(node.show()); preOrder(node.left); preOrder(node.right); } } // 后序遍历 function postOrder(node) { if(!(node == null)) { postOrder(node.left); postOrder(node.right); console.log("后序遍历"+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(current.data == data) { return current; }else if(data < current.data) { current = current.left; }else { current = current.right; } } return null; } function remove(data) { root = removeNode(this.root,data); } function getSmallest(node) { if (node.left == null) { return node; } else { return getSmallest(node.left); } } function removeNode(node,data) { if(node == null) { return null; } if(data == node.data) { // 没有子节点的节点 if(node.left == null && node.right == null) { return null; } // 没有左子节点的节点 if(node.left == null) { return node.right; } // 没有右子节点的节点 if(node.right == null) { return node.left; } // 有2个子节点的节点 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; } } //代码初始化如下: var nums = new BST(); nums.insert(23); nums.insert(45); nums.insert(16); nums.insert(37); nums.insert(3); nums.insert(99); nums.insert(22); var min = nums.getMin(); console.log(min); var max = nums.getMax(); console.log(max); var value = nums.find("45"); console.log(value); nums.remove(23);
运行结果:
希望本文所述对大家JavaScript程序设计有所帮助。
加载全部内容