给定一棵二叉查找树，设计算法，将每一层的全部结点构建为一个

链表(也就是说， 假设树有D层，那么你将构建出D个链表).

这个题实质是个BFS，可是实现起来有点麻烦，又不像常见的BFS，

所以编写代码时有点艰难。

以下的代码使用两个list来实现层次遍历的，首先用Cur链表存储当前层

的结点，然后用Pre链表存储当前层的子层结点，Cur和Pre。下一次遍历时

Pre就变成当前层，Cur就变成它的子层。这样交替运行。

代码：

struct TreeNode

{

	int   data;

	TreeNode* leftChild;

	TreeNode* rightChild;

};

void createLinks(const TreeNode* vRoot, std::vector<std::list<TreeNode*>>& vListVec)

{

	if (vRoot == NULL) return;

	vListVec.clear();

	std::list<TreeNode*> Pre;

	std::list<TreeNode*> Cur;

	std::list<TreeNode*>* pList;

	Cur.push_back(vRoot);

	vListVec.push_back(Cur);

	pList = &Cur;

	bool IsCur = true;

	while (pList->empty())

	{

		if (IsCur)

		{

			while (pList->empty())

			{

				TreeNode* Tmp = pList->front();

				pList->pop_front();

				if (Tmp->leftChild)  Pre.push_back(Tmp->leftChild);

				if (Tmp->rightChild) Pre.push_back(Tmp->rightChild);

			}

			IsCur = false;

			pList = &Pre;

			vListVec.push_back(Pre);

		}

		else

		{

			while (pList->empty())

			{

				TreeNode* Tmp = pList->front();

				pList->pop_front();

				if (Tmp->leftChild)  Cur.push_back(Tmp->leftChild);

				if (Tmp->rightChild) Cur.push_back(Tmp->rightChild);

			}

			IsCur = true;

			pList = Cur;

			vListVec.push_back(Cur);

		}

	}

}

给定一个有向图，设计算法推断两结点间是否存在路径。

常见的BFS。

代码：

struct GraphNode

{

	int data;

	GraphNode* next;

}

bool judge(const GraphNode* vBgn, const GraphNode* vEnd)

{

	if (vBgn == NULL || vEnd == NULL) return false;

	std::map<GraphNode*, bool> MapV;

	std::queue<GraphNode*> Que;

	Que.push(vBgn);

	MapV[vBgn] = true;

	while (!Que.empty())

	{

		GraphNode* Tmp = Que.front();

		Que.pop();

		while (Tmp->next)

		{

			Tmp = Tmp->next;

			if (MapV.find(Tmp) != MapV.end())

			{

				if (Tmp == vEnd) return true;

				MapV[Tmp] = true;

				Que.push(Tmp);

			}

		}

	}

	return false;

}