一、二叉樹(shù)遍歷的基本概念二、層次遍歷算法（兩種入隊(duì)列方式）1.出隊(duì)之后訪(fǎng)問(wèn)的層次遍歷2.入隊(duì)之前訪(fǎng)問(wèn)的層次遍歷三、層次遍歷算法的應(yīng)用難點(diǎn)：層次遍歷中隊(duì)列的變化過(guò)程第8講：二叉樹(shù)遍歷基本概念及層次序遍歷一、

二叉樹(shù)遍歷的基本概念1.什么是遍歷（周游）？

遍歷是指按照一定順序訪(fǎng)問(wèn)數(shù)據(jù)結(jié)構(gòu)（如數(shù)組、鏈表、樹(shù)、圖等）中的所有元素或節(jié)點(diǎn)的過(guò)程。遍歷的目的是執(zhí)行某種操作或獲取所需信息。一、

二叉樹(shù)遍歷的基本概念2.遍歷的步驟：（1）選擇起始位置；（2）訪(fǎng)問(wèn)元素或節(jié)點(diǎn)；（3）移動(dòng)到下一個(gè)位置；（4）終止遍歷。3.二叉樹(shù)遍歷的種類(lèi)1）層次序遍歷：ABCDEFG2）先序遍歷；3）中序遍歷；4）后序遍歷。二、層次序遍歷1.什么是二叉樹(shù)的層次序遍歷？層次遍歷，也稱(chēng)為廣度優(yōu)先遍歷，是一種從上到下、從左到右順序逐層訪(fǎng)問(wèn)二叉樹(shù)節(jié)點(diǎn)的遍歷方式。遍歷結(jié)果：ABCDEFG2.層次序遍歷算法：層次序遍歷要用到隊(duì)列1）出隊(duì)之后訪(fǎng)問(wèn)2）入隊(duì)之前訪(fǎng)問(wèn)算法1：出隊(duì)之后訪(fǎng)問(wèn)的層次遍歷#include<queue>template<class

T>void

BinaryTree<T>::levelOrder(const

BiTreeNode*t){if

(t

==nullptr)return;queue<const

BiTreeNode*>q;q.push(t);while

(!q.empty()){t

=q.front(); q.pop();cout<<t->data<<"";if

(t->left)q.push(t->left);if

(t->right)q.push(t->right);}}輸入：二叉樹(shù)的根節(jié)點(diǎn)指針輸出：二叉樹(shù)層次遍歷序列1定義隊(duì)列q，用于存儲(chǔ)二叉樹(shù)節(jié)點(diǎn)指針；2將根節(jié)點(diǎn)指針壓入隊(duì)列q；3循環(huán)，當(dāng)（隊(duì)列q不為空），執(zhí)行以下操作：3.1出隊(duì)列得到一個(gè)節(jié)點(diǎn)指針；3.2訪(fǎng)問(wèn)該指針?biāo)赶虻墓?jié)點(diǎn)；3.3如果（該節(jié)點(diǎn)的左孩子不為空），則將左孩子指針壓入隊(duì)列；3.4如果（該節(jié)點(diǎn)的右孩子不為空），則將右孩子指針壓入隊(duì)列；出隊(duì)后訪(fǎng)問(wèn)輸出序列：G#include<queue>template<class

T>void

BinaryTree<T>::levelOrder(const

BiTreeNode*t){if

(t

==nullptr)return;queue<const

BiTreeNode*>q;q.push(t);while

(!q.empty()){t

=q.front(); q.pop();cout<<t->data<<"";if

(t->left)q.push(t->left);if

(t->right)q.push(t->right);}}ABCDEFA↑A↑入隊(duì)列A↑出隊(duì)列，t指向A，輸出A，B↑、C↑入隊(duì)B↑C↑B↑出隊(duì)列，t指向B，輸出B,D↑入隊(duì)C↑D↑C↑出隊(duì)列，t指向C，輸出C，E↑、F↑入隊(duì)D↑E↑F↑D↑出隊(duì)列，t指向D，輸出D，G↑入隊(duì)E↑F↑G↑E↑出隊(duì)列，t指向E，輸出E,F↑G↑F↑出隊(duì)列，t指向F，輸出F,G↑G↑出隊(duì)列，t指向G，輸出G初始隊(duì)列為空ttttttt#include<queue>template<class

T>void

BinaryTree<T>::levelOrder2(const

BiTreeNode*t){if

(t

==nullptr)return;queue<const

BiTreeNode*>q;cout<<t->data<<"";q.push(t);while

(!q.empty()){t

=q.front();q.pop();if

(t->left){cout<<t->left->data<<"";q.push(t->left);}if

(t->right){cout<<t->right->data<<"";q.push(t->right);}}}輸入：二叉樹(shù)的根節(jié)點(diǎn)指針輸出：二叉樹(shù)層次遍歷序列1定義隊(duì)列q，用于存儲(chǔ)二叉樹(shù)節(jié)點(diǎn)指針；2訪(fǎng)問(wèn)根節(jié)點(diǎn)；3將根節(jié)點(diǎn)指針壓入隊(duì)列q；4循環(huán)，當(dāng)（隊(duì)列q不為空），執(zhí)行以下操作：4.1出隊(duì)列得到一個(gè)節(jié)點(diǎn)指針；4.2如果（該節(jié)點(diǎn)的左孩子不為空），則訪(fǎng)問(wèn)左孩子并將左孩子節(jié)點(diǎn)指針壓入隊(duì)列；4.3如果（該節(jié)點(diǎn)的右孩子不為空），則訪(fǎng)問(wèn)右孩子并將右孩子節(jié)點(diǎn)指針壓入隊(duì)列；算法2：入隊(duì)之前訪(fǎng)問(wèn)的層次遍歷入隊(duì)之前訪(fǎng)問(wèn)有三個(gè)輸出操作輸出序列：GABCDEFA↑輸出A，A↑入隊(duì)列t指向A，A↑出隊(duì)列，輸出B,B↑入隊(duì)列,輸出C，C↑入隊(duì)列B↑C↑t指向B，B↑出隊(duì)列，輸出D,D↑入隊(duì)列C↑D↑t指向C，C↑出隊(duì)列，輸出E,E↑入隊(duì)列,輸出F，F(xiàn)↑入隊(duì)列D↑E↑F↑t指向D，D↑出隊(duì)列，輸出G,G↑入隊(duì)E↑F↑G↑t指向E,E↑出隊(duì)列

F↑G↑t指向F,F↑出隊(duì)列G↑t指向G，G↑出隊(duì)列初始隊(duì)列為空ttttttt#include<queue>template<class

T>void

BinaryTree<T>::levelOrder2(const

BiTreeNode*t){if

(t

==nullptr)return;queue<const

BiTreeNode*>q;cout<<t->data<<"";q.push(t);while

(!q.empty()){t

=q.front();q.pop();if

(t->left){cout<<t->left->data<<"";q.push(t->left);}if

(t->right){cout<<t->right->data<<"";q.push(t->right);}}}把二叉樹(shù)的順序存儲(chǔ)轉(zhuǎn)化為鏈?zhǔn)酱鎯?chǔ)算法關(guān)鍵a[i]的左孩子為a[2i+1]a[i]的右孩子為a[2i+2]a[i]的雙親為a[(i-1)/2]0123456789ABC\0DEF\0\0G3、層次遍歷的應(yīng)用輸入：二叉樹(shù)的順序存儲(chǔ)數(shù)組seq輸出：鏈?zhǔn)酱鎯?chǔ)二叉樹(shù)的根節(jié)點(diǎn)指針t1定義隊(duì)列q，用于存儲(chǔ)二叉樹(shù)節(jié)點(diǎn)指針；2定義變量i，用于記錄數(shù)組下標(biāo)；3生成一個(gè)二叉鏈表節(jié)點(diǎn)，其指針為t，其data值為seq[0]，置i=0，并將t壓入隊(duì)列q；4循環(huán)，當(dāng)（隊(duì)列q不為空），執(zhí)行以下操作：4.1出隊(duì)列，將得到的節(jié)點(diǎn)指針記為parent；4.2如果（2*i+1<n，且編號(hào)為2*i+1的元素不為零元），則執(zhí)行以下操作：4.2.1生成一個(gè)新的二叉鏈表節(jié)點(diǎn)，其指針為child，其data值為seq[2*i+1]；4.2.2將child賦給parent->left；4.2.3將child壓入隊(duì)列；4.3如果（2*i+2<n，且編號(hào)為2*i+2的元素不為零元），則執(zhí)行以下操作：4.3.1生成新的二叉鏈表節(jié)點(diǎn)，其指針為child，其data值為seq[2*i+2]；4.3.2將child賦給parent->right；4.3.3將child壓入隊(duì)列；4.4考察數(shù)組下一個(gè)元素，i增1；4.5如果（下一個(gè)元素為零元），則繼續(xù)考查數(shù)組下一個(gè)元素；算法描述：t=GetBTNode(L[0]);產(chǎn)生左孩子并將其入隊(duì)產(chǎn)生右孩子并將其入隊(duì)考察下一個(gè)節(jié)點(diǎn)算法程序：template<class

T>void

BinaryTree<T>::seqToBiTreeLevel(const

vector<T>&seq){if(seq.size()==0)return;queue<BiTreeNode*>q;inti=0,n=seq.size();BiTreeNode*parent,*child;root=new

BiTreeNode(seq[0]);q.push(root);while(!q.empty()){parent=q.front();q.pop();if(2*i+1<n&&seq[2*i+1]!=T()){child=new

BiTreeNode(seq[2*i+1]);parent->left=child;q.push(child);}if(2*i+2<n&&seq[2*i+2]!=T()){child=new

BiTreeNode(seq[2*i+2]);parent->right=child;q.push(child);} i++; while(i<n&&seq[i]==T())i++;//處理零元節(jié)點(diǎn)}}產(chǎn)生左孩子并將其入隊(duì)產(chǎn)生右孩子并將其入隊(duì)考察下一個(gè)計(jì)數(shù)跳過(guò)零元節(jié)點(diǎn)2、垂直輸出二叉樹(shù)遍歷二叉樹(shù)：采用層次遍歷，輸出時(shí)確定結(jié)點(diǎn)位置。在特定位置輸出結(jié)點(diǎn)值：用cout.width(n)定位橫向位置，用層數(shù)定位縱向位置。cout是ostream類(lèi)的對(duì)象，處理標(biāo)準(zhǔn)輸出，即顯示器輸出.width(int)是ios類(lèi)中的成員函數(shù)，用于偏移橫向位置。輸入：二叉樹(shù)的根節(jié)點(diǎn)指針t輸出：在屏幕上垂直顯示二叉樹(shù)的樹(shù)狀結(jié)構(gòu)1定義隊(duì)列q，用于存儲(chǔ)二叉樹(shù)節(jié)點(diǎn)指針；2定義隊(duì)列l(wèi)ocQ，用于存儲(chǔ)二叉樹(shù)節(jié)點(diǎn)位置坐標(biāo)；3確定根節(jié)點(diǎn)位置坐標(biāo)，level=0，offset=w/2；//w為屏幕寬度4將根節(jié)點(diǎn)指針t壓入隊(duì)列q；將根節(jié)點(diǎn)位置坐標(biāo)壓入隊(duì)列l(wèi)ocQ；5循環(huán)，當(dāng)（隊(duì)列不為空），執(zhí)行以下操作：5.1q出隊(duì)列，并將隊(duì)首元素賦給t；5.2locQ出隊(duì)列，并將隊(duì)首元素賦給fLoc；5.3調(diào)用gotoxy（）函數(shù)確定輸出位置；5.4在屏幕上輸出節(jié)點(diǎn)；5.5如果（t的左子樹(shù)不為空），則執(zhí)行以下操作：5.5.1將t的左孩子節(jié)點(diǎn)壓入隊(duì)列q；5.5.2確定t的左孩子節(jié)點(diǎn)坐標(biāo)；5.5.3將t的左孩子節(jié)點(diǎn)坐標(biāo)壓入隊(duì)列l(wèi)ocQ；5.6如果（t的左子樹(shù)不為空），則執(zhí)行以下操作：5.6.1將t的右孩子節(jié)點(diǎn)壓入隊(duì)列q；5.6.2確定t的右孩子節(jié)點(diǎn)坐標(biāo)；5.6.3將t的右孩子節(jié)點(diǎn)坐標(biāo)壓入隊(duì)列l(wèi)ocQ；算法描述算法程序：template<class

T>void

BinaryTree<T>::printBiTree(const

BiTreeNode*t,int

w)const{if(t==nullptr)return;intlevel=0,offset=w/2;LocationfLoc,cLoc;queue<const

BiTreeNode*>q; queue<Location>locQ;fLoc.xIndent=offset;fLoc.yLevel=level;q.push(t);locQ.push(fLoc);while(!q.empty()){t=q.front();q.pop();fLoc=locQ.front();locQ.pop();gotoxy(fLoc.xIndent,fLoc.yLevel);cout<<t->data;if(fLoc.yLevel!=level){level++;offset=offset/2;}if(t->left){q.push(t->left);cLoc.yLevel=fLoc.yLevel+1;cLoc.xIndent=fLoc.xIndent-offset/2;locQ.push(cLoc);}if(t->right){q.push(t->right);cLoc.yLevel=fLoc.yLevel+1;cLoc.xIndent=fLoc.xIndent+offset/2;locQ.push(cLoc);}}cout<<endl;}voidGotoxy(int

xindent,int

ylevel){

static

intheight=0,indent=0;if(ylevel==0){//新的二叉樹(shù)重置靜態(tài)變量height=0;indent=0;}

if(height!=ylevel){

cout<<endl;

height++;

indent=0;

}

cout.width(xindent-indent);

indent=xindent; }（40，0）A（60，1）C（20，1）B（30，2）D（70，2）F（50，2）E（25，3）G（w=80）offset=40,level=0節(jié)點(diǎn)位置level:當(dāng)前打印層級(jí)offset用于計(jì)算縮進(jìn)聲明用于記錄打印位置的結(jié)構(gòu)體存儲(chǔ)節(jié)點(diǎn)和位置的隊(duì)列根節(jié)點(diǎn)橫向起始位置根節(jié)點(diǎn)層級(jí)為0取出隊(duì)列中的節(jié)點(diǎn)和對(duì)應(yīng)位置移動(dòng)指針位置并打印節(jié)點(diǎn)數(shù)據(jù)如果進(jìn)入新的層級(jí)，調(diào)整offset每深入一層，縮進(jìn)量減半處理左子樹(shù)子節(jié)點(diǎn)層級(jí)+1左子節(jié)點(diǎn)位置在父節(jié)點(diǎn)左側(cè)處理右子樹(shù)子節(jié)點(diǎn)層級(jí)+1左子節(jié)點(diǎn)位置在父節(jié)點(diǎn)右側(cè)ABCDEFG出隊(duì)t-->(40,0)(20,1)(60,1)(30,2)(50,2)(70,2)(25,3)ABCDEFGoffset:level:01234020105height:ylevel=01230123xident=indent:402060703025402060503070250xident:402060705025level=0offset=40level=1offset=20level=2offset=10節(jié)點(diǎn)：A，位置：xindent=40,ylevel=0節(jié)點(diǎn)B，位置：xindent=20,ylevel=1節(jié)點(diǎn)C，位置：xindent=60,ylevel=1節(jié)點(diǎn)D，位置：xindent=30,ylevel=2節(jié)點(diǎn)E，位置：xindent=50,ylevel=2節(jié)點(diǎn)F,位置:xindent=70,ylevel=2節(jié)點(diǎn)G,位置:xindent=25,ylevel=3level=3offset=5

voidPrintBTree(constBTNode<T>*t,intw)Gotoxy(intxindent,intylevel)隊(duì)列變化情況輸出結(jié)果level

OffsetfLoc.xindentfLoc.ylevelxindentylevelheightindent定位操作節(jié)點(diǎn)位置

隊(duì)列初始狀態(tài)040400

A(40,0)

出隊(duì)列（A）04040040000→40偏移40BC(20,1)(60,1)A(40,0)出隊(duì)列（B）0→140→202012010→120換行偏移20CD(60,1)(30,2)B(20,1)出隊(duì)列（C）120601601120→60不換行再偏移40DEF(30,2)(50,2)(70,2)C(60,1)出隊(duì)列（D）1→220→103025021→230換行偏移30EFG(50,2)(70,2)(25,3)D(30,2)出隊(duì)列（E）210502502230→50不換行再偏移20FG(70,2)(25,3)E(50,2)出隊(duì)列（F）210702702250→70不換行再偏移20G(25,3)F(70,2)出隊(duì)列（G）2→310→52532532→325換行偏移25

G(25,3)三、前序/中序/后序遍歷遞歸算法前序遍歷：遞歸定義

1.訪(fǎng)問(wèn)根節(jié)點(diǎn)

2.前序遍歷左子樹(shù)

3.前序遍歷右子樹(shù)中序遍歷：遞歸定義

1.中序遍歷左子樹(shù)

2.訪(fǎng)問(wèn)根節(jié)點(diǎn)

3.中序遍歷右子樹(shù)后序遍歷：遞歸定義

1.后序遍歷左子樹(shù)

2.后序遍歷右子樹(shù)

3.訪(fǎng)問(wèn)根節(jié)點(diǎn)層次遍歷結(jié)果：ABCDEFG前序遍歷結(jié)果：ABDGCEF中序遍歷結(jié)果：BGDAECF后序遍歷結(jié)果：GDBEFCA1、前序/中序/后序遍歷的定義template<class

T>void

BinaryTree<T>::preOrder(const

BiTreeNode*t)

{if

(!t)

return;cout

<<

t->data

<<

"

";preOrder(t->left);

preOrder(t->right);

}先序遍歷：遞歸算法輸入：二叉樹(shù)輸出：二叉樹(shù)的先序遍歷序列1如果（二叉樹(shù)為空），則直接返回；2否則，執(zhí)行以下操作：2.1訪(fǎng)問(wèn)根節(jié)點(diǎn)；2.2遞歸先序遍歷該二叉樹(shù)的左子樹(shù)；2.3遞歸先序遍歷該二叉樹(shù)的右子樹(shù)；中序遍歷：遞歸算法

輸入：二叉樹(shù)輸出：二叉樹(shù)的中序遍歷序列1如果（二叉樹(shù)為空），則直接返回；2否則，執(zhí)行以下操作：2.1遞歸中序遍歷該二叉樹(shù)的左子樹(shù)；2.2訪(fǎng)問(wèn)根節(jié)點(diǎn)；2.3遞歸中序遍歷該二叉樹(shù)的右子樹(shù)；template<class

T>void

BinaryTree<T>::inOrder(const

BiTreeNode*t){if

(!t)return;inOrder(t->left);cout<<t->data<<"";inOrder(t->right);}公有成員函數(shù)void