二叉樹(shù)的遍歷

Q：什么是二叉樹(shù)的遍歷？

A：二叉樹(shù)的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次，且僅被訪問(wèn)一次。

Q：二叉樹(shù)有幾種遍歷方法？

A：二叉樹(shù)的遍歷方法可以有很多種，如果限制了從左到右的習(xí)慣方式，那么主要分為以下四種：先序遍歷，中序遍歷，后序遍歷，層序遍歷。

前序遍歷

Q：什么是先序遍歷

A：先序遍歷就是先訪問(wèn)樹(shù)的根節(jié)點(diǎn)，再訪問(wèn)樹(shù)的左子節(jié)點(diǎn)，再訪問(wèn)右子節(jié)點(diǎn)。可以想象為，從一棵二叉樹(shù)根節(jié)點(diǎn)為起點(diǎn)，沿著二叉樹(shù)外沿，逆時(shí)針走一圈回到根節(jié)點(diǎn)，路上遇到的元素順序，就是先序遍歷的結(jié)果。

如圖：遍歷的順序?yàn)?ABDGHCEIF

操作定義

若二叉樹(shù)為空，則空操作返回，否則：

• 訪問(wèn)根節(jié)點(diǎn)
• 先序遍歷左子樹(shù)
• 先序遍歷右子樹(shù)

代碼演示

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

中序遍歷

Q：什么是中序遍歷

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

如圖：遍歷的順序?yàn)镚DHBAECF

操作定義

若二叉樹(shù)為空，則空操作返回，否則：

• 中序遍歷左子樹(shù)
• 訪問(wèn)根節(jié)點(diǎn)
• 中序遍歷右子樹(shù)

代碼演示

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

后序遍歷

Q：什么后序遍歷

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

如圖：遍歷的順序?yàn)镚HDBIEFCA

操作定義

若二叉樹(shù)為空，則空操作返回，否則：

• 后序遍歷左子樹(shù)
• 后序遍歷右子樹(shù)
• 訪問(wèn)根節(jié)點(diǎn)

代碼演示

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

層序遍歷

Q：什么層序遍歷

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

如圖：遍歷的順序?yàn)锳BCDEFGHL

代碼演示

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

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

最新評(píng)論