C++超詳細實現二元樹的遍歷

2022-05-25 14:01:16

二元樹的遍歷

Q：什麼是二元樹的遍歷？

A：二元樹的遍歷是指從根結點出發，按照某種次序依次存取二元樹中所有結點，使得每個結點被存取一次，且僅被存取一次。

Q：二元樹有幾種遍歷方法？

A：二元樹的遍歷方法可以有很多種，如果限制了從左到右的習慣方式，那麼主要分為以下四種：先序遍歷，中序遍歷，後序遍歷，層序遍歷。

前序遍歷

Q：什麼是先序遍歷

A：先序遍歷就是先存取樹的根節點，再存取樹的左子節點，再存取右子節點。可以想象為，從一棵二元樹根節點為起點，沿著二元樹外沿，逆時針走一圈回到根節點，路上遇到的元素順序，就是先序遍歷的結果。

如圖：遍歷的順序為 ABDGHCEIF

操作定義

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

存取根節點
先序遍歷左子樹
先序遍歷右子樹

程式碼演示

void PreOrderTraversal(BiTree BT)
{
    if( BT ！= NULL ) 
    {
        printf(「%dn」, BT->Data);        //對節點的資料進行列印          
        PreOrderTraversal(BT->Left);     //存取左子樹
        PreOrderTraversal(BT->Right);    //存取右子樹
    }
}

中序遍歷

Q：什麼是中序遍歷

A：中序遍歷就是存取完所有左子數後再存取根節點，最後存取右子樹，即左子樹-根節點-右子樹。中序遍歷可以看成，二元樹每個節點，垂直方向投影下來，然後從左往右數，得出的結果便是中序遍歷的結果。

如圖：遍歷的順序為GDHBAECF

操作定義

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

中序遍歷左子樹
存取根節點
中序遍歷右子樹

程式碼演示

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

後序遍歷

Q：什麼後序遍歷

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

如圖：遍歷的順序為GHDBIEFCA

操作定義

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

後序遍歷左子樹
後序遍歷右子樹
存取根節點

程式碼演示

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

層序遍歷

Q：什麼層序遍歷

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

如圖：遍歷的順序為ABCDEFGHL

程式碼演示

void LevelOrder(BiTree T){
	InitQueue(Q);				//初始化輔助佇列
	BiTree p;
	EnQueue(Q,T);				//將根結點入隊
	while(!IsEmpty(Q))
	{							//佇列不空則迴圈
		DeQueue(Q,p);			//隊頭結點出隊
		visit(p);				//存取出隊結點
		if(p->1child!=NULL)
			EnQueue(Q,p->lchild);//左子樹不空，則左子樹根結點入隊
		if(p->rchild!=NULL)
			EnQueue(Q,p->rchild);//右子樹不空，則右子樹根結點入隊
	}
}

到此這篇關於C++超詳細實現二元樹的遍歷的文章就介紹到這了,更多相關C++二元樹遍歷內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

C++超詳細實現二元樹的遍歷

目錄

二元樹的遍歷

前序遍歷

中序遍歷

後序遍歷

層序遍歷

熱門文章