C语言数据结构之二叉树详解

什么是二叉树？

二叉树是一种非常常用的数据结构，它具有以下几个特点：

• 在二叉树中，每个节点最多有两个子节点，其中一个称为左子节点，另一个称为右子节点。
• 每个节点都有一个值，这个值可以是任意类型的，比如整数、字符、指针等等。
• 可以使用递归的方式来遍历一个二叉树，具体包括前序遍历、中序遍历和后序遍历。

二叉树的存储方式

二叉树可以使用指针的方式来存储，每个节点包含一个数据域和两个指针域，用于指向该节点的左子节点和右子节点。在C语言中，可以使用结构体来实现二叉树。

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

二叉树的遍历方式

二叉树可以使用递归的方式来遍历，常见的遍历方式包括：

前序遍历

对于当前节点，先访问它本身，然后访问它的左子树，最后访问它的右子树。

void preorder(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    preorder(root->left);
    preorder(root->right);
}

中序遍历

对于当前节点，先访问它的左子树，然后访问它本身，最后访问它的右子树。

void inorder(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->val);
    inorder(root->right);
}

后序遍历

对于当前节点，先访问它的左子树，然后访问它的右子树，最后访问它本身。

void postorder(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->val);
}

二叉树的示例应用

例1：二叉树求深度

int maxDepth(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

例2：二叉树是否对称

bool isSymmetricHelper(struct TreeNode* left, struct TreeNode* right) {
    if (left == NULL && right == NULL) {
        return true;
    }
    if (left == NULL || right == NULL) {
        return false;
    }
    return (left->val == right->val) && 
           isSymmetricHelper(left->left, right->right) && 
           isSymmetricHelper(left->right, right->left);
}

bool isSymmetric(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    return isSymmetricHelper(root->left, root->right);
}

以上就是关于C语言数据结构之二叉树的完整攻略。希望能对大家有所帮助。