javascript实现二叉树

[coxo]

非递归算法 One crowded hour of glorious life is worth an age without a name. :8ball:

[bluesrocker]

function myNode(key, parent, leftChild, rightChild){
    //只会写左节点比父节点小的这种树，很大部分是抄书的
    this.rootNode = null;
    this.data = key;
    this.parent = parent;
    this.leftChild = leftChild; //左子节点较父节点小
    this.rightChild = rightChild; //右子节点较父节点大
    this.show = function(){
        return this.data;
    };
}
function myBST(){
    this.root = null;
    this.appendByData = function(data){
        var n = new myNode(data, null, null, null);
        if(this.root===null){
            this.root = n;
        }
        else{
            var current = this.root;
            var parent;
            while(true){
                parent = current;
                if(data<current.data){
                    current = current.leftChild;
                    if(current === null){
                        parent.leftChild = n;
                        n.rootNode = this.root;
                        n.parent = parent;
                        break;
                    }
                }
                else if(data>current.data){
                    current = current.rightChild;
                    if(current === null){
                        parent.rightChild = n;
                        n.rootNode = this.root;
                        n.parent = parent;
                        break;
                    }
                }
                else if(data===current.data){
                    throw new Error('there is a node whose property data is equal to' + data);
                    break;
                }
            }
        }
    };
    this.getNodeByData = function(data){ //根据属性data查找node
        var current = this.root;
        while(current !==null ){
            if(current.data === data){
                return current;
            }
            else if(data<current.data){
                current = current.leftChild;
            }
            else{
                current = current.rightChild;
            }
        }
        return null;
    };
    this.isNodeByData = function(data){ //根据属性data判断Node是否存在
        var current = this.root;
        while(current !== null){
            if(current.data === data){
                return true;
            }
            else if(data<current.data){
                current = current.leftChild;
            }
            else{
                current = current.rightChild;
            }           
        }
        return false;
    };
    this.inOrder = function(node){
        var arr = [];
        if(node instanceof myNode && this.isNodeByData(node.data)){
            (function order(node){
                if(!(node===null)){
                    order(node.leftChild);
                    arr.push(node.data);
                    order(node.rightChild);
                }           
            }(node));
        }
        return arr;
    };
    this.preOrder = function(node){
        var arr = [];
        if(node instanceof myNode && this.isNodeByData(node.data)){
            (function order(node){
                if(!(node===null)){
                    arr.push(node.data);
                    order(node.leftChild);
                    order(node.rightChild);
                }           
            }(node));
        }
        return arr;
    };
    this.postOrder = function(node){
        var arr = [];
        if(node instanceof myNode && this.isNodeByData(node.data)){
            (function inOrder(node){
                if(!(node===null)){
                    order(node.leftChild);
                    order(node.rightChild);
                    arr.push(node.data);
                }           
            }(node));
        }
        return arr;
    };
    this.getNodeMin = function(node){
        var current = node || this.root;
        while(!(current.leftChild===null)){
            current = current.leftChild;
        }
        return current;
    };
    this.getNodeMax = function(node){
        var current = node || this.root;
        while(!(current.rightChild===null)){
            current = current.rightChild;
        }
        return current;
    };
    this.removeNode =   function(node){
        var removedNode = null;
        if(node.leftChild===null){
            removedNode = translate(this, node, node.rightChild);
        }
        else if(node.rightChild===null){
            removedNode = translate(this, node, node.leftChild);
        }
        else{
            var y = this.getNodeMin(node.rightChild);
            if(y.parent!==node){
                translate(this, y, y.rightChild);
                y.rightChild = node.rightChild;
                y.rightChild.parent = y;
            }
            removedNode = translate(this, node, y);
            y.leftChild = node.leftChild;
            y.leftChild = y;
        }
        removedNode.rootNode = null;
        removedNode.parent = null;
        removedNode.leftChild = null;
        removedNode.rightChild = null;
        return removedNode;
    };
    function translate(T, u, v){
        if(u.parent===null){
            T.root = v;
        }
        else if(u===u.parent.leftChild){
            u.parent.leftChild = v;
        }
        else if(u===u.parent.rightChild){
            u.parent.rightChild = v;
        }
        if(v!==null){
            v.parent = u.parent;
        }
        return u;
    }    
}

[VaJoy]

北川你自己挖的坑还不快点来填:smirk:

[coxo]

二叉排序树基本上算法都是固定的，大体瞅了一眼逻辑上没啥问题，就是这个JS命名或者用法上有点不太好，比如，话说你为啥都把方法写构造函数里

[LeoHuiyi]

/**
 * 网上扒来的  - -！
 */
function Node(element, left, right) {
    this.element = element;
    this.level = 0;
    this.left = left;
    this.right = right;
}

function BST() {
    this.root = null;
}

BST.prototype = {
    insert: function(element) {
        var n = new Node(element, null, null);
        if (this.root == null) {
            this.root = n;
            n.level = 0;
            return true;
        } else {
            var current = this.root;
            var parent = null;
            while (current != null) {
                if (element < current.element) {
                    parent = current;
                    current = current.left;
                } else if (element > current.element) {
                    parent = current;
                    current = current.right;
                } else {
                    return false;
                }
            }
            n.level = parent.level + 1;
            if (element < parent.element) {
                parent.left = n;

            } else {
                parent.right = n;
            }
            return true;
        }
    },
    toString: function() {
        return this.inOrder(this.root, function(n) {
            return "\t" + n.element + '(' + n.level + ")\t";
        });
    },
    inOrder: function(n, fn) { // 中序遍历
        if (!n) {
            return '';
        } else {
            return this.inOrder(n.left, fn) + fn(n) + this.inOrder(n.right, fn);
        }
    },
    preOrder: function(n, fn) { // 先序遍历
        if (!n) {
            return '';
        } else {
            return fn(n) + this.preOrder(n.left, fn) + this.preOrder(n.right, fn);
        }
    },
    postOrder: function(n, fn) { // 后序遍历
        if (!n) {
            return '';
        } else {
            return this.postOrder(n.left, fn) + this.postOrder(n.right, fn) + fn(n);
        }
    }
};

var a = new BST();
a.insert(3);
a.insert(1);
a.insert(5);
a.insert(2);
a.insert(4);
console.log("inorder: " + a.toString());

var fn = function(n) {
    return "\t" + n.element + '(' + n.level + ")\t";
};
var s1 = a.preOrder(a.root, fn);
var s2 = a.postOrder(a.root, fn);
console.log("pre order:" + s1);
console.log("post order:" + s2);

[horsefefe]

define(function(require, exports){
    function traverseTree(x,func,context){
        if(x!=null){
            traverseTree(x.left,func,context);
            func.call(context||null,x.key);
            traverseTree(x.right,func,context);
        }
    }
    function binarytree(){
        this.root=null;
    }
    var prop=binarytree.prototype;
    prop.traverseTree=function(func,context){
        traverseTree.call(this,this.root,func,context);
    }
    prop.treeMin=function(x){
        if(!x){
            x=this.root;
        }
        while(x.left!=null){
            x=x.left;
        }
        return x;
    }
    prop.treeMax=function(x){
        if(!x){
            x=this.root;
        }
        while(x.right!=null){
            x=x.right;
        }
        return x;
    }
    prop.treeSuccessor=function(x){
        if(x.right!=null){
            return this.treeMin(x.right);
        }
        var y=x.parent;
        while(y!=null&&x==y.right){
            x=y;
            y=y.parent;
        }
        return y;
    }
    prop.treePredecessor=function(x){
        if(x.left!=null){
            return this.treeMax(x.left);
        }
        var y=x.parent;
        while(y!=null&&x==y.left){
            x=y;
            y=y.parent;
        }
        return y;
    }
    prop.treeSearch=function(x,key){
        if(typeof x!='object'){
            key=x;
            x=this.root;
        }
        if(key==x.key){
            return x;
        }
        if(x.key<key){
            return this.treeSearch(x.right,key);
        }else{
            return this.treeSearch(x.left,key);
        }
    }
    prop.treeInsert=function(z){
        if(typeof z!='object'){
            var z={
                key:z
            }
        }
        z.left=null;
        z.right=null;
        z.parent=null;
        y=null;
        x=this.root;
        while(x!=null){
            y=x;
            if(z.key<x.key){
                x=x.left;
            }else{
                x=x.right;
            }
        }
        z.parent=y;
        if(y==null){
            this.root=z;
        }else{
            if(z.key<y.key){
                y.left=z;
            }else{
                y.right=z;
            }
        }
    }
    prop.treeDelKey=function(key){
        var tempObj=this.treeSearch(key);
        return this.treeDel(tempObj);
    }
    prop.treeDel=function(z){
        if(z.left==null||z.right==null){
            y=z;
        }else{
            y=this.treeSuccessor(z);
        }
        if(y.left!=null){
            x=y.left;
        }else{
            x=y.right;
        }
        if(x!=null){
            x.parent=y.parent;
        }
        if(y.parent==null){
            this.root=x;
        }else if(y==y.parent.left){
            y.parent.left=x;
        }else{
            y.parent.right=x;
        }
        if(y!=z){
            z.key=y.key;
        }
        return y;
    }
    return binarytree;
});