二叉树

作者: 骑猪满天飞 | 来源:发表于2020-12-10 09:22 被阅读0次

数据结构与算法-二叉树02
二叉树
二叉树基础操作
树与二叉树
二叉树的宽度优先搜索（层次遍历，BFS）
剑指 offer：39、平衡二叉树
Algorithm小白入门 -- 二叉树
14-树&二叉树&真二叉树&满二叉树
二叉树的应用
12.树Tree（2）

二叉树简介

每个节点最多只有两个子节点的树称为二叉树：

Bitree.png

二叉树的存储结构

二叉树一般用链式结构存储，每个节点包含两个指向左右子树的指针与存储数据的区域。

struct.png

数据结构如下：

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

二叉树的基本函数操作

对于一颗二叉树而言最重要的就是对二叉树的遍历操作，因为二叉树在逻辑上不是线性的，所以如何遍历一颗二叉树至关重要。根据访问节点与其左右子树的顺序可以分为三种遍历方式（左右子树都是按照先左后右的顺序遍历）：

先根遍历（先序遍历）
中根遍历（中序遍历）
后根遍历（后序遍历）

对于图1的二叉树，先根遍历的结果为：ABDGHICEJF ，其遍历方式为先访问当前节点，再访问当前节点的左子节点，后访问当前节点的右子节点。即当前节点->左子节点->右子节点

中根遍历则按照左子节点->当前节点->右子节点的顺序遍历二叉树。对于图1的二叉树，中根遍历的结果为：GDIHBAEJCF。

同理，后根遍历按照左子节点->右子节点->当前节点的顺序遍历二叉树。对于图1的二叉树，后根遍历的结果为：GIHDBJEFCA。

三种遍历方式的代码实现

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);
    }
}

二叉树的构造

根据二叉树的遍历方式，我们可以在遍历的同时创建二叉树，这里我写了中根遍历的构造方式。

代码如下：

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;
}

二叉树的层次遍历

前面几种遍历都是基于深度优先的方式对二叉树进行遍历，而层次遍历则是基于广度优先的。

对图1二叉树进行层次结果为：ABCDEFGHJI。这种遍历方式更加符合我们日常的习惯。

算法设计

对于层次遍历我们需要按照从左往后、从上往下的顺序遍历每个节点。先进先出的队列结构可以很好的实现这个操作。

先将根节点入队列
当队列不为空时，节点出队列
判断该出队列节点是否存在左右子节点，若存在则按照左右的顺序将子节点入队列
当队列为空时遍历完成

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);
        }

    }
}

层次遍历创建二叉树

我们可以根据层次遍历，按照层次遍历的方式创建一颗二叉树。

具体代码如下：

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);

        }
    }   
}

完整代码

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

typedef struct TreeNode {       //二叉树节点数据结构
    int val;                    //数据区
    struct TreeNode* left;      //左子树指针
    struct TreeNode* right;     //右子树指针
}TreeNode, * Tree;


void createBitree(Tree& root);          //创建二叉树
void createBitreeByLevel(Tree& root);   //层次遍历创建二叉树
void midOrderTraverse(Tree root);       //中序遍历二叉树
int maxDepth(struct TreeNode* root);    //计算二叉树最大深度
void levelTraverse(Tree root);          //层次遍历二叉树
void draw(Tree root);                   //简单画出二叉树结构


#define Empty INT_MIN;          //标记空
typedef struct Qnode {          //队列节点数据结构
    TreeNode* t;                //二叉树指针
    struct Qnode* next;         //下一个节点
}Qnode, * QueuePtr;

typedef struct LinkQueue {      //队列结构
    QueuePtr front;             //队头指针
    QueuePtr rear;              //队尾指针
}LinkQueue;

void InitQueue(LinkQueue* Q);               //初始化队列
void DestoryQueue(LinkQueue* Q);            //销毁队列
bool EnQueue(LinkQueue* Q, TreeNode* t);    //新元素进插入队尾
bool EmptyQueue(LinkQueue Q);               //判断队列是否为空
TreeNode* DeQueue(LinkQueue* Q);            //队头元素出队列



/***************************************************************************
 * @date    2020/12/09
 * @brief   创建二叉树
 * @param   root  二叉树根节点
 ***************************************************************************/
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  二叉树根节点
 ***************************************************************************/
void midOrderTraverse(Tree root) {
    if (root) {
        midOrderTraverse(root->left);
        printf("%d ", root->val);
        midOrderTraverse(root->right);
    }
}


/***************************************************************************
 * @date    2020/12/09
 * @brief   计算二叉树的最大深度
 * @param   root  二叉树根节点
 ***************************************************************************/
#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  二叉树根节点
 ***************************************************************************/
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   简单画出二叉树结构
 * @param   root  二叉树根节点
 ***************************************************************************/
#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 }; //表示每层的节点个数
    int maxdepth = maxDepth(root);

    if (root == NULL) {
        return;
    }
    nums[cur_depth] = 1; //第一层节点个数
    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 记录当前所在层
        
        p = DeQueue(&Q);
        n++;                //n记录输出的节点数
        
        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]) { //当n等于当前层节点数时换行输出，到下一层
            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   层次遍历创建二叉树
 * @param   root  二叉树根节点
 ***************************************************************************/
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("开始创建二叉树，请输入节点元素，-1 表示为空\n");
    createBitreeByLevel(root);
    printf("层次遍历创建二叉树成功\n");
    printf("二叉树结构如下：\n");
    draw(root);
    printf("中序遍历结果：");
    midOrderTraverse(root);
    printf("\n");
    printf("层次遍历结果：");
    levelTraverse(root);
    return 1;
    
}

//构造一个空队列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;
}

测试结果如下：

result.png