XIAOSUO 记录个人学习的足迹

　　设树T如下图所示，结点R是根，根的子树从左到右依次为T1，T2，…，Tk。

　　　　
一、树的前序遍历
　　若树T非空，则：
　　　　①访问根结点R；
　　　　②依次前序遍历根R的各子树T1，T2，…，Tk。
　　先序遍历树结点算法实现如下：

//先序遍历树结点
public void PreOrder(MLNode<T> root)
{

	if (root == null)
	{
		return;
	}
	//访问根结点
	Console.Write(root.Data + "  ");
	//按先序访问子树结点 
	for (int i = 0; i < root.Childs.Length; i++)
	{
	   
		 PreOrder(root.Childs[i]);
	   
	}
	
}

二、树的后序遍历
　　若树T非空，则：
　　　　①依次后序遍历根T的各子树Tl，T2，…，Tk；
　　　　②访问根结点R。
　　后序遍历树结点算法实现如下：

//后序遍历树结点
public void PostOrder(MLNode<T> root) 
{
   
	if (root == null)
	{              
		return;
	}
	//按先序访问子树结点 
	for (int i = 0; i < root.Childs.Length; i++)
	{
		if (root.Childs[i] != null)
		{
			PostOrder(root.Childs[i]);
		}
	}
	//访问根结点
	Console.Write(root.Data + "  ");
}

三、树的层序遍历

　　按照树的结构从上到下、从左到右的顺序访问树的结点。
　　层序遍历树结点算法实现如下：

//层序遍历
public void BroadOrder(MLNode<T> root)
{
	Console.WriteLine("遍历开始:");
	if (root == null)
	{
		Console.WriteLine("没有结点！");
		return;
	}

	MLNode<T> tmp = root;

	Queue que = new Queue();
	//根结点入队列
	que.Enqueue(tmp);
	while (que.Count > 0)
	{
		//结点出队列并访问
		tmp = (MLNode<T>)que.Dequeue();
		
		Console.Write(tmp.Data + "  ");
		for (int i = 0; i < tmp.Childs.Length; i++)
		{
			if (tmp.Childs[i] != null)
			{
				//各个子结点入队列
				que.Enqueue(tmp.Childs[i]);
			}
		}
	}
	Console.WriteLine("遍历结束.");
}

对下面的(a)图中的树进行前序遍历、后序遍历和层序遍历，得到的前序序列、后序序列和层序序列分别是ABCDE、BDCEA和ABCED。
　　　　
　　注意：
　① 前序遍历一棵树恰好等价于前序遍历该树对应的二叉树。
　② 后序遍历树恰好等价于中序遍历该树对应的二叉树。
　③ 层序遍历树恰好等价于后序遍历该树对应的二叉树。

四、森林的遍历

1．前序遍历森林
　　若森林非空，则：
　　　　①访问森林中第一棵树的根结点；
　　　　②前序遍历第一棵树中根结点的各子树所构成的森林
　　　　③前序遍历除第一棵树外其它树构成的森林。

2．后序遍历森林
　　若森林非空，则:
　　　　①后序遍历森林中第一棵树的根结点的各子树所构成的森林；
　　　　②访问第一棵树的根结点；
　　　　③后序遍历除第一棵树外其它树构成的森林。
注意：
　　① 前序遍历森林等同于前序遍历该森林对应的二叉树
　　② 后序遍历森林等同于中序遍历该森林对应的二叉树
对下面(a)图中所示的森林进行前序遍历和后序遍历，则得到该森林的前序序列和后序序列分别为ABCDEFICJH和BDCAIFJGHE。而(b)图所示二叉树的前序序列和中序序列也分别为ABCDEFICJH和BDCAIFJGHE。
　　　　
　　　　
　　③ 当用二叉链表作树和森林的存储结构时，树和森林的前序遍历和后遍历，可用二叉树的前序遍历和中序遍历算法来实现。