JavaScript数据结构与算法之二叉树添加/删除节点操作示例
程序员文章站
2022-07-04 21:51:16
本文实例讲述了javascript数据结构与算法之二叉树添加/删除节点操作。分享给大家供大家参考,具体如下:
function node(data,left,ri...
本文实例讲述了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);
运行结果:
感兴趣的朋友可以使用在线html/css/javascript代码运行工具:http://tools.jb51.net/code/htmljsrun测试上述代码运行效果。
更多关于javascript相关内容感兴趣的读者可查看本站专题:《javascript数学运算用法总结》、《javascript数据结构与算法技巧总结》、《javascript数组操作技巧总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结》
希望本文所述对大家javascript程序设计有所帮助。
下一篇: 麻圆是哪里特产?麻圆的由来是什么?