C语言写二叉树历遍程序

我不是很清楚关于这个问题，但是我可以提供一些参考资料，例如：《C程序设计语言》（K & R），《C程序设计语言：结构化程序设计》（Brian W. Kernighan），以及《数据结构与算法：C语言描述》（Mark Allen Weiss）。

相关问题

使用c语言 采用二叉链表存储二叉树，并对二叉树进行如下操作：建立一棵二叉树；三种方式遍 历二叉树；求二叉树的深度；输出二叉树所有结点的个数；输出二叉树所有叶子结点的个 数。 要求写出各个算法相应的实现程序。

在C语言中，我们可以使用结构体来表示二叉树节点，然后通过指针相连形成二叉链表。以下是实现一些基本操作的代码示例：

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

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

// 创建新的二叉树节点
TreeNode* createNode(int val) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入节点到二叉链表中
TreeNode* insertNode(TreeNode** root, int val) {
    if (*root == NULL) {
        *root = createNode(val);
    } else if (val < (*root)->val) {
        (*root)->left = insertNode(&(*root)->left, val);
    } else {
        (*root)->right = insertNode(&(*root)->right, val);
    }
    return *root;
}

// 三种遍历方式

// 前序遍历(根-左-右)
void preOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->val); // 先访问根节点
        preOrderTraversal(root->left); // 再遍历左子树
        preOrderTraversal(root->right); // 最后遍历右子树
    }
}

// 中序遍历(左-根-右)
void inOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->val);
        inOrderTraversal(root->right);
    }
}

// 后序遍历(左-右-根)
void postOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        postOrderTraversal(root->left);
        postOrderTraversal(root->right);
        printf("%d ", root->val);
    }
}

// 求二叉树的深度
int maxDepth(TreeNode* root) {
    if (root == NULL) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

// 输出二叉树所有节点的个数
int countNodes(TreeNode* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// 输出二叉树所有叶子结点的个数
int countLeaves(TreeNode* root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1; // 叶子节点判断
    return countLeaves(root->left) + countLeaves(root->right);
}

// 主函数演示上述功能
int main() {
    TreeNode* root = NULL;
    // 假设已经插入了一些节点...

    // 遍历
    printf("前序遍历结果: ");
    preOrderTraversal(root);
    printf("\n");

    printf("中序遍历结果: ");
    inOrderTraversal(root);
    printf("\n");

    printf("后序遍历结果: ");
    postOrderTraversal(root);
    printf("\n");

    printf("最大深度: %d\n", maxDepth(root));
    printf("节点总数: %d\n", countNodes(root));
    printf("叶子节点总数: %d\n", countLeaves(root));

    return 0;
}

请注意，这只是一个基础的实现，实际应用中还需要处理内存分配和释放，以及异常情况等。

用c语言编写一个程序，实现由先序遍历序列以及由中序遍历序列构造一棵 二叉树的功 能。 并 用 后 序 遍 历 验 证

以下是用C语言实现的程序，可以实现由先序遍历序列以及由中序遍历序列构造一棵二叉树的功能，并用后序遍历验证：

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

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

// 根据先序遍历和中序遍历构建二叉树
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    if (preorderSize == 0 || inorderSize == 0) {
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));  // 创建新节点
    root->val = preorder[0];
    int i;
    for (i = 0; i < inorderSize; i++) {
        if (inorder[i] == root->val) {
            break;
        }
    }
    root->left = buildTree(preorder + 1, i, inorder, i);
    root->right = buildTree(preorder + i + 1, preorderSize - i - 1, inorder + i + 1, inorderSize - i - 1);
    return root;
}

// 后序遍历二叉树
void postorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->val);
}

int main() {
    int preorder[] = {1, 2, 4, 5, 3, 6};
    int inorder[] = {4, 2, 5, 1, 3, 6};
    int n = sizeof(preorder) / sizeof(preorder[0]);
    struct TreeNode* root = buildTree(preorder, n, inorder, n);
    printf("后序遍历结果：");
    postorderTraversal(root);
    return 0;
}

这个程序的主要思路是根据先序遍历和中序遍历构建二叉树，然后用后序遍历验证。在构建二叉树时，我们首先根据先序遍历序列确定根节点，然后在中序遍历序列中定位根节点的位置，将序列分为左子树和右子树两部分，然后递归地构建左子树和右子树。最后，我们用后序遍历验证二叉树是否正确构建。

在本程序中，我们使用了一个结构体`TreeNode`来定义二叉树节点，并实现了两个函数：`buildTree`和`postorderTraversal`。`buildTree`函数用于构建二叉树，它接受先序遍历序列和中序遍历序列两个参数，返回二叉树的根节点。`postorderTraversal`函数用于后序遍历二叉树，并将遍历结果输出到控制台。

在主函数中，我们先定义了先序遍历序列和中序遍历序列，并计算序列长度。然后，我们调用`buildTree`函数构建二叉树，并调用`postorderTraversal`函数输出后序遍历结果。最后，程序将返回0，表示正常退出。