本篇文章給大家談?wù)劧鏄涞谋闅v操作，以及二叉樹的三種遍歷例題對(duì)應(yīng)的知識(shí)點(diǎn)，文章可能有點(diǎn)長(zhǎng)，但是希望大家可以閱讀完，增長(zhǎng)自己的知識(shí)，最重要的是希望對(duì)各位有所幫助，可以解決了您的問(wèn)題，不要忘了收藏本站喔。

二叉樹的層次遍歷

設(shè)計(jì)一個(gè)算法層序遍歷二叉樹（同一層從左到右訪問(wèn)）。思想：用一個(gè)隊(duì)列保存被訪問(wèn)的當(dāng)前節(jié)點(diǎn)的左右孩子以實(shí)現(xiàn)層序遍歷。

voidHierarchyBiTree(BiTreeRoot){

LinkQueue*Q;//保存當(dāng)前節(jié)點(diǎn)的左右孩子的隊(duì)列

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

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

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

Visit(p->data);//訪問(wèn)根節(jié)點(diǎn)

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

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

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

Visit(p->data);//訪問(wèn)當(dāng)前節(jié)點(diǎn)

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

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

}

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

return;

這個(gè)已經(jīng)很詳細(xì)了！你一定可以看懂的！加油?。?/p>

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

其實(shí)很簡(jiǎn)單跟著我的思路來(lái)。

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

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

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

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

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

一、首先，簡(jiǎn)單介紹一下什么是“二叉樹”

二叉樹是n個(gè)結(jié)點(diǎn)的有限集合，它的定義具有遞歸性：

（1）當(dāng)n=0時(shí)，為空樹；

（2）當(dāng)n=1時(shí)，只有一個(gè)結(jié)點(diǎn)，該節(jié)點(diǎn)稱為根結(jié)點(diǎn)；

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

圖1二叉樹

根據(jù)二叉樹的結(jié)構(gòu)和定義，可總結(jié)出二叉樹的特點(diǎn)：

（1）非空二叉樹的第i層最多有2∧（i-1）個(gè)結(jié)點(diǎn)；

（2）深度為k的二叉樹最多有2∧k-1個(gè)結(jié)點(diǎn)

二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹是非線性的結(jié)構(gòu)，其每個(gè)結(jié)點(diǎn)最多有一個(gè)“前驅(qū)”，但可以有多個(gè)“后繼”。它可以采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

1、順序存儲(chǔ)結(jié)構(gòu)

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

要介紹順序存儲(chǔ)結(jié)構(gòu)，首先要了解一個(gè)概念——完全二叉樹。如果深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)k與n滿足2∧(k-1)≦n≦2∧k-1時(shí)，該二叉樹稱為完全二叉樹。

對(duì)于一個(gè)二叉樹，如果其不是一個(gè)完全二叉樹，則首先增添一些并不存在的空結(jié)點(diǎn)，使之稱為一個(gè)完全二叉樹的形式，然后按照從上到下、從左到右的順序?qū)渲械慕Y(jié)點(diǎn)存儲(chǔ)在數(shù)組中。

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

圖2補(bǔ)完后的二叉樹

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

ABCDE∧H∧∧FGI

顯然，當(dāng)一個(gè)非完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，由于需要增加許多空結(jié)點(diǎn)，因此會(huì)造成空間的大量浪費(fèi)。

2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用鏈來(lái)表示二叉樹結(jié)點(diǎn)之間的邏輯關(guān)系。

通常的方法是鏈表中的每個(gè)結(jié)點(diǎn)由3個(gè)域組成：

左指針域＋數(shù)據(jù)域＋右指針域即：Lchild+data+Rchild其中：data域存放結(jié)點(diǎn)的數(shù)據(jù)信息；Lchild和Rchild分別存放左、右支的指針，當(dāng)某一支不存在時(shí)，相應(yīng)的指針域?yàn)榭?用符號(hào)∧國(guó)NULL表示)。

如圖1中的c結(jié)點(diǎn)，因其左支不存在，因此其Lchild的值為NULL。

三、二叉樹的遍歷算法

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

1、前序遍歷

先訪問(wèn)根結(jié)點(diǎn)，然后是左子樹，最后是右子樹。

圖1的前序遍歷結(jié)果為：

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

2、中序遍歷

先訪問(wèn)左子樹，然后是根結(jié)點(diǎn)，最后是右子樹。

圖1的中序遍歷結(jié)果為：

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

3、后續(xù)遍歷

先訪問(wèn)左子樹，然后是右子樹，最后是根結(jié)點(diǎn)。

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

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

4、層序遍歷

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

圖1的層序遍歷結(jié)果為：

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

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

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

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

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

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

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

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

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

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

關(guān)于二叉樹的遍歷操作，二叉樹的三種遍歷例題的介紹到此結(jié)束，希望對(duì)大家有所幫助。