二叉樹

二叉樹簡介

每個節(jié)點最多只有兩個子節(jié)點的樹稱為二叉樹：


Bitree.png

二叉樹的存儲結(jié)構(gòu)

二叉樹一般用鏈?zhǔn)浇Y(jié)構(gòu)存儲，每個節(jié)點包含兩個指向左右子樹的指針與存儲數(shù)據(jù)的區(qū)域。


struct.png

數(shù)據(jù)結(jié)構(gòu)如下：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode, * Tree;

二叉樹的基本函數(shù)操作

對于一顆二叉樹而言最重要的就是對二叉樹的遍歷操作，因為二叉樹在邏輯上不是線性的，所以如何遍歷一顆二叉樹至關(guān)重要。根據(jù)訪問節(jié)點與其左右子樹的順序可以分為三種遍歷方式（左右子樹都是按照先左后右的順序遍歷）：

  • 先根遍歷（先序遍歷）
  • 中根遍歷（中序遍歷）
  • 后根遍歷（后序遍歷）

對于圖1的二叉樹，先根遍歷的結(jié)果為：ABDGHICEJF ， 其遍歷方式為先訪問當(dāng)前節(jié)點，再訪問當(dāng)前節(jié)點的左子節(jié)點，后訪問當(dāng)前節(jié)點的右子節(jié)點。即當(dāng)前節(jié)點->左子節(jié)點->右子節(jié)點

中根遍歷則按照左子節(jié)點->當(dāng)前節(jié)點->右子節(jié)點的順序遍歷二叉樹。對于圖1的二叉樹，中根遍歷的結(jié)果為：GDIHBAEJCF。

同理，后根遍歷按照左子節(jié)點->右子節(jié)點->當(dāng)前節(jié)點的順序遍歷二叉樹。對于圖1的二叉樹，后根遍歷的結(jié)果為：GIHDBJEFCA。

三種遍歷方式的代碼實現(xiàn)

void preOrderTraverse(Tree root){
    if (root) {
        printf("%d ", root->val);
        midOrderTraverse(root->left);
        midOrderTraverse(root->right);
    }
}

void midOrderTraverse(Tree root){
    if (root) {
        midOrderTraverse(root->left);
        printf("%d ", root->val);
        midOrderTraverse(root->right);
    }
}

void postOrderTraverse(Tree root){
    if (root) {
        midOrderTraverse(root->left);
        midOrderTraverse(root->right);
        printf("%d ", root->val);
    }
}

二叉樹的構(gòu)造

根據(jù)二叉樹的遍歷方式，我們可以在遍歷的同時創(chuàng)建二叉樹，這里我寫了中根遍歷的構(gòu)造方式。

代碼如下：

void createBitree(Tree& root) {
    int val;
    scanf_s("%d", &val);
    if (val == -1) {
        root = NULL;
    }
    else {
        if (!(root = (TreeNode*)malloc(sizeof(TreeNode))))
            exit(1);
        root->val = val;
        createBitree(root->left);
        createBitree(root->right);
    }
    return;
}

二叉樹的層次遍歷

前面幾種遍歷都是基于深度優(yōu)先的方式對二叉樹進(jìn)行遍歷，而層次遍歷則是基于廣度優(yōu)先的。

對圖1二叉樹進(jìn)行層次結(jié)果為：ABCDEFGHJI。這種遍歷方式更加符合我們?nèi)粘５牧?xí)慣。

算法設(shè)計

對于層次遍歷我們需要按照從左往后、從上往下的順序遍歷每個節(jié)點。先進(jìn)先出的隊列結(jié)構(gòu)可以很好的實現(xiàn)這個操作。

  1. 先將根節(jié)點入隊列

  2. 當(dāng)隊列不為空時，節(jié)點出隊列

  3. 判斷該出隊列節(jié)點是否存在左右子節(jié)點，若存在則按照左右的順序?qū)⒆庸?jié)點入隊列

  4. 當(dāng)隊列為空時遍歷完成


    leveltraverse.png

層次遍歷代碼如下：

void levelTraverse(Tree root) {
    TreeNode* p;
    LinkQueue Q;

    if (root == NULL) {
        return;
    }
    InitQueue(&Q);
    EnQueue(&Q, root);

    while (!EmptyQueue(Q)) { 
        p = DeQueue(&Q);
        printf("%d", p->val);       
        if (p->left) {
            EnQueue(&Q, p->left);
        }
        if (p->right) {
            EnQueue(&Q, p->right);
        }

    }
}

層次遍歷創(chuàng)建二叉樹

我們可以根據(jù)層次遍歷，按照層次遍歷的方式創(chuàng)建一顆二叉樹。

具體代碼如下：

void createBitreeByLevel(Tree& root) {
    int val;
    TreeNode* p = NULL;
    LinkQueue Q;
    InitQueue(&Q);
    
    //先對根節(jié)點進(jìn)行判斷，輸入是否為空
    scanf_s("%d", &val);
    if (val == -1) {
        root = NULL;
        return;
    }
    else {
        if (!(root = (TreeNode*)malloc(sizeof(TreeNode))))
            exit(1);
        root->val = val;
    }
    
    EnQueue(&Q, root);
    while (!EmptyQueue(Q)) {
        p = DeQueue(&Q);
        scanf_s("%d", &val);
        if (val == -1) {
            p->left = NULL;
        }
        else {
            if (!(p->left = (TreeNode*)malloc(sizeof(TreeNode))))
                exit(1);
            p->left->val = val;
            EnQueue(&Q,p->left);
            
        }
        scanf_s("%d", &val);
        if (val == -1) {
            p->right = NULL;
        }
        else {
            if (!(p->right = (TreeNode*)malloc(sizeof(TreeNode))))
                exit(1);
            p->right->val = val;
            EnQueue(&Q, p->right);

        }
    }   
}

完整代碼

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct TreeNode {       //二叉樹節(jié)點數(shù)據(jù)結(jié)構(gòu)
    int val;                    //數(shù)據(jù)區(qū)
    struct TreeNode* left;      //左子樹指針
    struct TreeNode* right;     //右子樹指針
}TreeNode, * Tree;


void createBitree(Tree& root);          //創(chuàng)建二叉樹
void createBitreeByLevel(Tree& root);   //層次遍歷創(chuàng)建二叉樹
void midOrderTraverse(Tree root);       //中序遍歷二叉樹
int maxDepth(struct TreeNode* root);    //計算二叉樹最大深度
void levelTraverse(Tree root);          //層次遍歷二叉樹
void draw(Tree root);                   //簡單畫出二叉樹結(jié)構(gòu)


#define Empty INT_MIN;          //標(biāo)記空
typedef struct Qnode {          //隊列節(jié)點數(shù)據(jù)結(jié)構(gòu)
    TreeNode* t;                //二叉樹指針
    struct Qnode* next;         //下一個節(jié)點
}Qnode, * QueuePtr;

typedef struct LinkQueue {      //隊列結(jié)構(gòu)
    QueuePtr front;             //隊頭指針
    QueuePtr rear;              //隊尾指針
}LinkQueue;

void InitQueue(LinkQueue* Q);               //初始化隊列
void DestoryQueue(LinkQueue* Q);            //銷毀隊列
bool EnQueue(LinkQueue* Q, TreeNode* t);    //新元素進(jìn)插入隊尾
bool EmptyQueue(LinkQueue Q);               //判斷隊列是否為空
TreeNode* DeQueue(LinkQueue* Q);            //隊頭元素出隊列



/***************************************************************************
 * @date    2020/12/09
 * @brief   創(chuàng)建二叉樹
 * @param   root  二叉樹根節(jié)點
 ***************************************************************************/
void createBitree(Tree& root) {
    int val;
    scanf_s("%d", &val);

    if (val == -1) {
        root = NULL;
    }
    else {
        if (!(root = (TreeNode*)malloc(sizeof(TreeNode))))
            exit(1);
        root->val = val;
        createBitree(root->left);
        createBitree(root->right);
    }
    return;
}

/***************************************************************************
 * @date    2020/12/09
 * @brief   中序遍歷二叉樹
 * @param   root  二叉樹根節(jié)點
 ***************************************************************************/
void midOrderTraverse(Tree root) {
    if (root) {
        midOrderTraverse(root->left);
        printf("%d ", root->val);
        midOrderTraverse(root->right);
    }
}


/***************************************************************************
 * @date    2020/12/09
 * @brief   計算二叉樹的最大深度
 * @param   root  二叉樹根節(jié)點
 ***************************************************************************/
#define  max(a,b) (((a)>(b)) ? a : b) 
int maxDepth(struct TreeNode* root) {
    int lDepth, rDepth;
    if (!root) {
        return 0;
    }
    lDepth = maxDepth(root->left);
    rDepth = maxDepth(root->right);
    return 1 + max(lDepth, rDepth);
}



/***************************************************************************
 * @date    2020/12/09
 * @brief   層次遍歷二叉樹
 * @param   root  二叉樹根節(jié)點
 ***************************************************************************/
void levelTraverse(Tree root) {
    TreeNode* p;
    LinkQueue Q;

    if (root == NULL) {
        return;
    }
    InitQueue(&Q);
    EnQueue(&Q, root);

    while (!EmptyQueue(Q)) { 

        p = DeQueue(&Q);
        printf("%d ", p->val);      
        if (p->left) {
            EnQueue(&Q, p->left);
        }
        if (p->right) {
            EnQueue(&Q, p->right);
        }

    }
}


/***************************************************************************
 * @date    2020/12/09
 * @brief   簡單畫出二叉樹結(jié)構(gòu)
 * @param   root  二叉樹根節(jié)點
 ***************************************************************************/
#define MAX_SIZE 100
void draw(Tree root) {
    TreeNode* p;
    LinkQueue Q;
    int n = 0, cur_depth = 1,i,spaceNums = 0;  
    int nums[MAX_SIZE] = { 0 }; //表示每層的節(jié)點個數(shù)
    int maxdepth = maxDepth(root);

    if (root == NULL) {
        return;
    }
    nums[cur_depth] = 1; //第一層節(jié)點個數(shù)
    for (i = 0; i <= maxdepth - cur_depth; i++) {
        spaceNums = spaceNums * 2 + 1;
    }
    for (i = 0; i < spaceNums / 2; i++) {
        printf(" ");
    }
    InitQueue(&Q);
    EnQueue(&Q,root);

    while (!EmptyQueue(Q)) {  //cur_depth 記錄當(dāng)前所在層
        
        p = DeQueue(&Q);
        n++;                //n記錄輸出的節(jié)點數(shù)
        
        printf("%d", p->val);
        for (i = 0; i < spaceNums; i++) {
            printf(" ");
        }
        if (p->left) {
            EnQueue(&Q, p->left);
            nums[cur_depth+1] += 1;
        }
        if (p->right) {
            EnQueue(&Q, p->right);
            nums[cur_depth+1] += 1;
            
        }
        if (n == nums[cur_depth]) { //當(dāng)n等于當(dāng)前層節(jié)點數(shù)時換行輸出，到下一層
            printf("\n");
            n = 0;
            spaceNums = 0;
            cur_depth++;
            for (i = 0; i <= maxdepth - cur_depth; i++) {
                spaceNums = spaceNums * 2 + 1;
            }
            for (i = 0; i < spaceNums / 2; i++) {
                printf(" ");
            }
            
        }

    }
}

/***************************************************************************
 * @date    2020/12/09
 * @brief   層次遍歷創(chuàng)建二叉樹
 * @param   root  二叉樹根節(jié)點
 ***************************************************************************/
void createBitreeByLevel(Tree& root) {
    int val;
    TreeNode* p = NULL;
    LinkQueue Q;
    InitQueue(&Q);

    scanf_s("%d", &val);
    if (val == -1) {
        root = NULL;
        return;
    }
    else {
        if (!(root = (TreeNode*)malloc(sizeof(TreeNode))))
            exit(1);
        root->val = val;
    }

    EnQueue(&Q, root);
    while (!EmptyQueue(Q)) {
        p = DeQueue(&Q);
        scanf_s("%d", &val);
        if (val == -1) {
            p->left = NULL;
        }
        else {
            if (!(p->left = (TreeNode*)malloc(sizeof(TreeNode))))
                exit(1);
            p->left->val = val;
            EnQueue(&Q,p->left);
            
        }
        scanf_s("%d", &val);
        if (val == -1) {
            p->right = NULL;
        }
        else {
            if (!(p->right = (TreeNode*)malloc(sizeof(TreeNode))))
                exit(1);
            p->right->val = val;
            EnQueue(&Q, p->right);

        }
    }   
}

int main() {
    Tree root;
    printf("開始創(chuàng)建二叉樹，請輸入節(jié)點元素，-1 表示為空\n");
    createBitreeByLevel(root);
    printf("層次遍歷創(chuàng)建二叉樹成功\n");
    printf("二叉樹結(jié)構(gòu)如下：\n");
    draw(root);
    printf("中序遍歷結(jié)果：");
    midOrderTraverse(root);
    printf("\n");
    printf("層次遍歷結(jié)果：");
    levelTraverse(root);
    return 1;
    
}

//構(gòu)造一個空隊列Q
void InitQueue(LinkQueue* Q) {
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(Qnode));
    if (!Q->front) {
        exit(1);
    }
    Q->front->next = NULL;
}

//銷毀隊列Q
void DestoryQueue(LinkQueue* Q) {
    while (Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
}

//插入data到Q的隊尾
bool EnQueue(LinkQueue* Q, TreeNode* t) {
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(Qnode));
    if (!p) {
        return false;
    }
    p->t = t;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return true;
}

bool EmptyQueue(LinkQueue Q) {
    if (Q.front == Q.rear) {
        return true;
    }
    else {
        return false;
    }
}

//刪除對頭元素,并返回值
TreeNode* DeQueue(LinkQueue* Q) {
    QueuePtr p;
    TreeNode* result;
    if (EmptyQueue(*Q)) {
        return NULL;
    }
    p = Q->front->next;
    Q->front->next = p->next;
    if (Q->rear == p) {
        Q->rear = Q->front;
    }
    result = p->t;
    free(p);
    return result;
}

測試結(jié)果如下：


result.png
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容