二叉樹的前序、中序、後續、層序周遊

二叉樹的基本概念

每個結點最多有兩棵子樹，左子樹和右子樹，次序不可以颠倒。

性質：

1、非空二叉樹的第n層上至多有2^(n-1)個元素。

2、深度為h的二叉樹至多有2^h-1個結點。

3、滿二叉樹：所有終端都在同一層次，且非終端結點的度數為2。

4、在滿二叉樹中若其深度為h，則其所包含的結點數必為2^h-1。

5、完全二叉樹：除了最大的層次即成為一顆滿二叉樹且層次最大那層所有的 結點均向左靠齊，即集中在左面的位置上，不能有空位置。

對于完全二叉樹，設一個結點為i則其父節點為i/2，2i為左子節點，2i+1為右子節點。

前序周遊：中-左-右

void PreTraverTree(NodeBinaryTree *ps)//前序周遊
{
	if (ps != NULL)//當二叉樹不為空時周遊
	{
		cout<<ps->data<<' ';
		if (ps->Left != NULL) PreTraverTree(ps->Left);
		if (ps->Right != NULL) PreTraverTree(ps->Right);
	}
}
           

中序周遊：左-中-右

void InTraverTree(NodeBinaryTree *ps)//中序周遊
{
	if (ps != NULL)
	{
		if (ps->Left != NULL) InTraverTree(ps->Left);
		cout << ps->data << ' ';
		if (ps->Right != NULL) InTraverTree(ps->Right);
	}
}
           

後序周遊：左-右-中

void EndTraverTree(NodeBinaryTree *ps)//後序周遊
{
	if (ps != NULL)
	{
		if (ps->Left != NULL) EndTraverTree(ps->Left);
		if (ps->Right != NULL) EndTraverTree(ps->Right);
		cout << ps->data << ' ';
	}
}

           

層序周遊：由上到下，由左到右

void SequeTraverTree(NodeBinaryTree *ps)//層序周遊
{
	queue<NodeBinaryTree *> q;
	if (ps)
		q.push(ps);
	while (q.empty()==false)
	{
		NodeBinaryTree *temp = q.front();//q.front()代表隊列q的首個元素       //法一
		cout << temp->data << "->";
		q.pop();//出隊列。每執行一次，最先進去隊列的元素出隊列，下個元素随即變成q.front()代表的元素
		if (temp->Left)
		{
			q.push(temp->Left);
		}
		if (temp->Right)
		{
			q.push(temp->Right);
		}
		//cout << q.front()->data << "->";//法二
		//if (q.front()->Left)
		//{
		//	q.push(q.front()->Left);
		//}
		//if (q.front()->Right)
		//{
		//	q.push(q.front()->Right);
		//}
		//q.pop();
	}
}