去年照着严蔚敏的《数据结构》写了这个脚本，用JavaScript实现了栈、队列、链表、树和二叉树。后来在工作中没发现能派上什么用场，丢在一边很久也没理会。今天偶然翻了一下觉得有些写得还挺有意思的。

例如求树的所有叶子节点数。

递归解法：
getLeafCount:function(){
    var _count = 0;
    for(var i in this.children){
        if(this.children[i].hasChild()) 
            _count += this.children[i].getLeafCount();
        else 
            _count++;
    }
    return _count;
}
使用堆栈的非递归解法：
getLeafCount:function()
{
    var _stack = new BX.DataStructure.Stack();
    var _tree = this;
    var _count = 0;
    while(_tree != null)
    {
        for(var i = 0; i < _tree.children.length; i++)
            {
                if(_tree.children[i].hasChild()) 
                    _stack.push(_tree.children[i]);
                else 
                    _count++;
            }
        _tree = _stack.pop();
    }
    return _count;
}
使用队列的非递归解法：
getLeafCount:function()
{
    var _queue = new BX.DataStructure.Queue();
    var _tree = this;
    var _count = 0;
    while(_tree != null)
    {
        for(var i = 0; i < _tree.children.length; i++)
        {
            if(_tree.children[i].hasChild()) 
                _queue.enQueue(_tree.children[i]);
            else 
                _count++;
        }
        _tree = _queue.deQueue();
    }
    return _count;
}

又如求二叉树同一深度的所有子节点。

广度优先(Queue实现)
getChildrenByDepth:function(depth)
{
    if(depth < 1) return null;
    if(depth == 1) return new Array(this);
    var _queue = new BX.DataStructure.Queue();
    //同一层元素的个数队列，对头为同一层元素的个数
    var _depthQueue = new BX.DataStructure.Queue();
    var _children = [];
    var _treeNode = null;
    var _depth = 1;
    var _count = 0;
    _queue.enQueue(this);
    while(!_queue.isEmpty())
    {
        if(_depth == depth) { _children = _queue.elements; break;}
        else
        {
            _depthQueue.enQueue(_queue.getLength());
            _treeNode = _queue.deQueue();
            if(_treeNode.hasLeftChild()) _queue.enQueue(_treeNode.leftChild);
            if(_treeNode.hasRightChild()) _queue.enQueue(_treeNode.rightChild);
            _count++;
            //当计数等于同一层元素个数的时候，_depthQueue置0，下一次循环时推入下一层的个数
            if(_count == _depthQueue.getHead())
            {
                _depth++;
                _count = 0;
                _depthQueue.clear();
            }
        }
    }
    return _children;
}

深度优先(Stack实现)
getChildrenByDepth:function(depth)
{
    if(depth < 1) return null;
    if(depth == 1) return new Array(this);
    var _stack = new BX.DataStructure.Stack();
    var _depthStack = new BX.DataStructure.Stack();
    var _children = [];
    var _treeNode = null;
    var _currentDepth = 1;
    var isMatched = false;
    _stack.push(this);
    _depthStack.push(_currentDepth);
    while(!_stack.isEmpty())
    {
        //元素和该元素相应的深度同时出栈
        _treeNode = _stack.pop();
        _currentDepth = _depthStack.pop();

        if(_treeNode.hasLeftChild() || _treeNode.hasRightChild()) 
            _currentDepth++;
        //判断是否到达所求深度，如果是则添加到_children数组，否则当前深度和子元素都入栈
        isMatched = _currentDepth == depth ? true : false;
        if(_treeNode.hasLeftChild())
        {
            if(isMatched) _children.push(_treeNode.leftChild);
            else
            {
                _stack.push(_treeNode.leftChild);
                _depthStack.push(_currentDepth);
            }
        }
        if(_treeNode.hasRightChild())
        {
            if(isMatched) _children.push(_treeNode.rightChild);
            else
            {
                _stack.push(_treeNode.rightChild);
                _depthStack.push(_currentDepth);
            }
        }
    }
    return _children;
}