大家好，二叉樹的深度遍歷相信很多的網(wǎng)友都不是很明白，包括c++多態(tài)也是一樣，不過沒有關(guān)系，接下來就來為大家分享關(guān)于二叉樹的深度遍歷和c++多態(tài)的一些知識點，大家可以關(guān)注收藏，免得下次來找不到哦，下面我們開始吧！
順序存儲的二叉樹是如何創(chuàng)建和遍歷的
一、首先，簡單介紹一下什么是“二叉樹”
二叉樹是n個結(jié)點的有限集合，它的定義具有遞歸性：
（1）當(dāng)n=0時，為空樹；
（2）當(dāng)n=1時，只有一個結(jié)點，該節(jié)點稱為根結(jié)點；
（3）當(dāng)n>1時，除了根結(jié)點外的其他節(jié)點可分為互不相交的兩個子集，稱為左右子樹，且左右子樹本質(zhì)上也都是二叉樹。
圖1二叉樹
根據(jù)二叉樹的結(jié)構(gòu)和定義，可總結(jié)出二叉樹的特點：
（1）非空二叉樹的第i層最多有2∧（i-1）個結(jié)點；
（2）深度為k的二叉樹最多有2∧k-1個結(jié)點
二叉樹的存儲結(jié)構(gòu)二叉樹是非線性的結(jié)構(gòu)，其每個結(jié)點最多有一個“前驅(qū)”，但可以有多個“后繼”。它可以采用順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。
1、順序存儲結(jié)構(gòu)
二叉樹的順序存儲，就是用一組連續(xù)的存儲單元存放二叉樹的結(jié)點。必須把二叉樹的所有結(jié)點安排成一個恰當(dāng)?shù)男蛄薪Y(jié)點在這個序列中的相互位置能反映出結(jié)點之間的邏輯關(guān)系。
要介紹順序存儲結(jié)構(gòu)，首先要了解一個概念——完全二叉樹。如果深度為k，有n個結(jié)點的二叉樹，當(dāng)k與n滿足2∧(k-1)≦n≦2∧k-1時，該二叉樹稱為完全二叉樹。
對于一個二叉樹，如果其不是一個完全二叉樹，則首先增添一些并不存在的空結(jié)點，使之稱為一個完全二叉樹的形式，然后按照從上到下、從左到右的順序?qū)渲械慕Y(jié)點存儲在數(shù)組中。
以圖1為例，其補成完全二叉樹如圖2所示。
圖2補完后的二叉樹
其順序存儲狀態(tài)為：
ABCDE∧H∧∧FGI顯然，當(dāng)一個非完全二叉樹采用順序存儲結(jié)構(gòu)時，由于需要增加許多空結(jié)點，因此會造成空間的大量浪費。
2、鏈式存儲結(jié)構(gòu)
二叉樹的鏈式存儲結(jié)構(gòu)是指用鏈來表示二叉樹結(jié)點之間的邏輯關(guān)系。
通常的方法是鏈表中的每個結(jié)點由3個域組成：
左指針域＋數(shù)據(jù)域＋右指針域即：Lchild+data+Rchild其中：data域存放結(jié)點的數(shù)據(jù)信息；Lchild和Rchild分別存放左、右支的指針，當(dāng)某一支不存在時，相應(yīng)的指針域為空(用符號∧國NULL表示)。如圖1中的c結(jié)點，因其左支不存在，因此其Lchild的值為NULL。
三、二叉樹的遍歷算法二叉樹常用的遍歷方式有：前序遍歷、中序遍歷、后續(xù)遍歷以及層序遍歷。
1、前序遍歷
先訪問根結(jié)點，然后是左子樹，最后是右子樹。
圖1的前序遍歷結(jié)果為：
A->B->D->E->F->G->C->H->I
2、中序遍歷
先訪問左子樹，然后是根結(jié)點，最后是右子樹。
圖1的中序遍歷結(jié)果為：
D->B->F->E->G->A->C->I->H
3、后續(xù)遍歷
先訪問左子樹，然后是右子樹，最后是根結(jié)點。
圖1的后續(xù)遍歷結(jié)果為：
D->>F->G->E->I->H->B->C->A
4、層序遍歷
從頂層的結(jié)點開始，從左向右依次遍歷，之后轉(zhuǎn)到第二層，繼續(xù)從左向右遍歷，……，直到所有的結(jié)點都遍歷完成。
圖1的層序遍歷結(jié)果為：
A->B->C->D->E->H->F->G->I
二叉樹的雙序遍歷是指什么可不可以解釋的通俗點:)
雙序遍歷是指對于二叉樹的每一個結(jié)點來說，先訪問這個結(jié)點，再按雙序遍歷它的左子樹，然后再一次訪問這個結(jié)點，接下來按雙序遍歷它的右子樹
舉個例子：
Input
HDA##C#B##GF#E###-+a##xb##-c##d##/e##f##
Output
HDAADCCBBHGFFEEG-+aa+xbbx-cc-dd-/ee/ff
二叉樹的層序遍歷需要用到什么存儲結(jié)構(gòu)
隊列或者數(shù)組都可以
隊列
1、首先將二叉樹的根節(jié)點push到隊列中，判斷隊列不為NULL，就輸出隊頭的元素，2、判斷節(jié)點如果有孩子，就將孩子push到隊列中，3、遍歷過的節(jié)點出隊列，4、循環(huán)以上操作，直到Tree==NULL。
數(shù)組
1、創(chuàng)建一個指針數(shù)組，保存二叉樹結(jié)構(gòu)體指針，2、保存二叉樹根節(jié)點，再申請變量in、out，控制數(shù)組，在遍歷過程中，始終能找到節(jié)點和該節(jié)點的前一個節(jié)點，3、循環(huán)以上過程。
二叉樹三種遍歷順序的特點
二叉樹的遍歷分為以下三種：
先序遍歷：遍歷順序規(guī)則為【根左右】
中序遍歷：遍歷順序規(guī)則為【左根右】
后序遍歷：遍歷順序規(guī)則為【左右根】
二叉樹的層序遍歷用堆棧
要構(gòu)建二叉樹及對二叉樹進行操作首先得構(gòu)建節(jié)點，節(jié)點包括節(jié)點的值還有它的左右孩子，
對二叉樹的操作有構(gòu)建，遍歷（遞歸，非遞歸，層次遍歷）。棧的特點是先進先出，用棧能保留二叉樹的訪問路徑，所以二叉樹的非遞歸遍歷應(yīng)該用棧來操作，隊列是先進后出，用來層次打印二叉樹。
END，本文到此結(jié)束，如果可以幫助到大家，還望關(guān)注本站哦！
