二叉搜索树的构建

文章来源https://www.nczonline.net/blog/2009/06/09/computer-science-in-javascript-binary-search-tree-part-1/

基本界面

function BinarySearchTree() { this._root = null; } BinarySearchTree.prototype = //restore constructor constructor: BinarySearchTree, add: function (value){ }, contains: function(value){ }, remove: function(value){ }, size: function(){ }, toArray: function(){ }, toString: function(){ } };//这里size,toArray,toString是文章作者添加的新函数

contians

BinarySearchTree.prototype = { //more code contains: function(value){ var found = false, current = this._root //make sure there's a node to search while(!found && current){ //if the value is less than the current node's, go left if (value < current.value){ current = current.left; //if the value is greater than the current node's, go right } else if (value > current.value){ current = current.right; //values are equal, found it! } else { found = true; } } //only proceed if the node was found return found; }, //more code };

add

`BinarySearchTree.prototype = {
//more code
add: function(value){
//create a new item object, place data in
var node = {
value: value,

            left: null,
            right: null
        },
        //used to traverse the structure
        current;
    //special case: no items in the tree yet
    if (this._root === null){
        this._root = node;
    } else {
        current = this._root;
        while(true){
            //if the new value is less than this node's value, go left
            if (value < current.value){
                //if there's no left, then the new node belongs there
                if (current.left === null){
                    current.left = node;
                    break;
                } else {
                    current = current.left;
                }
            //if the new value is greater than this node's value, go right
            } else if (value > current.value){
                //if there's no right, then the new node belongs there
                if (current.right === null){
                    current.right = node;
                    break;
                } else {
                    current = current.right;
                }       
            //if the new value is equal to the current one, just ignore
            } else {
                break;
            }
        }
    }
},
//more code

};`

traverse遍历递归

BinarySearchTree.prototype = { //more code traverse: function(process){ //helper function function inOrder(node){ if (node){ //traverse the left subtree if (node.left !== null){ inOrder(node.left); } //call the process method on this node process.call(this, node); //traverse the right subtree if (node.right !== null){ inOrder(node.right); } } } //start with the root inOrder(this._root); }, //more code };

size/toArray/toString

BinarySearchTree.prototype = { //more code size: function(){ var length = 0; this.traverse(function(node){ length++; }); return length; }, toArray: function(){ var result = []; this.traverse(function(node){ result.push(node.value); }); return result; }, toString: function(){ return this.toArray().toString(); }, //more code };

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,776评论 0 33
  • 花了半天的时间,把史蒂芬.柯维的《高效能人士的7个习惯》的前三章啃了下来。不愧是经典,字字珠玑。对于我这个困境中的...
    安宁姑娘阅读 243评论 0 2
  • 你们的确
    25151ee6d9c9阅读 178评论 0 1
  • 父亲离开我们已十年有余了。 父亲在世时,我与父亲的感情一般,主要是他在我心里“形象”不太好。母亲由于长年有病,家中...
    飞翔的狐阅读 269评论 1 2