本篇文章給大家談談二叉樹的遍歷操作，以及二叉樹的三種遍歷例題對應的知識點，文章可能有點長，但是希望大家可以閱讀完，增長自己的知識，最重要的是希望對各位有所幫助，可以解決了您的問題，不要忘了收藏本站喔。

二叉樹的層次遍歷

設計一個算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節(jié)點的左右孩子以實現(xiàn)層序遍歷。

voidHierarchyBiTree(BiTreeRoot){

LinkQueue*Q;//保存當前節(jié)點的左右孩子的隊列

InitQueue(Q);//初始化隊列

if(Root==NULL)return;//樹為空則返回

BiNode*p=Root;//臨時保存樹根Root到指針p中

Visit(p->data);//訪問根節(jié)點

if(p->lchild)EnQueue(Q,p->lchild);//若存在左孩子，左孩子進隊列

if(p->rchild)EnQueue(Q,p->rchild);//若存在右孩子，右孩子進隊列

while(!QueueEmpty(Q))//若隊列不空，則層序遍歷{DeQueue(Q,p);//出隊列

Visit(p->data);//訪問當前節(jié)點

if(p->lchild)EnQueue(Q,p->lchild);//若存在左孩子，左孩子進隊列

if(p->rchild)EnQueue(Q,p->rchild);//若存在右孩子，右孩子進隊列

}

DestroyQueue(Q);//釋放隊列空間

return;

這個已經很詳細了！你一定可以看懂的！加油啊！

二叉樹前序遍歷abdgcef中序遍歷dgbaechf后序遍歷怎么求

其實很簡單跟著我的思路來。

。。畫出來了這個樹，就很簡單了對吧前序遍歷是先根。我們看abdgcef，第一個是a，說明整個樹的根是a。中序遍歷中根，我們看dgbaechf。既然a是整個樹的根，那么a左邊的dgb就是左子樹，a右邊echf就是右子樹。再看前序遍歷：a是根，那么接下來就應該是左子樹了。我們把左子樹分離出來看既然中序遍歷已經知道是dgb了，那么前序遍歷就是a后面的bdg。已知左子樹的前序遍歷是bdg，中序遍歷是dgb，求左子樹的形狀?？?，這不又變成剛才的問題了嗎？只不過是規(guī)模減小了。顯然，根是d，d的左兒子是b，d的右兒子是g。以此類推，就能畫出整個Tree了。很簡單吧！多用手模擬一下，多做兩三題，很快就能掌握了。如果還不懂還可以Q我：328880142

c語言編程實現(xiàn)二叉樹的三種遍歷

二叉樹有三種遍歷方式，分別為先序遍歷、中序遍歷、后序遍歷。

二叉樹是指樹中節(jié)點的度不大于2的有序樹，它是一種最簡單且最重要的樹。二叉樹的遞歸定義為：二叉樹是一棵空樹，或者是一棵由一個根節(jié)點和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹。

順序存儲的二叉樹是如何創(chuàng)建和遍歷的

一、首先，簡單介紹一下什么是“二叉樹”

二叉樹是n個結點的有限集合，它的定義具有遞歸性：

（1）當n=0時，為空樹；

（2）當n=1時，只有一個結點，該節(jié)點稱為根結點；

（3）當n>1時，除了根結點外的其他節(jié)點可分為互不相交的兩個子集，稱為左右子樹，且左右子樹本質上也都是二叉樹。

圖1二叉樹

根據二叉樹的結構和定義，可總結出二叉樹的特點：

（1）非空二叉樹的第i層最多有2∧（i-1）個結點；

（2）深度為k的二叉樹最多有2∧k-1個結點

二叉樹的存儲結構

二叉樹是非線性的結構，其每個結點最多有一個“前驅”，但可以有多個“后繼”。它可以采用順序存儲結構和鏈式存儲結構。

1、順序存儲結構

二叉樹的順序存儲，就是用一組連續(xù)的存儲單元存放二叉樹的結點。必須把二叉樹的所有結點安排成一個恰當?shù)男蛄薪Y點在這個序列中的相互位置能反映出結點之間的邏輯關系。

要介紹順序存儲結構，首先要了解一個概念——完全二叉樹。如果深度為k，有n個結點的二叉樹，當k與n滿足2∧(k-1)≦n≦2∧k-1時，該二叉樹稱為完全二叉樹。

對于一個二叉樹，如果其不是一個完全二叉樹，則首先增添一些并不存在的空結點，使之稱為一個完全二叉樹的形式，然后按照從上到下、從左到右的順序將樹中的結點存儲在數(shù)組中。

以圖1為例，其補成完全二叉樹如圖2所示。

圖2補完后的二叉樹

其順序存儲狀態(tài)為：

ABCDE∧H∧∧FGI

顯然，當一個非完全二叉樹采用順序存儲結構時，由于需要增加許多空結點，因此會造成空間的大量浪費。

2、鏈式存儲結構

二叉樹的鏈式存儲結構是指用鏈來表示二叉樹結點之間的邏輯關系。

通常的方法是鏈表中的每個結點由3個域組成：

左指針域＋數(shù)據域＋右指針域即：Lchild+data+Rchild其中：data域存放結點的數(shù)據信息；Lchild和Rchild分別存放左、右支的指針，當某一支不存在時，相應的指針域為空(用符號∧國NULL表示)。

如圖1中的c結點，因其左支不存在，因此其Lchild的值為NULL。

三、二叉樹的遍歷算法

二叉樹常用的遍歷方式有：前序遍歷、中序遍歷、后續(xù)遍歷以及層序遍歷。

1、前序遍歷

先訪問根結點，然后是左子樹，最后是右子樹。

圖1的前序遍歷結果為：

A->B->D->E->F->G->C->H->I

2、中序遍歷

先訪問左子樹，然后是根結點，最后是右子樹。

圖1的中序遍歷結果為：

D->B->F->E->G->A->C->I->H

3、后續(xù)遍歷

先訪問左子樹，然后是右子樹，最后是根結點。

圖1的后續(xù)遍歷結果為：

D->>F->G->E->I->H->B->C->A

4、層序遍歷

從頂層的結點開始，從左向右依次遍歷，之后轉到第二層，繼續(xù)從左向右遍歷，……，直到所有的結點都遍歷完成。

圖1的層序遍歷結果為：

A->B->C->D->E->H->F->G->I

知道中序和后序遍歷，畫二叉樹和寫出前序遍歷

知道中序和后序遍歷，以中序遍歷是:HDMIBJNEAFKCG。后續(xù)遍歷是HMIDNJEBKFGCA為例，畫二叉樹和寫出前序遍歷的方法和步驟如下1、從后序遍歷知道，最后一個必然是根節(jié)點，因此A是根。再結合中序遍歷可知HDMIBJNE是A的左子樹部分，F(xiàn)KCG是右子樹部分；

2、取A的右子樹部分來看先，右子樹部分的中序遍歷：FKCE，后序遍歷：KFGC。接著從后序遍歷中看A的右子樹部分KFGC，所以C是根，又從中序遍歷知，F(xiàn)K是C的左子樹部分，G是C右子樹；

3、使用同樣的方法，C的左子樹部分，中序：FK，后序：KF?？梢缘贸鯢是根，那么K只能是F的右子樹了。此時如圖所示，A的右子樹部分都出來了；

4、再看，A的左子樹部分HDMIBJE，中序：HDMIBJNE，后序：HMIDNJEB。后序遍歷可知，B是根結點，那么再結合中序遍歷可知道HDMI是B的左子樹部分，JNE是B的右子樹部分；

5、緊接著就是看B的左子樹部分HDMI，中序：HDMI，后序：HMID，可知D是根，H是D的左子樹，MI是D的右子樹部分；

6、看到D的右子樹部分，中序后序都是MI，根據后序中序的特性可知道，根只能是I，M是I的左子樹；

7、再接著看看B的右子樹部分JNE，中序：JNE，后序：NJE，后序看出E是根，中序看出E無右子樹，只有JN是E的左子樹部分；

8、最后看JN的中序：JN，后序：NJ，根據后序特性看出，J是根，中序看出N是J的右子樹，那么整體的二叉樹就出來了。

關于二叉樹的遍歷操作，二叉樹的三種遍歷例題的介紹到此結束，希望對大家有所幫助。