二叉树的基本操作c++

二叉树是一种非常常见的数据结构，它由一个根节点以及每个节点最多有两个子节点组成。以下是二叉树的基本操作及其c++代码实现：

1. 创建一个二叉树

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

2. 二叉树的遍历（前序遍历、中序遍历、后序遍历）

// 前序遍历
void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

// 后序遍历
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
}

3. 求二叉树的深度

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

4. 判断是否为平衡二叉树

bool isBalanced(TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    if (abs(leftDepth - rightDepth) > 1) {
        return false;
    }
    return isBalanced(root->left) && isBalanced(root->right);
}

5. 判断是否为对称二叉树

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

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