數據結構之二叉樹的深度優先遍歷

數據結構之二叉樹的深度優先遍歷

可以將二叉樹的遍歷方式分為兩類：

一：深度

先序遍歷

中序編列

後序遍歷

二、廣度（也就是從左往右）

層序遍歷

下面是深度的三種遍歷方式：

#include

using namespace std;


typedef struct BitNode{
	char data;
	struct  BitNode *lchild, *rchild;
}BitNode,*BiTree;

void CreateBiTree(BiTree &T);
void PreOrderTraverse(BiTree T);
void InOrderTraverse(BiTree T);
void PostOrderTraverse(BiTree T);



void CreateBiTree(BiTree &T)
{
	
	//創建二叉樹時使用完整的字符串序列表示,
	//示例:ab##c##

	char ch;
	scanf("%c",&ch);
	if (ch == '#')	T = NULL;//   空樹
	else
	{
		T = new BitNode;
		if (T)
		{
			T->data = ch;
			CreateBiTree(T->lchild);
			CreateBiTree(T->rchild);
		}
	}
}


//先序遍歷二叉樹
void PreOrderTraverse(BiTree T)
{
	if (T != NULL)
	{
		cout << T->data << endl;
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}

//中序遍歷二叉樹
void InOrderTraverse(BiTree T)
{
	if (T != NULL)
	{
		InOrderTraverse(T->lchild);
		cout << T->data << endl;
		InOrderTraverse(T->rchild);
	}
}


//後序遍歷二叉樹
void PostOrderTraverse(BiTree T)
{
	if (T != NULL)
	{
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		cout<< T->data << endl;
	}
}




int main()
{
	BiTree T;
	CreateBiTree(T);
	cout << "二叉樹已經生成，開始先序遍歷：" << endl;
	PreOrderTraverse(T);
	cout << "開始中序遍歷：" << endl;
	InOrderTraverse(T);
	cout << "開始後序遍歷：" << endl;
	PostOrderTraverse(T);
	return 0;
}