function BrnarySearchTree() { //创建节点 function Node(key) { this.key = key; this.left = null; this.right = null; } //跟节点 this.root = null; //插入节点 BrnarySearchTree.prototype.insert = function (key) { var node = new Node(key); if (!this.root) { this.root = node } else { this.insertNode(this.root, node) } } //插入节点方法 BrnarySearchTree.prototype.insertNode = function (node, newNode) { if (node.key > newNode.key) { if (!node.keft) { node.left = newNode } else { this.insertNode(node.left, newNode) } } else { if (node.key < newNode.key) { if (!node.right) { node.right = newNode } else { this.insertNode(node.right, newNode) } } } } //前序遍历 BrnarySearchTree.prototype.preTree = function (node, handler) { if (node == null) { return; } handler(node.key) this.preTree(node.left, handler) this.preTree(node.right, handler) } //中序遍历 BrnarySearchTree.prototype.midTree = function (node, handler) { if (node == null) { return; } this.midTree(node.left, handler) handler(node.key) this.midTree(node.right, handler) } //后序遍历 BrnarySearchTree.prototype.aftTree = function (node, handler) { if (node == null) { return; } this.aftTree(node.left, handler) this.aftTree(node.right, handler) handler(node.key) } //寻找最大值 BrnarySearchTree.prototype.max = function () { var node = this.root; var key = null; while (node != null) { key = node.key; node = node.right; } return key } //寻找最小值 BrnarySearchTree.prototype.min = function () { var node = this.root; var key = null; while (node != null) { key = node.key; node = node.left; } return key; } //查找特定值 BrnarySearchTree.prototype.search = function (key) { var node = this.root; while (node != null) { if (key > node.key) { node = node.right; } else if (key < node.key) { node = node.left; } else { return true } } return false; } //删除节点 BrnarySearchTree.prototype.delete = function (key) { var node = this.root; var parent = this.root; var isLeftChild = true; while (node.key != key) { parent = node; if (key < node.key) { isLeftChild = true; node = node.left; } else { isLeftChild = false; node = node.rigth } if (node == null) { return false; } } } //二叉树层数 BrnarySearchTree.prototype.getNum = function (node) { if (!node) return 0; return Math.max(this.getNum(node.left), this.getNum(node.right)) + 1 } } var tree = new BrnarySearchTree(); tree.insert(5) tree.insert(6) tree.insert(1) tree.insert(7) console.log(tree.root)
原文:https://www.cnblogs.com/wangyisu/p/13141058.html