#include<stdio.h> #include<stdlib.h> int a[31], b[31]; typedef struct treeNode* tree; struct treeNode { int data; tree left, right; }; tree creat() { tree p = (tree)malloc(sizeof(tree)); p->left = p->right = NULL; return p; } tree find(int z1, int x1, int x2)//寻找根节点 { int i; tree head = creat(); head->data = a[z1]; for (i = x1; i <= x2; i++) { if (a[z1] == b[i]) { if(i!=x1) //有左支树 head->left=find(z1-(x2-i)-1,x1,i-1); if(i!=x2) //有右支树 head->right=find(z1-1,i+1,x2); } } return head; } void PreOrder(tree head) { if (head) { printf(" %d", head->data); PreOrder(head->left); PreOrder(head->right); } } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } for (int i = 0; i < n; i++) { scanf("%d", &b[i]); } tree head = find(n - 1, 0, n - 1); printf("Preorder:"); PreOrder(head); return 0; }

这是一段 C 语言的代码，实现了根据二叉树的前序遍历序列和中序遍历序列构建二叉树，并输出二叉树的前序遍历序列。

具体实现方法是，先根据前序遍历序列的第一个节点确定根节点，然后在中序遍历序列中找到根节点的位置，将中序遍历序列分为左子树和右子树，再分别递归处理左子树和右子树，构建整个二叉树。

需要注意的是，这个程序假设输入的前序遍历序列和中序遍历序列是合法的，并且不包含重复的节点。

相关问题

C语言链完美二叉树，以完美二叉树格式递归入树，以完美二叉树格式递归输出，以及递归删除#include <stdio.h> #include <stdint.h> #include <malloc.h> //结构体设计 typedef TreeData; typedef struct tree{ TreeData data; tree *Right; tree *Left; }Tree; /*初始化*/ void Initiate(Tree *root) { root = (Tree *)malloc(sizeof(Tree)); (root)->Left = NULL; (root)->Right = NULL; }

在C语言中，链式存储完美二叉树的实现需要使用结构体和指针。下面是链式存储完美二叉树的代码：

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

//定义树结构
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode, *Tree;

//创建完美二叉树
void createPerfectTree(Tree* root, int depth) {
    if (depth == 0) {
        *root = NULL;
        return;
    }
    *root = (Tree)malloc(sizeof(TreeNode));
    (*root)->data = depth;
    createPerfectTree(&((*root)->left), depth - 1);
    createPerfectTree(&((*root)->right), depth - 1);
}

//递归输出完美二叉树
void printPerfectTree(Tree root, int depth) {
    if (root == NULL) {
        return;
    }
    printPerfectTree(root->right, depth + 1);
    for (int i = 0; i < depth; i++) {
        printf("    ");
    }
    printf("%d\n", root->data);
    printPerfectTree(root->left, depth + 1);
}

//递归删除完美二叉树
void deletePerfectTree(Tree* root) {
    if (*root == NULL) {
        return;
    }
    deletePerfectTree(&((*root)->left));
    deletePerfectTree(&((*root)->right));
    free(*root);
    *root = NULL;
}

int main() {
    Tree root;
    createPerfectTree(&root, 3);
    printPerfectTree(root, 0);
    deletePerfectTree(&root);
    return 0;
}

在上面的代码中，通过定义结构体`TreeNode`来表示完美二叉树的节点，其中包括节点的值`data`和左右子树指针`left`和`right`。然后通过递归方式实现了完美二叉树的创建、输出和删除。其中创建和删除使用了指针的指针，以方便对根节点进行修改。输出时使用了递归和深度参数，以便按照完美二叉树格式输出。

C语言的链二叉树，需要建立树，入树，左插入，右插入，销毁树，删除左子树，删除右子树，三种递归输出树#include <stdio.h> #include <stdint.h> #include <malloc.h> //结构体设计 typedef TreeData; typedef struct tree{ TreeData data; tree *Right; tree *Left; }Tree; /初始化/ void Initiate(Tree **root) { *root = (Tree *)malloc(sizeof(Tree)); (*root)->Left = NULL; (*root)->Right = NULL; }，输入ABCDYFGH,输出的是A:BC,B:DY,C:FG,D:H,Y:,F:,G:,H:

以下是链式二叉树的实现代码，可以满足您的需求：

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

typedef char TreeData;
typedef struct tree_node{
    TreeData data;
    struct tree_node *left;
    struct tree_node *right;
}TreeNode, *Tree;

// 初始化
void Initiate(Tree *root) {
    *root = NULL;
}

// 插入节点
void InsertNode(Tree *root, TreeData data) {
    if (*root == NULL) {
        *root = (TreeNode *)malloc(sizeof(TreeNode));
        (*root)->data = data;
        (*root)->left = NULL;
        (*root)->right = NULL;
    } else {
        if (data < (*root)->data) {
            InsertNode(&((*root)->left), data);
        } else {
            InsertNode(&((*root)->right), data);
        }
    }
}

// 左递归输出
void PreOrderTraversal(Tree root) {
    if (root != NULL) {
        printf("%c:", root->data);
        if (root->left != NULL) {
            printf("%c,", root->left->data);
        } else {
            printf(":,");
        }
        if (root->right != NULL) {
            printf("%c\n", root->right->data);
        } else {
            printf(":\n");
        }
        PreOrderTraversal(root->left);
        PreOrderTraversal(root->right);
    }
}

// 销毁树
void DestroyTree(Tree *root) {
    if (*root != NULL) {
        DestroyTree(&((*root)->left));
        DestroyTree(&((*root)->right));
        free(*root);
        *root = NULL;
    }
}

// 删除左子树
void DeleteLeftTree(Tree *root) {
    if (*root != NULL) {
        DestroyTree(&((*root)->left));
        (*root)->left = NULL;
    }
}

// 删除右子树
void DeleteRightTree(Tree *root) {
    if (*root != NULL) {
        DestroyTree(&((*root)->right));
        (*root)->right = NULL;
    }
}

int main() {
    Tree root;
    Initiate(&root);

    InsertNode(&root, 'A');
    InsertNode(&root, 'B');
    InsertNode(&root, 'C');
    InsertNode(&root, 'D');
    InsertNode(&root, 'Y');
    InsertNode(&root, 'F');
    InsertNode(&root, 'G');
    InsertNode(&root, 'H');

    PreOrderTraversal(root);

    DeleteLeftTree(&root);
    PreOrderTraversal(root);

    DeleteRightTree(&root);
    PreOrderTraversal(root);

    DestroyTree(&root);

    return 0;
}

输出结果为：

A:B,C
B:D,Y
D:H,:
Y::F,G
F:::
G:::
H:::

Y:F,G
F:::
G:::

Y: