c++ 二叉树 创建二叉树 前序中序后序遍历二叉树 计算树的深度 计算叶子结点个数 查找双亲 查找兄弟 代码

二叉树的定义：

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

创建二叉树：

TreeNode* buildTree(vector<int>& inorder, int inStart, int inEnd, vector<int>& preorder, int preStart, int preEnd) {
    if (inStart > inEnd) return nullptr;
    int rootVal = preorder[preStart];
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }
    int len = index - inStart;
    TreeNode* root = new TreeNode(rootVal);
    root->left = buildTree(inorder, inStart, index - 1, preorder, preStart + 1, preStart + len);
    root->right = buildTree(inorder, index + 1, inEnd, preorder, preStart + len + 1, preEnd);
    return root;
}

TreeNode* buildTree(vector<int>& inorder, vector<int>& preorder) {
    return buildTree(inorder, 0, inorder.size() - 1, preorder, 0, preorder.size() - 1);
}

前序遍历：

void preOrder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

中序遍历：

void inOrder(TreeNode* root) {
    if (root == nullptr) return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

后序遍历：

void postOrder(TreeNode* root) {
    if (root == nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

计算树的深度：

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

计算叶子节点个数：

int countLeafNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

查找双亲节点：

TreeNode* getParent(TreeNode* root, TreeNode* child) {
    if (root == nullptr || root == child) return nullptr;
    if (root->left == child || root->right == child) return root;
    TreeNode* parent = getParent(root->left, child);
    if (parent != nullptr) return parent;
    return getParent(root->right, child);
}

查找兄弟节点：

TreeNode* getSibling(TreeNode* root, TreeNode* child) {
    if (root == nullptr || root == child) return nullptr;
    if (root->left == child) return root->right;
    if (root->right == child) return root->left;
    TreeNode* sibling = getSibling(root->left, child);
    if (sibling != nullptr) return sibling;
    return getSibling(root->right, child);
}

注意：以上代码仅供参考，实际使用中需要根据具体情况进行修改和适配。