所謂遍歷(Traversal)是指沿著某條搜索路線，依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)。訪問(wèn)結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問(wèn) 題。 遍歷是二叉樹(shù)上最重要的運(yùn)算之一，是二叉樹(shù)上進(jìn)行其它運(yùn)算之基礎(chǔ)。
一、基本概念
每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，左子樹(shù)和右子樹(shù)，次序不可以顛倒。
性質(zhì)：
1、非空二叉樹(shù)的第n層上至多有2^(n-1)個(gè)元素。
2、深度為h的二叉樹(shù)至多有2^h-1個(gè)結(jié)點(diǎn)。
滿二叉樹(shù)：所有終端都在同一層次，且非終端結(jié)點(diǎn)的度數(shù)為2。
在滿二叉樹(shù)中若其深度為h，則其所包含的結(jié)點(diǎn)數(shù)必為2^h-1。
完全二叉樹(shù)：除了最大的層次即成為一顆滿二叉樹(shù)且層次最大那層所有的結(jié)點(diǎn)均向左靠齊，即集中在左面的位置上，不能有空位置。
對(duì)于完全二叉樹(shù)，設(shè)一個(gè)結(jié)點(diǎn)為i則其父節(jié)點(diǎn)為i/2，2i為左子節(jié)點(diǎn)，2i+1為右子節(jié)點(diǎn)。

 簡(jiǎn)單二叉樹(shù)遍歷，可分為：先序，中序，后序。

  在此分別總結(jié)先序，中序，后序的結(jié)點(diǎn)輸出順序。

  先序： 1.訪問(wèn)根結(jié)點(diǎn)

　　　　2.訪問(wèn)左子樹(shù)

　　　　3.訪問(wèn)右子樹(shù)

 

先序較簡(jiǎn)單，不予以即系解釋。

  中序：1.訪問(wèn)左子樹(shù)

　　　  2.訪問(wèn)根結(jié)點(diǎn)

　　     3.訪問(wèn)右子樹(shù)

　　　　原則：訪問(wèn)左子樹(shù)?！鞠仍L問(wèn)左子樹(shù)中的左子樹(shù)，再訪問(wèn)左子樹(shù)中的右子樹(shù)?！恐钡皆L問(wèn)到葉子結(jié)點(diǎn)后輸出。

　　　　　　　輸出根。

　　　　　　   訪問(wèn)右子樹(shù)。【先訪問(wèn)右子樹(shù)中的左子樹(shù)，再訪問(wèn)右子樹(shù)中的右子樹(shù)?！恐钡皆L問(wèn)到葉子結(jié)點(diǎn)后輸出。

具體步驟如下：

  A作為根。從A開(kāi)始，先訪問(wèn)A的左子樹(shù)。即。

在看B的左子樹(shù)，D。則輸出D。B無(wú)左子樹(shù)。訪問(wèn)完B的左子樹(shù)。然后訪問(wèn)B。輸出B。再看B的右子樹(shù)。F有左子樹(shù)E，則輸出E。返回輸出F。A的左子樹(shù)全部輸出完，再返回A，輸出A。

  

同理，看A的右子樹(shù)。。輸出順序?yàn)镚,H,C,I。

 

所以，中序遍歷輸出的結(jié)果為：（D B E F）A（G H C I）.

 

  后序：1.訪問(wèn)左子樹(shù)

　　　  2.訪問(wèn)右子樹(shù)

          3.訪問(wèn)根

　　　  原則：訪問(wèn)左子樹(shù)?！鞠仍L問(wèn)左子樹(shù)中的左子樹(shù)，再訪問(wèn)左子樹(shù)中的右子樹(shù)】。直到訪問(wèn)到葉子結(jié)點(diǎn)后輸出。

　　　　　　  訪問(wèn)右子樹(shù)?！鞠仍L問(wèn)右子樹(shù)中的左子樹(shù)，再訪問(wèn)右子樹(shù)中的右子樹(shù)】。直到訪問(wèn)到葉子結(jié)點(diǎn)后輸出。

　　　　　　  再返回訪問(wèn)根，并輸出。

具體步驟：

  先訪問(wèn)A的左子樹(shù)。再訪問(wèn)左子樹(shù)中的左子樹(shù)。【即：A的左子樹(shù)為B，再訪問(wèn)B的左子樹(shù)D。D沒(méi)有左右子樹(shù)，輸出D?！浚缓笤L問(wèn)左子樹(shù)中的右子樹(shù)?！炯矗涸L問(wèn)B的右子樹(shù)F，F(xiàn)還有左子樹(shù)，再訪問(wèn)F的左子樹(shù)E，E沒(méi)有左右子樹(shù)。輸出E。再輸出F，再輸出B?！?。

  然后訪問(wèn)A的右子樹(shù)。再訪問(wèn)右子樹(shù)中的左子樹(shù)?！炯矗篈的右子樹(shù)為C，再訪問(wèn)C的左子樹(shù)G。G還有右子樹(shù)H，輸出H。再輸出G，再輸出G】，然后訪問(wèn)右子樹(shù)中的右子樹(shù)?！炯矗涸L問(wèn)C的右子樹(shù)I，I沒(méi)有左右子樹(shù)，輸出I。在輸出C。再輸出A?！?。

  所以，后序遍歷輸出結(jié)果為：（D E F B）（H G I C）A

二、存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)：
將數(shù)據(jù)結(jié)構(gòu)存在一塊固定的數(shù)組中。

#define LENGTH 100 
typedef char datatype; 
typedef struct node{ 
    datatype data; 
    int lchild,rchild; 
    int parent; 
}Node; 
 
Node tree[LENGTH]; 
int length; 
int root; 

   雖然在遍歷速度上有一定的優(yōu)勢(shì)，但因所占空間比較大，是非主流二叉樹(shù)。二叉樹(shù)通常以鏈?zhǔn)酱鎯?chǔ)。
鏈?zhǔn)酱鎯?chǔ)：

typedef char datatype; 
 
typedef struct BinNode{ 
    datatype data; 
    struct BinNode* lchild; 
    struct BinNode* rchild; 
}BinNode; 
 
typedef BinNode* bintree;          //bintree本身是個(gè)指向結(jié)點(diǎn)的指針 

三、二叉樹(shù)的遍歷
遍歷即將樹(shù)的所有結(jié)點(diǎn)訪問(wèn)且僅訪問(wèn)一次。按照根節(jié)點(diǎn)位置的不同分為前序遍歷，中序遍歷，后序遍歷。
前序遍歷：根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)
中序遍歷：左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)
后序遍歷：左子樹(shù)->右子樹(shù)->根節(jié)點(diǎn)
例如：求下面樹(shù)的三種遍歷

前序遍歷：abdefgc
中序遍歷：debgfac
后序遍歷：edgfbca
四、遍歷的實(shí)現(xiàn)
遞歸實(shí)現(xiàn)(以前序遍歷為例，其他的只是輸出的位置稍有不同)

void preorder(bintree t){ 
    if(t){ 
        printf("%c ",t->data); 
        preorder(t->lchild); 
        preorder(t->rchild); 
    } 
} 

非遞歸的實(shí)現(xiàn)
因?yàn)楫?dāng)遍歷過(guò)根節(jié)點(diǎn)之后還要回來(lái)，所以必須將其存起來(lái)?？紤]到后進(jìn)先出的特點(diǎn)，選用棧存儲(chǔ)。數(shù)量確定，以順序棧存儲(chǔ)。

#define SIZE 100 
typedef struct seqstack{ 
    bintree data[SIZE]; 
    int tag[SIZE];   //為后續(xù)遍歷準(zhǔn)備的 
    int top;     //top為數(shù)組的下標(biāo) 
}seqstack; 
 
void push(seqstack *s,bintree t){ 
 
    if(s->top == SIZE){ 
        printf("the stack is full\n"); 
    }else{ 
        s->top++; 
        s->data[s->top]=t; 
    } 
} 
 
bintree pop(seqstack *s){ 
    if(s->top == -1){ 
        return NULL; 
    }else{ 
        s->top--; 
        return s->data[s->top+1]; 
    } 
} 

1、前序遍歷

void preorder_dev(bintree t){ 
    seqstack s; 
    s.top = -1;     //因?yàn)閠op在這里表示了數(shù)組中的位置，所以空為-1 
    if(!t){ 
        printf("the tree is empty\n"); 
    }else{ 
        while(t || s.stop != -1){ 
            while(t){    //只要結(jié)點(diǎn)不為空就應(yīng)該入棧保存，與其左右結(jié)點(diǎn)無(wú)關(guān)     
                  printf("%c ",t->data); 
                push(&s,t); 
                t= t->lchild; 
            } 
            t=pop(&s); 
            t=t->rchild; 
        } 
    } 
} 

2、中序遍歷
 

void midorder(bintree t){ 
    seqstack s; 
    s.top = -1; 
    if(!t){ 
        printf("the tree is empty!\n"); 
    }else{ 
        while(t ||s.top != -1){ 
            while(t){ 
                push(&s,t); 
                t= t->lchild; 
            } 
            t=pop(&s); 
            printf("%c ",t->data); 
            t=t->rchild; 
        } 
    } 
} 

3、后序遍歷
因?yàn)楹笮虮闅v最后還要要訪問(wèn)根結(jié)點(diǎn)一次，所以要訪問(wèn)根結(jié)點(diǎn)兩次。采取夾標(biāo)志位的方法解決這個(gè)問(wèn)題。
這段代碼非常糾結(jié)，對(duì)自己有信心的朋友可以嘗試獨(dú)立寫(xiě)一下。反正我是寫(xiě)了很長(zhǎng)時(shí)間。邏輯不難，我畫(huà)了一張邏輯圖：

代碼：
 

void postorder_dev(bintree t){ 
    seqstack s; 
    s.top = -1; 
    if(!t){ 
        printf("the tree is empty!\n"); 
    }else{ 
        while(t || s.top != -1){    //?？樟说耐瑫r(shí)t也為空。 
            while(t){ 
                push(&s,t); 
                s.tag[s.top] = 0;   //設(shè)置訪問(wèn)標(biāo)記，0為第一次訪問(wèn)，1為第二次訪問(wèn) 
                t= t->lchild; 
            } 
            if(s.tag[s.top] == 0){  //第一次訪問(wèn)時(shí)，轉(zhuǎn)向同層右結(jié)點(diǎn) 
                t= s.data[s.top];   //左走到底時(shí)t是為空的，必須有這步！ 
                s.tag[s.top]=1;      
                t=t->rchild; 
            }else { 
                while (s.tag[s.top] == 1){ //找到棧中下一個(gè)第一次訪問(wèn)的結(jié)點(diǎn)，退出循環(huán)時(shí)并沒(méi)有pop所以為其左子結(jié)點(diǎn) 
                    t = pop(&s); 
                    printf("%c ",t->data); 
                } 
                t = NULL; //必須將t置空。跳過(guò)向左走，直接向右走 
            } 
        } 
    } 
} 

4、層次遍歷：即每一層從左向右輸出
元素需要儲(chǔ)存有先進(jìn)先出的特性，所以選用隊(duì)列存儲(chǔ)。
隊(duì)列的定義：

#define MAX 1000 
 
typedef struct seqqueue{ 
    bintree data[MAX]; 
    int front; 
    int rear; 
}seqqueue; 
 
 
void enter(seqqueue *q,bintree t){ 
    if(q->rear == MAX){ 
        printf("the queue is full!\n"); 
    }else{ 
        q->data[q->rear] = t; 
        q->rear++; 
    } 
} 
 
bintree del(seqqueue *q){ 
    if(q->front == q->rear){ 
        return NULL; 
    }else{ 
        q->front++; 
        return q->data[q->front-1]; 
    } 
} 

遍歷實(shí)現(xiàn)

void level_tree(bintree t){ 
    seqqueue q; 
    bintree temp; 
    q.front = q.rear = 0; 
    if(!t){ 
        printf("the tree is empty\n"); 
        return ; 
    } 
    enter(&q,t); 
    while(q.front != q.rear){ 
        t=del(&q); 
        printf("%c ",t->data); 
        if(t->lchild){ 
            enter(&q,t->lchild); 
        } 
        if(t->rchild){ 
            enter(&q,t->rchild); 
        } 
    } 
} 

5、利用前序遍歷的結(jié)果生成二叉樹(shù)

//遞歸調(diào)用，不存點(diǎn)，想的時(shí)候只關(guān)注于一個(gè)點(diǎn)，因?yàn)檫€會(huì)回來(lái)的，不要跟蹤程序運(yùn)行，否則容易多加循環(huán) 
 
void createtree(bintree *t){       
    datatype c; 
    if((c=getchar()) == '#') 
        *t = NULL; 
    else{ 
        *t = (bintree)malloc(sizeof(BinNode)); 
        (*t)->data = c; 
        createtree(&(*t)->lchild); 
        createtree(&(*t)->rchild); 
    } 
} 

6、二叉樹(shù)的查找

bintree search_tree(bintree t,datatype x){ 
    if(!t){ 
        return NULL; 
    } 
    if(t->data == x){ 
        return t; 
    }else{ 
        if(!search_tree(t->lchild,x)){ 
            return search_tree(t->rchild,x); 
        } 
        return t; 
    } 
} 

7、統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)

int count_tree(bintree t){ 
    if(t){ 
        return (count_tree(t->lchild)+count_tree(t->rchild)+1); 
    } 
    return 0; 
} 

8、比較兩個(gè)樹(shù)是否相同

int is_equal(bintree t1,bintree t2){ 
    if(!t1 && !t2){      //都為空就相等 
        return 1; 
    } 
    if(t1 && t2 && t1->data == t2->data){      //有一個(gè)為空或數(shù)據(jù)不同就不判斷了 
        if(is_equal(t1->lchild,t2->lchild)) 
            if(is_equal(t1->rchild,t2->rchild)){ 
                return 1; 
            } 
    } 
    return 0; 
} 

9、求二叉樹(shù)的深度

int hight_tree(bintree t){ 
    int h,left,right; 
    if(!t){ 
        return 0; 
    } 
    left = hight_tree(t->lchild); 
    right = hight_tree(t->rchild); 
    h = (left>right?left:right)+1; 
    return h; 
}