潘魏增

去年照着严蔚敏的《数据结构》写了这个脚本，用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;
}

脚本在线地址：http://panweizeng.com/others/DataStructure.js