c语言构建一个二叉树

在C语言中，可以使用结构体来构建一个二叉树。首先，我们需要定义一个二叉树结构体，其中包含一个数据域和左右子树的指针域。例如，可以使用以下代码定义一个二叉树的结构体：

typedef struct binary_tree {
    int data;  // 节点保存的数据
    struct binary_tree* left;  // 定义左节点指针
    struct binary_tree* right;  // 定义右节点指针
} node;

上述代码定义了一个名为`binary_tree`的结构体，其中包含了一个整数类型的数据域`data`，以及左右子树的指针域`left`和`right`。这样就成功地构建了一个二叉树的结构。

接下来，我们可以根据需要编写相应的函数来构建二叉树。例如，可以编写一个函数来插入新节点、构建二叉树的前序遍历、中序遍历或后序遍历等。

请注意，以上只是构建二叉树的基本概念和方法，具体的实现取决于你的需求和编码风格。你可以根据自己的实际情况来选择合适的方法来构建二叉树。同时，你可以参考引用和中提供的代码示例来更详细地了解如何使用C语言构建一个二叉树。

相关问题

请用标准c语言构建一个二叉树，要求使用括号表示法输入二叉树并转化为二叉树的链式存储结构；横向输出二叉树；求二叉树的高度；统计二叉树中的节点个数；中序遍历该二叉树（采用递归算法）；层序遍历该二叉树

好的，我来逐一回答你的问题。

首先是构建二叉树。以下是用标准 C 语言实现的二叉树结构体：

typedef struct node {
    char data;              // 节点数据
    struct node *lchild;    // 左子节点
    struct node *rchild;    // 右子节点
} Node, *Tree;

接下来是用括号表示法输入二叉树并转化为二叉树的链式存储结构。输入格式如下：

(A(B(D,E),C(F,G)))

这个表示一个如下图所示的二叉树：

        A
      /   \
     B     C
   /  \   / \
  D    E F   G

下面是转化为链式存储结构的代码：

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

Node *create_tree(char *str, int *index) {
    Node *root = NULL;
    if (str[*index] != '\0' && str[*index] != ')') {
        root = (Node *)malloc(sizeof(Node));
        root->data = str[*index];
        root->lchild = NULL;
        root->rchild = NULL;
        (*index)++;
        if (str[*index] == '(') {
            (*index)++;
            root->lchild = create_tree(str, index);
        }
        if (str[*index] == ',') {
            (*index)++;
            root->rchild = create_tree(str, index);
        }
    }
    (*index)++;
    return root;
}

int main() {
    char str[100];
    int index = 0;
    scanf("%s", str);
    Tree root = create_tree(str, &index);
    return 0;
}

这个函数的返回值是一个二叉树的根节点指针。

接下来是横向输出二叉树。我们可以通过中序遍历二叉树，同时记录每个节点在树中的位置，最后按行输出。这里使用了一个辅助函数 `tree_height` 来计算二叉树的高度：

int tree_height(Tree root) {
    if (root == NULL) {
        return 0;
    }
    int left_height = tree_height(root->lchild);
    int right_height = tree_height(root->rchild);
    return left_height > right_height ? left_height + 1 : right_height + 1;
}

void print_tree(Tree root, int level, int pos[]) {
    if (root == NULL) {
        return;
    }
    pos[level] = pos[level - 1] * 2;
    print_tree(root->lchild, level + 1, pos);
    printf("%*c%c\n", pos[level] - pos[level - 1], ' ', root->data);
    pos[level] = pos[level - 1] * 2 + 1;
    print_tree(root->rchild, level + 1, pos);
}

void print(Tree root) {
    int height = tree_height(root);
    int pos[height];
    for (int i = 0; i < height; i++) {
        pos[i] = 1;
    }
    print_tree(root, 1, pos);
}

接下来是求二叉树的高度。这个函数非常简单，就是递归计算左子树和右子树的高度，然后取较大值加 1：

int tree_height(Tree root) {
    if (root == NULL) {
        return 0;
    }
    int left_height = tree_height(root->lchild);
    int right_height = tree_height(root->rchild);
    return left_height > right_height ? left_height + 1 : right_height + 1;
}

接下来是统计二叉树中的节点个数。这个函数也非常简单，就是递归计算左子树和右子树的节点数，然后加上 1：

int node_count(Tree root) {
    if (root == NULL) {
        return 0;
    }
    int left_count = node_count(root->lchild);
    int right_count = node_count(root->rchild);
    return left_count + right_count + 1;
}

接下来是中序遍历该二叉树（采用递归算法）。中序遍历的顺序是左子树 -> 根节点 -> 右子树，按照这个顺序递归即可：

void inorder_traversal(Tree root) {
    if (root == NULL) {
        return;
    }
    inorder_traversal(root->lchild);
    printf("%c ", root->data);
    inorder_traversal(root->rchild);
}

最后是层序遍历该二叉树。层序遍历需要借助队列来实现。具体实现方法是：先将根节点入队，然后每次从队列中取出一个节点，输出它的值，并将它的左右子节点入队。直到队列为空为止：

void level_order_traversal(Tree root) {
    if (root == NULL) {
        return;
    }
    Queue queue;
    init_queue(&queue);
    enqueue(&queue, root);
    while (!is_empty(&queue)) {
        Node *node = dequeue(&queue);
        printf("%c ", node->data);
        if (node->lchild != NULL) {
            enqueue(&queue, node->lchild);
        }
        if (node->rchild != NULL) {
            enqueue(&queue, node->rchild);
        }
    }
}

以上就是用标准 C 语言实现二叉树的一些常见操作的代码。

C语言写一个二叉树的层序遍历

下面是C语言实现二叉树的层序遍历的代码：

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

//定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

//定义队列节点结构体
typedef struct QueueNode {
    TreeNode *node;
    struct QueueNode *next;
} QueueNode;

//定义队列结构体
typedef struct Queue {
    QueueNode *front;
    QueueNode *rear;
} Queue;

//初始化队列
void initQueue(Queue *queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

//判断队列是否为空
int isEmpty(Queue *queue) {
    return queue->front == NULL;
}

//入队
void enqueue(Queue *queue, TreeNode *node) {
    QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->node = node;
    newNode->next = NULL;
    if (isEmpty(queue)) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

//出队
TreeNode* dequeue(Queue *queue) {
    if (isEmpty(queue)) {
        printf("队列为空\n");
        return NULL;
    } else {
        QueueNode *node = queue->front;
        TreeNode *treeNode = node->node;
        queue->front = queue->front->next;
        if (queue->front == NULL) {
            queue->rear = NULL;
        }
        free(node);
        return treeNode;
    }
}

//层序遍历
void levelOrder(TreeNode *root) {
    Queue *queue = (Queue*)malloc(sizeof(Queue));
    initQueue(queue);
    enqueue(queue, root);
    while (!isEmpty(queue)) {
        TreeNode *node = dequeue(queue);
        printf("%d ", node->val);
        if (node->left) {
            enqueue(queue, node->left);
        }
        if (node->right) {
            enqueue(queue, node->right);
        }
    }
}

int main() {
    //构建二叉树
    TreeNode *node1 = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode *node2 = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode *node3 = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode *node4 = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode *node5 = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode *node6 = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode *node7 = (TreeNode*)malloc(sizeof(TreeNode));
    node1->val = 1;
    node2->val = 2;
    node3->val = 3;
    node4->val = 4;
    node5->val = 5;
    node6->val = 6;
    node7->val = 7;
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->left = node6;
    node3->right = node7;
    node4->left = NULL;
    node4->right = NULL;
    node5->left = NULL;
    node5->right = NULL;
    node6->left = NULL;
    node6->right = NULL;
    node7->left = NULL;
    node7->right = NULL;

    //层序遍历
    levelOrder(node1);

    return 0;
}

这里使用队列来实现层序遍历。首先将根节点入队，然后循环遍历队列，每次出队一个节点并打印它的值，如果它有左子树，则将左子树入队，如果它有右子树，则将右子树入队。这样可以保证每一层的节点按照从左到右的顺序被访问到。