c语言二叉树层次遍历和中序遍历完整代码

以下是C语言二叉树层次遍历和中序遍历的完整代码：

1. 二叉树层次遍历

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

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

// 根据中序遍历和层次遍历构建二叉树
void BuildTree(char *level, char *inorder, BiTree *T) {
    int i;
    int len = strlen(level); // 取得层次遍历长度
    int pos;
    if (len == 0) return;
    char *p = strchr(inorder, level[0]);
    if (p == NULL) // 如果为空则...
        return;
    pos = p - inorder; // 取得根节点在中序遍历中的位置
    (*T) = (TreeNode *)malloc(sizeof(TreeNode));
    (*T)->data = level[0];
    (*T)->left = NULL;
    (*T)->right = NULL;
    BuildTree(level + 1, inorder, &((*T)->left)); // 递归构建左子树
    BuildTree(level + pos + 1, p + 1, &((*T)->right)); // 递归构建右子树
}

// 层次遍历
void LevelOrder(BiTree T) {
    BiTree queue[1000];
    int front = 0, rear = 0;
    if (T == NULL) return;
    queue[rear++] = T;
    while (front != rear) {
        BiTree p = queue[front++];
        printf("%c ", p->data);
        if (p->left != NULL) queue[rear++] = p->left;
        if (p->right != NULL) queue[rear++] = p->right;
    }
}

int main() {
    char level[] = "ABDECFG";
    char inorder[] = "DBEAFCG";
    BiTree T = NULL;
    BuildTree(level, inorder, &T);
    printf("层次遍历结果：");
    LevelOrder(T);
    return 0;
}

2. 二叉树中序遍历

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

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

// 根据中序遍历和层次遍历构建二叉树
void BuildTree(char *level, char *inorder, BiTree *T) {
    int i;
    int len = strlen(level); // 取得层次遍历长度
    int pos;
    if (len == 0) return;
    char *p = strchr(inorder, level[0]);
    if (p == NULL) // 如果为空则...
        return;
    pos = p - inorder; // 取得根节点在中序遍历中的位置
    (*T) = (TreeNode *)malloc(sizeof(TreeNode));
    (*T)->data = level[0];
    (*T)->left = NULL;
    (*T)->right = NULL;
    BuildTree(level + 1, inorder, &((*T)->left)); // 递归构建左子树
    BuildTree(level + pos + 1, p + 1, &((*T)->right)); // 递归构建右子树
}

// 中序遍历
void InOrder(BiTree T) {
    if (T == NULL) return;
    InOrder(T->left);
    printf("%c ", T->data);
    InOrder(T->right);
}

int main() {
    char level[] = "ABDECFG";
    char inorder[] = "DBEAFCG";
    BiTree T = NULL;
    BuildTree(level, inorder, &T);
    printf("中序遍历结果：");
    InOrder(T);
    return 0;
}