C語言實現(xiàn)二叉樹的各種遍歷及求解深度

一俯艰、介紹

二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)弦悉，在很多方面都有重要的應(yīng)用，此文主要記錄了二叉樹的基礎(chǔ)知識蟆炊，包括二叉樹的建立稽莉、前中后序遍歷方式、層次遍歷方式涩搓、求解二叉樹的深度污秆、求解二叉樹的節(jié)點總數(shù)、求解二叉樹每層的節(jié)點數(shù)目等昧甘。(更好的閱讀體驗良拼，請移步我的個人博客)

二、實現(xiàn)思路

主要借助棧和隊列方式實現(xiàn)二叉樹的非遞歸訪問等操作充边，二叉樹的建立采用遞歸方式庸推。層次遍歷時，借助隊列數(shù)據(jù)結(jié)構(gòu)浇冰，將根節(jié)點入隊贬媒，當(dāng)隊列不為空時，退出隊列的一個節(jié)點肘习，判斷此節(jié)點是否有左孩子际乘，如有則訪問，并將此孩子入隊列漂佩，然后判斷此節(jié)點是否有右孩子脖含，如有則訪問罪塔，并將有孩子入隊列；重復(fù)此過程即可养葵。

三征堪、實現(xiàn)代碼

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100
typedef char dataType;
//二叉樹結(jié)構(gòu)
typedef struct bnode{
    dataType data;
    struct bnode *lChild,*rChild;
}Bnode,*BTree;
//隊列結(jié)構(gòu)
typedef struct {
    BTree data[MAXSIZE];
    int front,rear;
}SeqQueue,*PSeqQueue;
//棧的結(jié)構(gòu)
typedef struct {
    BTree data[MAXSIZE];
    int top;
}SeqStack,*PSeqStack;
 
//隊列的初始化
PSeqQueue initSeqQueue(){
    PSeqQueue  queue;
    queue = (PSeqQueue)malloc(sizeof(SeqQueue));
    if(queue){
        queue->front = queue->rear = 0;
    }
    return queue;
}
//判斷隊列是否為空
int emptyQueue(PSeqQueue queue){
    if(queue && queue->front==queue->rear){
        return 1;
    }else{
        return 0;
    }
}
//入隊列
int pushQueue(PSeqQueue queue,Bnode *node){
    if((queue->rear+1)%MAXSIZE == queue->front){//判斷隊列是否滿了
        return -1;
    }else{
        queue->rear = (queue->rear+1)%MAXSIZE;//位置為0的地址空間不用，方便判斷是否為空
        queue->data[queue->rear] = node;
        return 1;
    }
}
//出隊列
int popQueue(PSeqQueue queue,BTree *node){
    if(emptyQueue(queue)){
        return -1;
    }else{
        queue->front = (queue->front +1)%MAXSIZE;
        *node = queue->data[queue->front];
        return 1;
    }
}
//讀取隊頭元素
int frontQueue(PSeqQueue queue,BTree *node){
    if(queue->rear == queue->front){
        return -1;
    }else{
        *node = queue->data[(queue->front+1)%MAXSIZE];
        return 1;
    }
}
//銷毀隊列
void destroyQueue(PSeqQueue *queue){
    if(*queue){
        free(*queue);
        *queue = NULL;
    }
}
//棧的初始化
PSeqStack initStack(){
    PSeqStack stack;
    stack = (PSeqStack)malloc(sizeof(SeqStack));
    if(stack){
        stack->top = -1;
    }
    return stack;
}
//判斷棧是否為空    1,空;0,非空
int emptyStack(PSeqStack stack){
    if(stack->top == -1){
        return 1;
    }else{
        return 0;
    }
}
//入棧
int pushStack(PSeqStack stack,Bnode *node){
    if(stack->top == MAXSIZE-1){
        return 0;
    }else{
        stack->top ++;
        stack->data[stack->top] = node;
        return 1;
    }
}
//出棧
int popStack(PSeqStack stack,BTree *node){
    if(emptyStack(stack) == 1){
        return 0;
    }else{
        *node = stack->data[stack->top];
        stack->top --;
        return 1;
    }
}
//打印元素
void visit(char ch){
    printf("%c \t",ch);
}
 
//二叉樹的建立
BTree createTree(){
    BTree tree;
    dataType str;
    str = getchar();
    if(str == '#'){
        tree = NULL;
    }else{
        tree = (BTree)malloc(sizeof(Bnode));
        tree->data = str;
        tree->lChild = createTree();
        tree->rChild = createTree();
    }
    return tree;
}
//先序遍歷二叉樹
void perOrder(BTree tree){
    PSeqStack stack;
    BTree p = tree;
    stack = initStack();
    while(p || ! emptyStack(stack)){
        if(p){
            visit(p->data);
            pushStack(stack,p);
            p = p->lChild;
        }else{
            popStack(stack,&p);
            p = p->rChild;
        }
    }
} 
//中序遍歷此二叉樹
void inOrder(BTree tree){
    PSeqStack stack;
    BTree p = tree;
    stack = initStack();
    while(p || !emptyStack(stack)){
        if(p){
            pushStack(stack,p);
            p = p->lChild;
        }else{
            popStack(stack,&p);
            visit(p->data);
            p = p->rChild;
        }
    }
}
 
//后序遍歷打印元素
void postOrder(BTree tree){
    PSeqStack s1,s2;
    BTree p = tree;
    s1 = initStack();
    s2 = initStack();
    while(p || !emptyStack(s2)){
        if(p){
            pushStack(s1,p);
            pushStack(s2,p);
            p = p->rChild;
        }else{
            popStack(s2,&p);
            p = p->lChild;
        }
    }
    while(!emptyStack(s1)){
        popStack(s1,&p);
        visit(p->data);
    }
}
//層次遍歷二叉樹
void levelOrder(BTree tree ){
    BTree p = tree;
    PSeqQueue queue = initSeqQueue();
    if(p){
        pushQueue(queue,p);
        while(!emptyQueue(queue)){
            popQueue(queue,&p);
            visit(p->data);
            if(p->lChild){
                pushQueue(queue,p->lChild);
            }
            if(p->rChild){
                pushQueue(queue,p->rChild);
            }
        }
    }
}
//求二叉樹的高度
int height(BTree tree){
    int h1,h2;
    if(tree == NULL){
        return 0;
    }else{
        h1 = height(tree->lChild);
        h2 = height(tree->rChild);
        if(h1>h2){
            return h1+1;
        }else{
            return h2+1;
        }
    }
}
//求解二叉樹每層節(jié)點的個數(shù)
void levelCount(BTree tree,int l,int num[]){
    if(tree){
        num[l]++;
        levelCount(tree->lChild,l+1,num);
        levelCount(tree->rChild,l+1,num);
    }
}
//求解二叉樹節(jié)點總數(shù)
int countTree(BTree tree){
    int lCount,rCount;
    if(tree == NULL){
        return 0;
    }
    lCount = countTree(tree->lChild);
    rCount = countTree(tree->rChild);
    return lCount + rCount +1;
}
 
int main(){
    BTree tree = createTree();
    int i=0;
    int countNum[10]={0,0,0,0,0,0,0,0,0,0},l=1,treeHeight,treeCount;//記錄每層的節(jié)點數(shù),l從1開始,樹的深度
    
    treeHeight = height(tree);
    printf("\n此二叉樹的深度為: %d\n",treeHeight);
 
    treeCount = countTree(tree);
    printf("此二叉樹的節(jié)點總數(shù)為: %d\n",treeCount);
 
    levelCount(tree,l,countNum);
    printf("此二叉樹各層的節(jié)點數(shù)為: ");
    for(i=1;i<=treeHeight;i++){
        printf("第%d層數(shù)目: %d,  ",i,countNum[i]);
    }
    printf("\n\n");
 
    printf("先序遍歷此二叉樹: ");
    perOrder(tree);
    printf("\n");
 
    printf("中序遍歷此二叉樹: ");
    inOrder(tree);
    printf("\n");
 
    printf("后序遍歷此二叉樹: ");
    postOrder(tree);
    printf("\n");
 
    printf("層次遍歷此二叉樹: ");
    levelOrder(tree);
    printf("\n");
    return 0;
}

四关拒、實驗結(jié)果截圖

實驗結(jié)果截圖.png