数据结构中，二叉树的使用频率非常高，这得益于二叉树优秀的性能。
二叉树是非线性的数据结构，用以存储带有层级的数据，其用于查找的删除的性能非常高。
二叉树 数据结构的实现方法如下：
function Node (data, left, right) { ???this.data = data; ???this.left = left; ???this.right = right; ???this.show = function () { ???????return this.data; ???};}function BST () { ???this.root = null; ???this.insert = function (data) { ???????var node = new Node(data, null, null); ???????if (this.root === null) { ???????????this.root = node; ???????} else { ???????????var current = this.root; ???????????var parent; ???????????while (true) { ???????????????parent = current; ???????????????if (data < current.data) { ???????????????????current = current.left; ???????????????????if (current === null) { ???????????????????????parent.left = node; ???????????????????????break; ???????????????????} ???????????????} else { ???????????????????current = current.right; ???????????????????if(current === null) { ???????????????????????parent.right = node; ???????????????????????break; ???????????????????} ???????????????} ???????????} ???????} ???}; ???// 中序遍历 ???this.inOrder = function (node) { ???????if (node !== null) { ???????????this.inOrder(node.left); ???????????console.log(node.show()); ???????????this.inOrder(node.right); ???????} ???}; ???// 先序遍历 ???this.preOrder = function (node) { ???????if (node !== null) { ???????????console.log(node.show()); ???????????this.preOrder(node.left); ???????????this.preOrder(node.right); ???????} ???}; ???// 后序遍历 ???this.afterOrder = function (node) { ???????if (node !== null) { ???????????this.afterOrder(node.left); ???????????this.afterOrder(node.right); ???????????console.log(node.show()); ???????} ???}; ???this.getMin = function () { ???????var current = this.root; ???????while (current.left !== null) { ???????????current = current.left; ???????} ???????return current.data; ???}; ???this.getMax = function () { ???????var current = this.root; ???????while (current.right !== null) { ???????????current = current.right; ???????} ???????return current.data; ???}; ???this.find = function (data) { ???????var current = this.root; ???????while (current !== null) { ???????????if (data < current.data) { ???????????????current = current.left; ???????????} else if (data > current.data) { ???????????????current = current.right; ???????????} else { ???????????????return current; ???????????} ???????} ???????return null; ???}; ???????this.remove = function (data) { ???????this.root = this._removeNode(this.root, data); //将根节点转换 ???}; ???this._getSmallest = function (node) { ???????while(node.left!=null){ ???????????node=node.left; ???????} ???????return node; ???}; ???this._removeNode = function (node, data) { ???????if (node === null) { ???????????return null; ???????} ???????if (data === node.data) { ???????????// 如果没有子节点 ???????????if (node.right === null && node.left === null) { ???????????????return null; ???????????} ???????????// 如果没有左子节点 ???????????if (node.left === null) { ???????????????return node.right;//直接指向其右节点 ???????????} ???????????// 如果没有右子节点 ???????????if (node.right === null) { ???????????????return node.left; ???????????} ???????????// 如果有两个节点 ???????????if (node.right !== null && node.left !== null) { ???????????????var tempNode = this._getSmallest(node.right); ??// 找到最小的右节点 ???????????????node.data = tempNode.data; ???????????????node.right = this._removeNode(node.right, tempNode.data); ???// 依次寻找 ???????????????return node; ???????????} ???????} else if (data < node.data){ ???????????node.left = this._removeNode(node.left, data); ???????????return node; ???????} else { ???????????node.right = this._removeNode(node.right, data); ???????????return node; ???????} ???};}二叉树 数据结构的使用方法如下：
var bst = new BST ();bst.insert(40);bst.insert(20);bst.insert(70);bst.insert(60);bst.insert(75);bst.insert(71);bst.insert(73);bst.inOrder(bst.root);bst.remove(70);console.log("----------------");bst.inOrder(bst.root);console.log("----------------");console.log(bst.find(73))js数据结构之二叉树的详细实现方法
原文地址：https://www.cnblogs.com/pomelott/p/9478279.html