1.概覽
二叉樹的遍歷(traversing binary tree)是指從根節(jié)點(diǎn)出發(fā)诺擅，按照某種次序依次訪問二叉樹中所有結(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)被訪問依次且僅被訪問一次啡直。
注意：
- 從根節(jié)點(diǎn)出發(fā)烁涌，并不一定是從根節(jié)點(diǎn)開始遍歷苍碟，只是從根節(jié)點(diǎn)開始邏輯
- 次序表示有一定的規(guī)則
- 訪問表示可以得到這個(gè)結(jié)點(diǎn)的信息
二叉樹的遍歷次序不同于線性結(jié)構(gòu)，線性結(jié)構(gòu)最多也就是分為順序撮执、循環(huán)微峰、雙向等簡(jiǎn)單的遍歷方式。
二叉樹的遍歷方式可以很多抒钱，如果我們限制了從左到右的習(xí)慣方式蜓肆，那么主要就分為以下四種：
- 前序遍歷
- 中序遍歷
- 后序遍歷
- 層序遍歷
2.前序遍歷
定義：若二叉樹為空，則空操作返回继效，否則先訪問根節(jié)點(diǎn)症杏，然后前序遍歷左子樹，再前序遍歷右子樹
如圖所示瑞信，先訪問根節(jié)點(diǎn)A厉颤，然后訪問A的左子樹B，再訪問B的左子樹D凡简，再訪問D的左子樹H逼友，由于H是終端結(jié)點(diǎn)，則再訪問D的右子樹I秤涩，訪問完了B的左子樹帜乞，再訪問B的右子樹，剩下的類推可得到
總結(jié)：前序遍歷中筐眷，遵循根節(jié)點(diǎn)->左子樹->右子樹的順序來訪問結(jié)點(diǎn)
3. 中序遍歷
定義：若二叉樹為空黎烈，則空操作返回，否則從根節(jié)點(diǎn)開始(注意并不是先訪問根節(jié)點(diǎn)),中序遍歷根節(jié)點(diǎn)的左子樹匀谣，然后是訪問根節(jié)點(diǎn)照棋，最后中序遍歷右子樹。
總結(jié)：中序遍歷遵循左子樹->根節(jié)點(diǎn)->右子樹的順序來訪問結(jié)點(diǎn)
4.后序遍歷
定義：若樹為空武翎，則空操作返回烈炭，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問左右子樹，最后訪問根節(jié)點(diǎn)
總結(jié)：后序遍歷遵循左子樹->右子樹->根節(jié)點(diǎn)的順序來訪問結(jié)點(diǎn)
5.層序遍歷
定義：若樹為空宝恶，則空操作返回符隙，否則從樹的第一層，也就是根節(jié)點(diǎn)開始訪問垫毙，從上而下逐層遍歷霹疫，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問
總結(jié)：層序遍歷遵循層級(jí)遞增综芥，同層級(jí)中從左至右的順序訪問結(jié)點(diǎn)
6.算法：使用前序遍歷更米，建立二叉樹并進(jìn)行遍歷，輸出各個(gè)結(jié)點(diǎn)的層次
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//創(chuàng)建一棵二叉樹毫痕，約定用戶遵照前序遍歷的方式輸入數(shù)據(jù)
Status createBiTree(BiTree *T){
//接收輸入
ElemType c = 0;
scanf("%c",&c);
if ( c == ' ') {
//輸入空格便是結(jié)束這棵子樹
*T = NULL;
return ERROR;
} else {
*T = (BiTree)malloc(sizeof(BiTNode));
(*T) -> data = c;
//遞歸創(chuàng)建
//創(chuàng)建左子樹
createBiTree(&((*T)->lchild));
//創(chuàng)建右子樹
createBiTree(&((*T)->rchild));
return OK;
}
}
//訪問二叉樹結(jié)點(diǎn)的具體操作
void visit(ElemType c,int level){
printf("data:%c,level:%d",c,level);
}
//前序遍歷
Status preOrderTraverse(BiTree T,int level){
if ( !T ) {
return ERROR;
}
visit(T->data, level);
//遞歸遍歷
preOrderTraverse(T->lchild, level+1);
preOrderTraverse(T->rchild, level+1);
return OK;
}
int main(){
int level = 1;
BiTree T = NULL;
createBiTree(&T);
preOrderTraverse(T, level);
return 0;
}
7.二叉樹的前序征峦、中序、后序遍歷的遞歸與非遞歸實(shí)現(xiàn)
二叉樹遍歷的非遞歸實(shí)現(xiàn)需要借助棧來實(shí)現(xiàn)(由于棧LIFO的特性)消请，我們先建立一個(gè)樹的結(jié)點(diǎn)棧栏笆，如下所示:
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct BiTreeStack{
BiTNode *base;//棧底
BiTNode *top;//棧頂
int stackSize;
}BiTreeStack;
Status initStack(BiTreeStack *s){
s->base = (BiTNode *)malloc(sizeof(BiTNode) * STACK_INIT_SIZE);
if (!s->base) {
return ERROR;
}
s->top = s->base;
s->stackSize = STACK_INIT_SIZE;
return OK;
}
Status Push(BiTreeStack *s,BiTNode node){
if (s->top - s->base >= s->stackSize) {
s->base = (BiTNode *)realloc(s->base, sizeof(BiTNode)*(s->stackSize + STACKINCREMENT));
if (!s->base) {
return ERROR;
}
s->top = s->base + s->stackSize;
s->stackSize += STACKINCREMENT;
}
*(s->top) = node;
(s->top)++;
return OK;
}
Status Pop(BiTreeStack *s,BiTNode *node){
if (s->top - s->base == 0) {
return ERROR;
}
*node = *(--(s->top));
return OK;
}
int StackLength(BiTreeStack *s){
return (int)(s->top - s->base);
}
void visitNode(BiTree node){
printf("data:%c",node->data);
}
前序遍歷
前序遍歷的遞歸實(shí)現(xiàn)比較簡(jiǎn)單，遵循根節(jié)點(diǎn)-左子樹-右子樹的順序即可
//遞歸
Status PreorderTraversalRecursive(BiTree T){
if (!T) {
return ERROR;
}
visitNode(T);
PreorderTraversalRecursive(T->lchild);
PreorderTraversalRecursive(T->rchild);
return OK;
}
非遞歸實(shí)現(xiàn)我們需要?jiǎng)?chuàng)建一個(gè)棧臊泰，先把二叉樹的根節(jié)點(diǎn)壓入棧蛉加，訪問后，再依次壓入右結(jié)點(diǎn)缸逃，再壓入左結(jié)點(diǎn)针饥，這樣訪問的時(shí)候就遵循了根節(jié)點(diǎn)-左子樹-右子樹的順序
//非遞歸
Status PreorderTraversalNotRecursive(BiTree T){
if (!T) {
return ERROR;
}
BiTNode node = *T;
BiTreeStack s;
BiTreeStack *stack = NULL;
initStack(&s);
stack = &s;
Push(stack, node);
while (StackLength(stack) != 0) {
Pop(stack, &node);
visitNode(&node);
//先把右子樹根節(jié)點(diǎn)壓入棧
if (node.rchild) {
Push(stack, *(node.rchild));
}
//再把左子樹根節(jié)點(diǎn)壓入棧
if (node.lchild) {
Push(stack, *(node.lchild));
}
}
return OK;
}
中序遍歷
中序遍歷的遞歸實(shí)現(xiàn)比較簡(jiǎn)單，遵循左子樹-根節(jié)點(diǎn)-右子樹的順序即可
//遞歸
Status InorderTraversalRecursive(BiTree T){
if (!T) {
return ERROR;
}
InorderTraversalRecursive(T->lchild);
visitNode(T);
InorderTraversalRecursive(T->rchild);
return OK;
}
中序遍歷的非遞歸實(shí)現(xiàn)稍微麻煩一點(diǎn)需频，我們需要先從根節(jié)點(diǎn)出發(fā)丁眼，逐個(gè)將左子樹壓入棧，由于我們知道葉子結(jié)點(diǎn)是沒有子樹的昭殉，那么我每次每次訪問的就當(dāng)做是根節(jié)點(diǎn)苞七，我們判斷它是否有右子樹，有右子樹的話挪丢，就重復(fù)之前步驟蹂风，將左子樹依次加入到棧中，這樣也就遵循了中序遍歷左子樹-根節(jié)點(diǎn)-右子樹的順序
//非遞歸
Status InorderTraversalNotRecursive(BiTree T){
if (!T) {
return ERROR;
}
BiTNode *p = T;
BiTreeStack s;
BiTreeStack *stack = NULL;
initStack(&s);
stack = &s;
//將左子樹都?jí)喝霔? while (p) {
Push(stack, *p);
p = p->lchild;
}
//開始遍歷
while (StackLength(stack)) {
//每一個(gè)出棧的結(jié)點(diǎn)我們都當(dāng)做根節(jié)點(diǎn)
Pop(stack, p);
visitNode(p);
//判斷有無右子樹
if (p->rchild) {
p = p->rchild;
Push(stack, *p);
while (p->lchild) {
p = p->lchild;
Push(stack, *p);
}
}
}
return OK;
}
后序遍歷
后序遍歷的遞歸實(shí)現(xiàn)也比較簡(jiǎn)單乾蓬，遵循左子樹-右子樹-根節(jié)點(diǎn)的順序即可
//遞歸
Status PostorderTraversalRecursive(BiTree T){
if (!T) {
return ERROR;
}
PostorderTraversalRecursive(T->lchild);
PostorderTraversalRecursive(T->rchild);
visitNode(T);
return OK;
}
后序遍歷的非遞歸實(shí)現(xiàn)看上去是最麻煩的惠啄，不過我們?nèi)匀豢梢杂冒凑蘸笮虮闅v左子樹-右子樹-根節(jié)點(diǎn)的思路來進(jìn)行思考：
- 對(duì)于每一個(gè)結(jié)點(diǎn)，如果它是非葉子結(jié)點(diǎn)任内，且它的左孩子和右孩子都不是上一次訪問的結(jié)點(diǎn)的情況下撵渡，循環(huán)將它的左子樹壓入棧，這樣就確定了訪問的順序
- 將棧頂結(jié)點(diǎn)推出族奢，判斷結(jié)點(diǎn)是否有右孩子且右孩子不是之前訪問的結(jié)點(diǎn)的情況下姥闭，將右孩子壓入棧
- 棧頂結(jié)點(diǎn)推出，不符合2的條件下越走，訪問結(jié)點(diǎn)棚品，并存儲(chǔ)新訪問結(jié)點(diǎn)的指針，然后將出棧新節(jié)點(diǎn)有用于比較
//非遞歸
Status PostorderTraversalNotRecursive(BiTree T){
if (!T) {
return ERROR;
}
BiTNode *p = T;
//記錄上一次訪問的結(jié)點(diǎn)
BiTNode *pre = T;
BiTreeStack s;
BiTreeStack *stack = NULL;
initStack(&s);
stack = &s;
while(p || StackLength(stack)){
if(p != NULL && pre != p->lchild && pre != p->rchild){ //結(jié)點(diǎn)不為空且左孩子和右孩子都不是上一次訪問的,入棧左子樹
Push(stack, *p);
p = p->lchild;
}
else{
Pop(stack, p);
if(p->rchild != NULL && pre != p->rchild){ //右子樹不為空且右孩子沒有訪問過廊敌，入棧右子樹結(jié)點(diǎn)
Push(stack, *p);
p = p->rchild;
Push(stack, *p);
}
else{
//訪問到最后的右子樹的結(jié)點(diǎn)后铜跑，退棧
visitNode(p);
pre = p;
Pop(stack, p);
}
}
}
return OK;
}
