数据结构编程练习（二叉树）

呦，又写BUG呢

3479人浏览 · 2022-02-16 19:14:24

呦，又写BUG呢 · 2022-02-16 19:14:24 发布

文章目录

1.基于二叉链表的二叉树的遍历
2.基于二叉链表的二叉树高度的计算
3.基于二叉链表的二叉树结点个数的统计
4.基于二叉链表的二叉树左右孩子的交换
5.二叉排序树的判定
6.基于二叉链表的二叉树最大宽度的计算

1.基于二叉链表的二叉树的遍历

描述：设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写三个递归算法分别实现二叉树的先序、中序和后序遍历。

输入样例：
abcd00e00f00ig00h00
abd00e00cf00g00
0

输出样例：
abcdefigh
dcebfagih
decfbghia
abdecfg
dbeafcg
debfgca

在这里插入图片描述

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

#define MAX_SIZE 100

typedef struct BiTNode {
    char data;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

void BiTree_create(BiTree *T, char *node_data, int *cursor);

void pre_order_traverse(BiTree T);

void in_order_traverse(BiTree T);

void post_order_traverse(BiTree T);

void BiTree_free(BiTree T);

int main() {
    char str[MAX_SIZE];

    while (scanf("%s", str) && str[0] != 48) {
        int i = 0;
        BiTree T = NULL;

        BiTree_create(&T, str, &i);

        printf("\n");
        pre_order_traverse(T);//trəˈvɜːs
        printf("\n");
        in_order_traverse(T);
        printf("\n");
        post_order_traverse(T);

        BiTree_free(T);
    }

    return 0;
}

void BiTree_create(BiTree *T, char *node_data, int *cursor) {
    if (node_data[*cursor] == 48) {
        *T = NULL;
    } else {
        *T = (BiTree) malloc(sizeof(BiTNode));
        (*T)->data = node_data[*cursor];

        (*cursor)++;
        BiTree_create(&((*T)->left), node_data, cursor);
        (*cursor)++;
        BiTree_create(&((*T)->right), node_data, cursor);
    }
}

void pre_order_traverse(BiTree T) {
    if (T) {
        printf("%c", T->data);
        pre_order_traverse(T->left);
        pre_order_traverse(T->right);
    }
}

void in_order_traverse(BiTree T) {
    if (T) {
        in_order_traverse(T->left);
        printf("%c", T->data);
        in_order_traverse(T->right);
    }
}

void post_order_traverse(BiTree T) {
    if (T) {
        post_order_traverse(T->left);
        post_order_traverse(T->right);
        printf("%c", T->data);
    }
}

void BiTree_free(BiTree T) {
    if (T) {
        BiTree_free(T->left);
        BiTree_free(T->right);
        free(T);
    }
}

2.基于二叉链表的二叉树高度的计算

描述：设二叉树中每个结点的元素均为一个字节，按先序遍历的顺序建立二叉链表，编写递归算法计算二叉树的高度。

输入样例：
abcd00e00f00ig00h00
abd00e00cf00g00
0

输出样例：
4
3

在这里插入图片描述

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

#define MAX_SIZE 100

typedef struct BiTNode {
    char data;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

void BiTree_create(BiTree *T, char *node_data, int *cursor);

void BiTree_free(BiTree T);

int BiTree_height(BiTree T);

void BiTree_depth(BiTree T, int now_depth, int *max_depth);

int main() {
    char str[MAX_SIZE];

    while (scanf("%s", str) && str[0] != 48) {
        BiTree T;
        int i = 0;

        BiTree_create(&T, str, &i);

        /*recursion with return value*/
        printf("\n%d", BiTree_height(T));

        /*recursion without return value*/
        /*int depth = 0;
        BiTree_depth(T, 1, &depth);
        printf("\n%d", depth);*/

        BiTree_free(T);
    }

    return 0;
}

void BiTree_create(BiTree *T, char *node_data, int *cursor) {
    if (node_data[*cursor] == 48) {
        *T = NULL;
    } else {
        *T = (BiTree) malloc(sizeof(BiTNode));
        (*T)->data = node_data[*cursor];

        (*cursor)++;
        BiTree_create(&((*T)->left), node_data, cursor);
        (*cursor)++;
        BiTree_create(&((*T)->right), node_data, cursor);
    }
}

void BiTree_free(BiTree T) {
    if (T) {
        BiTree_free(T->left);
        BiTree_free(T->right);
        free(T);
    }
}
/**
 * calculate height by return value
 * @param T current root node
 * @return height of current node
 */
int BiTree_height(BiTree T) {
    if (T) {
        int l_height = BiTree_height(T->left) + 1;
        int r_height = BiTree_height(T->right) + 1;
        return (l_height > r_height) ? l_height : r_height;
    }
    return 0;
}
/**
 * calculate depth with parameter
 * @param T current root node
 * @param now_depth depth of current node
 * @param max_depth depth of this tree
 */
void BiTree_depth(BiTree T, int now_depth, int *max_depth) {
    if (T) {
        if (now_depth > *max_depth) {
            *max_depth = now_depth;
        }
        BiTree_depth(T->left, now_depth + 1, max_depth);
        BiTree_depth(T->right, now_depth + 1, max_depth);
    }
}

3.基于二叉链表的二叉树结点个数的统计

描述：设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写三个递归算法对二叉树的结点（度为0、1、2）个数进行统计。

输入样例：
abcd00e00f00ig00h00
abd00e00cf00g00
0

输出样例：
5 0 4
4 0 3

在这里插入图片描述

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

#define MAX_SIZE 100

typedef struct BiTNode {
    char data;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

void BiTree_create(BiTree *T, char *node_data, int *cursor);

void BiTree_free(BiTree T);

void post_order_count(BiTree T, int *degree);

int main() {
    char str[MAX_SIZE];
    while (scanf("%s", str) && str[0] != 48) {
        BiTree T;
        int i = 0;
        int degree[3] = {0, 0, 0};

        BiTree_create(&T, str, &i);
        post_order_count(T, degree);
        printf("%c%d%c%d%c%d", 10, degree[0], 32, degree[1], 32, degree[2]);
        BiTree_free(T);
    }

    return 0;
}

void BiTree_create(BiTree *T, char *node_data, int *cursor) {
    if (node_data[*cursor] == 48) {
        *T = NULL;
    } else {
        *T = (BiTree) malloc(sizeof(BiTNode));
        (*T)->data = node_data[*cursor];

        (*cursor)++;
        BiTree_create(&((*T)->left), node_data, cursor);
        (*cursor)++;
        BiTree_create(&((*T)->right), node_data, cursor);
    }
}

void BiTree_free(BiTree T) {
    if (T) {
        BiTree_free(T->left);
        BiTree_free(T->right);
        free(T);
    }
}

void post_order_count(BiTree T, int *degree) {
    if (T) {
        post_order_count(T->left, degree);
        post_order_count(T->right, degree);
        if (T->left == NULL) {
            if (T->right == NULL) {
                degree[0]++;
            } else {
                degree[1]++;
            }
        } else {
            if (T->right == NULL) {
                degree[1]++;
            } else {
                degree[2]++;
            }
        }
    }
}

4.基于二叉链表的二叉树左右孩子的交换

描述：设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写递归算法交换该二叉树的左右孩子。

输入样例：
abcd00e00f00ig00h00
abd00e00cf00g00
0

输出样例：
aihgbfced
acgfbed

在这里插入图片描述

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

#define MAX_SIZE 100

typedef struct BiTNode {
    char data;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

void BiTree_create(BiTree *T, char *node_data, int *cursor);

void BiTree_free(BiTree T);

void BiTree_mirror(BiTree T);

void pre_order_traverse(BiTree T);

int main() {
    char str[MAX_SIZE];
    while (scanf("%s", str) && str[0] != 48) {
        BiTree T;
        int i = 0;

        BiTree_create(&T, str, &i);
        BiTree_mirror(T);
        printf("\n");
        pre_order_traverse(T);
        BiTree_free(T);
    }

    return 0;
}

void BiTree_create(BiTree *T, char *node_data, int *cursor) {
    if (node_data[*cursor] == 48) {
        *T = NULL;
    } else {
        *T = (BiTree) malloc(sizeof(BiTNode));
        (*T)->data = node_data[*cursor];

        (*cursor)++;
        BiTree_create(&((*T)->left), node_data, cursor);
        (*cursor)++;
        BiTree_create(&((*T)->right), node_data, cursor);
    }
}

void BiTree_free(BiTree T) {
    if (T) {
        BiTree_free(T->left);
        BiTree_free(T->right);
        free(T);
    }
}

void BiTree_mirror(BiTree T) {
    if (T) {
        BiTree_mirror(T->left);
        BiTree_mirror(T->right);

        BiTNode *tmp = T->left;
        T->left = T->right;
        T->right = tmp;
    }
}

void pre_order_traverse(BiTree T) {
    if (T) {
        printf("%c", T->data);
        pre_order_traverse(T->left);
        pre_order_traverse(T->right);
    }
}

5.二叉排序树的判定

描述：假设二叉树每个结点的元素均为一个单字符，根据给定的字符序列按照先序遍历的顺序递归创建该树的二叉链表，然后判断该二叉树是否为二叉排序树。

输入样例：
ba##c##
ca##b##
#

输出样例：
YES
NO

在这里插入图片描述

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

#define MAX_SIZE 100

typedef struct BiTNode {
    char data;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

void BiTree_create(BiTree *T, char *node_data, int *cursor);

void BiTree_free(BiTree T);

bool is_BST(BiTree T, int last_value);

int main() {
    char str[MAX_SIZE];
    while (scanf("%s", str) && str[0] != 35) {
        BiTree T;
        int i = 0;

        BiTree_create(&T, str, &i);
        if (is_BST(T, INT_MIN)) {
            printf("\nYES");
        } else {
            printf("\nNO");
        }
        BiTree_free(T);
    }

    return 0;
}

void BiTree_create(BiTree *T, char *node_data, int *cursor) {
    if (node_data[*cursor] == 35) {
        *T = NULL;
    } else {
        *T = (BiTree) malloc(sizeof(BiTNode));
        (*T)->data = node_data[*cursor];

        (*cursor)++;
        BiTree_create(&((*T)->left), node_data, cursor);
        (*cursor)++;
        BiTree_create(&((*T)->right), node_data, cursor);
    }
}

void BiTree_free(BiTree T) {
    if (T) {
        BiTree_free(T->left);
        BiTree_free(T->right);
        free(T);
    }
}
/**
 * judge whether the middle sequence is an increasing sequence
 * @param T current root node
 * @param last_value the value of the last visited node
 * @return whether tree T is a BST
 */
bool is_BST(BiTree T, int last_value) {
    if (T) {
        /*judge left subtree*/
        if (!is_BST(T->left, last_value))
            return false;
        /*judge middle order sequence*/
        if (T->data <= last_value)
            return false;
        last_value = T->data;
        /*judge right subtree*/
        if (!is_BST(T->right, last_value))
            return false;
    }
    return true;
}

/**
 * according to the definition of BST
 * @param T current root node
 * @return whether tree T is a BST
 */
bool is_BST(BiTree T) {
    if (T) {
        if (!is_BST(T->left))
            return false;
        if (!is_BST(T->right))
            return false;
        if (!(left_subtree_max_value(T) < T->data && T->data < right_subtree_min_value(T)))
            return false;
    }
    return true;
}

int right_subtree_min_value(BiTree T) {
    if (T->right == NULL) {
        return INT_MAX;
    }
    T = T->right;
    while (T->left != NULL) {
        T = T->left;
    }
    return T->data;
}

int left_subtree_max_value(BiTree T) {
    if (T->left == NULL) {
        return INT_MIN;
    }
    T = T->left;
    while (T->right != NULL) {
        T = T->right;
    }
    return T->data;
}

6.基于二叉链表的二叉树最大宽度的计算

描述：设二叉树中每个结点的元素均为一个字符，按先序便利的顺序建立二叉链表，编写算法计算该二叉树的最大宽度。
说明：最大宽度是指二叉树所有层中结点个数的最大值。

输入样例：
abcd00e00f00ig00h00
abd00e00cf00g00
0

输出样例：
4
4

在这里插入图片描述

通过层次遍历依次统计每层宽度。

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

#define MAX_SIZE 100
#define ElemType BiTree

typedef struct BiTNode {
    char data;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

typedef struct SqQueue {
    ElemType data[MAX_SIZE];
    int front, rear;
} SqQueue;

/*Binary Tree Part*/
void CreateBiTree(BiTree *T, char *node_data, int *cursor);

void FreeBiTree(BiTree T);

int GetBiTreeWidth(BiTree T);

/*Queue Part*/
void InitQueue(SqQueue *Q);

bool IsEmptyQueue(SqQueue Q);

void EnQueue(SqQueue *Q, ElemType e);

ElemType DeQueue(SqQueue *Q);

int main() {
    char str[MAX_SIZE];
    while (scanf("%s", str) && str[0] != 48) {
        BiTree T = NULL;
        int i = 0;

        CreateBiTree(&T, str, &i);
        printf("\n%d", GetBiTreeWidth(T));
        FreeBiTree(T);
    }

    return 0;
}

void CreateBiTree(BiTree *T, char *node_data, int *cursor) {
    if (node_data[*cursor] == 48) {
        (*T) = NULL;
    } else {
        (*T) = (BiTree) malloc(sizeof(BiTNode));
        (*T)->data = node_data[*cursor];

        (*cursor)++;
        CreateBiTree(&((*T)->left), node_data, cursor);
        (*cursor)++;
        CreateBiTree(&((*T)->right), node_data, cursor);
    }
}

void FreeBiTree(BiTree T) {
    if (T) {
        FreeBiTree(T->left);
        FreeBiTree(T->right);
        free(T);
    }
}
/**
 * count width by level order traverse
 * @param T 
 * @return 
 */
int GetBiTreeWidth(BiTree T) {
    int max_width = 0;//max width
    int next_level_width = 0;//width of next level
    int remaining = 1;//number of remaining nodes in this level
    BiTree now_node = NULL;//currently accessed node
    SqQueue Q;//access queue

    InitQueue(&Q);
    EnQueue(&Q, T);

    while (!IsEmptyQueue(Q)) {
        now_node = DeQueue(&Q);
        remaining--;
        if (now_node->left) {
            EnQueue(&Q, now_node->left);
            next_level_width++;
        }
        if (now_node->right) {
            EnQueue(&Q, now_node->right);
            next_level_width++;
        }
        if (!remaining) {//access of nodes in this level is completed
            max_width = (next_level_width > max_width) ? next_level_width
                                                       : max_width;
            /*prepare for access to the next level*/
            remaining = next_level_width;
            next_level_width = 0;
        }
    }

    return max_width;
}

void InitQueue(SqQueue *Q) {
    Q->front = Q->rear = 0;
}

bool IsEmptyQueue(SqQueue Q) {
    return (Q.rear == Q.front) ? true : false;
}

void EnQueue(SqQueue *Q, ElemType e) {
    if ((Q->rear + 1) % MAX_SIZE == Q->front)
        return;//the queue is full

    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAX_SIZE;
    return;
}

ElemType DeQueue(SqQueue *Q) {
    if (IsEmptyQueue(*Q))
        return NULL;//the queue is empty

    ElemType tmp = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_SIZE;
    return tmp;
}

通过任意遍历将每层结点数记录在数组中，最后查找数组中的最大值。

/**
 * count width by the depth every node
 * @param T
 * @param now_depth
 * @param depth_count
 * @return
 */
int GetBiTreeWidth(BiTree T, int now_depth, int *depth_count) {
    if (T) {
        depth_count[now_depth]++;
        GetBiTreeWidth(T->left, now_depth + 1, depth_count);
        GetBiTreeWidth(T->right, now_depth + 1, depth_count);
    }
}

int main() {
    char str[MAX_SIZE];
    while (scanf("%s", str) && str[0] != 48) {
        int depth_count[MAX_SIZE] = {0};
        BiTree T = NULL;
        int i = 0;
        int max = INT_MIN;

        CreateBiTree(&T, str, &i);
        GetBiTreeWidth(T, 1, depth_count);
        for (int j = 0; j < MAX_SIZE; j++) {
            max = (depth_count[j] > max) ? depth_count[j] : max;
        }
        printf("\n%d", max);
        FreeBiTree(T);
    }

    return 0;
}

以上为定义的二叉树最大宽度，实际中如果想要查找二叉树中最左结点与最右结点的横向距离，只需要从根结点分别向左向右查找。

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

#define MAX_SIZE 100

typedef struct BiTNode {
    int data;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

void BiTreeCreate(BiTree *root, char *node_data, int *cursor);
void BiTreeDestroy(BiTree *root);
int GetMaxWidth(BiTree T);

int main() {
    char str[MAX_SIZE] = "";
    BiTree T;
    int i = 0;

    while (scanf("%[^\n]%*c", str) && str[0] != '0') {
        BiTreeCreate(&T, str, &i);
        printf("%d\n", GetMaxWidth(T));
        BiTreeDestroy(&T);
    }
    return 0;
}

void BiTreeCreate(BiTree *root, char *node_data, int *cursor) {
    if (node_data[*cursor] == '0') {
        *root = NULL;
    } else {
        *root = (BiTree) malloc(sizeof(BiTNode));

        (*root)->data = node_data[*cursor];
        (*cursor)++;
        BiTreeCreate(&((*root)->left), node_data, cursor);
        (*cursor)++;
        BiTreeCreate(&((*root)->right), node_data, cursor);
    }
}

void BiTreeDestroy(BiTree *root) {
    while (*root) {
        BiTreeDestroy(&(*root)->left);
        BiTreeDestroy(&(*root)->right);
        free(*root);
        *root = NULL;
    }
}

int GetMaxWidth(BiTree T) {
    BiTNode *cursor;
    int width = 0;

    for (cursor = T; cursor->left; cursor = cursor->left) width++;
    for (cursor = T; cursor->right; cursor = cursor->right) width++;
    return width;
}

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

小参数・大码力・易部署 | Qwen3.6-27B上线魔乐社区，基于昇腾的部署教程来了

继一周前模型开源发布后，千问再度开源Qwen3.6-27B —— 一个拥有270亿参数的稠密多模态模型，也是社区呼声最高的模型规格。Qwen3.6-27B 依然支持多模态思考与非思考模式，在智能体编程方面达到了旗舰级表现，全面超越前代开源旗舰 Qwen3.5-397B-A17B（总参数397B / 激活参数17B的MoE模型）。作为稠密架构，它无需MoE路由即可部署，是开发者在实用、可广泛部署规模