C++超詳細實現二叉樹的遍歷
二叉樹的遍歷
Q：什麼是二叉樹的遍歷？
A：二叉樹的遍歷是指從根結點出發，按照某種次序依次訪問二叉樹中所有結點，使得每個結點被訪問一次，且僅被訪問一次。
Q：二叉樹有幾種遍歷方法？
A：二叉樹的遍歷方法可以有很多種，如果限制瞭從左到右的習慣方式，那麼主要分為以下四種：先序遍歷，中序遍歷，後序遍歷，層序遍歷。
前序遍歷
Q：什麼是先序遍歷
A：先序遍歷就是先訪問樹的根節點，再訪問樹的左子節點，再訪問右子節點。可以想象為，從一棵二叉樹根節點為起點，沿著二叉樹外沿，逆時針走一圈回到根節點，路上遇到的元素順序，就是先序遍歷的結果。
如圖：遍歷的順序為 ABDGHCEIF
操作定義
若二叉樹為空，則空操作返回，否則：
- 訪問根節點
- 先序遍歷左子樹
- 先序遍歷右子樹
代碼演示
void PreOrderTraversal(BiTree BT)
{
if( BT ！= NULL )
{
printf(“%d\n”, BT->Data); //對節點的數據進行打印
PreOrderTraversal(BT->Left); //訪問左子樹
PreOrderTraversal(BT->Right); //訪問右子樹
}
}
中序遍歷
Q：什麼是中序遍歷
A：中序遍歷就是訪問完所有左子數後再訪問根節點，最後訪問右子樹，即左子樹-根節點-右子樹。中序遍歷可以看成，二叉樹每個節點，垂直方向投影下來，然後從左往右數，得出的結果便是中序遍歷的結果。
如圖：遍歷的順序為GDHBAECF
操作定義
若二叉樹為空，則空操作返回，否則：
- 中序遍歷左子樹
- 訪問根節點
- 中序遍歷右子樹
代碼演示
void InOrderTraversal(BiTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d\n", BT->Data);
InOrderTraversal(BT->Right);
}
}
後序遍歷
Q：什麼後序遍歷
A：後序遍歷就是先訪問左子樹和右子樹，最後訪問節點，即左子樹-右子樹-根節點。後序遍歷可以看成圍著樹的外圍繞一圈，若下面隻有一個結點就摘下來，得出的結果便是後序遍歷的結果。
如圖：遍歷的順序為GHDBIEFCA
操作定義
若二叉樹為空，則空操作返回，否則：
- 後序遍歷左子樹
- 後序遍歷右子樹
- 訪問根節點
代碼演示
void PostOrderTraversal(BiTree BT)
{
if (BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d\n", 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++二叉樹遍歷內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！