void PreOrderTraversal(BiTree BT)
{
    if( BT ！= NULL ) 
    {
        printf(“%d\n”, BT->Data);        //對節(jié)點的數(shù)據(jù)進(jìn)行打印          
        PreOrderTraversal(BT->Left);     //訪問左子樹
        PreOrderTraversal(BT->Right);    //訪問右子樹
    }
}

中序遍歷

Q：什么是中序遍歷

A：中序遍歷就是訪問完所有左子數(shù)后再訪問根節(jié)點，最后訪問右子樹，即左子樹-根節(jié)點-右子樹。中序遍歷可以看成，二叉樹每個節(jié)點，垂直方向投影下來，然后從左往右數(shù)，得出的結(jié)果便是中序遍歷的結(jié)果。

如圖：遍歷的順序為GDHBAECF

操作定義

若二叉樹為空，則空操作返回，否則：

中序遍歷左子樹
訪問根節(jié)點
中序遍歷右子樹

代碼演示

void InOrderTraversal(BiTree BT)
{
    if(BT)
    {
        InOrderTraversal(BT->Left);
        printf("%d\n", BT->Data);
        InOrderTraversal(BT->Right);
    }
}

后序遍歷

Q：什么后序遍歷

A：后序遍歷就是先訪問左子樹和右子樹，最后訪問節(jié)點，即左子樹-右子樹-根節(jié)點。后序遍歷可以看成圍著樹的外圍繞一圈，若下面只有一個結(jié)點就摘下來，得出的結(jié)果便是后序遍歷的結(jié)果。

如圖：遍歷的順序為GHDBIEFCA

操作定義

若二叉樹為空，則空操作返回，否則：

后序遍歷左子樹
后序遍歷右子樹
訪問根節(jié)點

代碼演示

void PostOrderTraversal(BiTree BT)
{
    if (BT)
    {
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        printf("%d\n", BT->Data);
    }
}

層序遍歷

Q：什么層序遍歷

A：層次遍歷就是從根節(jié)點開始，一層一層，從上到下，每層從左到右，依次取值。

如圖：遍歷的順序為ABCDEFGHL

代碼演示

void LevelOrder(BiTree T){
	InitQueue(Q);				//初始化輔助隊列
	BiTree p;
	EnQueue(Q,T);				//將根結(jié)點入隊
	while(!IsEmpty(Q))
	{							//隊列不空則循環(huán)
		DeQueue(Q,p);			//隊頭結(jié)點出隊
		visit(p);				//訪問出隊結(jié)點
		if(p->1child!=NULL)
			EnQueue(Q,p->lchild);//左子樹不空，則左子樹根結(jié)點入隊
		if(p->rchild!=NULL)
			EnQueue(Q,p->rchild);//右子樹不空，則右子樹根結(jié)點入隊
	}
}

到此這篇關(guān)于C++超詳細(xì)實現(xiàn)二叉樹的遍歷的文章就介紹到這了,更多相關(guān)C++二叉樹遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: