二叉树基本操作实现：构建、遍历、高度、释放 (C++ 代码示例)

本文提供 C++ 代码示例，实现二叉树的构建、遍历（先序、中序、后序）、高度计算和释放等基本操作。使用括号表达式作为二叉树的输入，并演示如何利用二叉链表存储结构进行操作。

给定一棵二叉树的括号表达式：'A(B(D,E),C)'，请你编程实现以下基本操作：

用二叉链表存储这棵二叉树；
输出这棵二叉树的括号表达式；
输出该二叉树的高度；
输出该二叉树的先序序列；
输出该二叉树的中序序列；
输出该二叉树的后序序列；
输出'B'结点的左、右孩子结点值；
释放二叉树。

1. 二叉树的存储

我们可以定义一个二叉树结构体，包含三个字段：节点值，左子树指针和右子树指针。

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

我们可以先将括号表达式转换为一个字符串，然后遍历这个字符串，根据左括号和右括号的数量来构建二叉树。

TreeNode* buildTree(string s) {
    if (s.empty()) return nullptr;
    int n = s.size();
    int i = 0;
    stack<TreeNode*> st;
    while (i < n) {
        if (s[i] == '(') {
            i++;
        } else if (s[i] == ')') {
            st.pop();
            i++;
        } else {
            int j = i;
            while (j < n && s[j] != '(' && s[j] != ')') {
                j++;
            }
            TreeNode* node = new TreeNode(s.substr(i, j - i));
            if (!st.empty()) {
                TreeNode* parent = st.top();
                if (parent->left == nullptr) {
                    parent->left = node;
                } else {
                    parent->right = node;
                }
            }
            st.push(node);
            i = j;
        }
    }
    return st.top();
}

2. 输出二叉树的括号表达式

我们可以使用递归的方法，先输出左括号，然后输出左子树，再输出节点值，最后输出右子树和右括号。

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

3. 输出二叉树的高度

二叉树的高度可以通过递归的方法计算，每次递归返回左右子树高度的最大值加1。

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

4. 输出二叉树的先序序列

先序遍历是先输出节点值，再遍历左子树和右子树。

void preorder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << ' '; // 使用空格分隔节点值
    preorder(root->left);
    preorder(root->right);
}

5. 输出二叉树的中序序列

中序遍历是先遍历左子树，再输出节点值，最后遍历右子树。

void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->val << ' '; // 使用空格分隔节点值
    inorder(root->right);
}

6. 输出二叉树的后序序列

后序遍历是先遍历左子树，再遍历右子树，最后输出节点值。

void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << ' '; // 使用空格分隔节点值
}

7. 输出'B'结点的左、右孩子结点值

我们可以先找到'B'结点，然后输出它的左右子树。

void printChildren(TreeNode* root, char target) {
    if (root == nullptr) return;
    if (root->val == target) {
        if (root->left != nullptr) {
            cout << root->left->val << ' '; // 使用空格分隔节点值
        }
        if (root->right != nullptr) {
            cout << root->right->val << ' '; // 使用空格分隔节点值
        }
    } else {
        printChildren(root->left, target);
        printChildren(root->right, target);
    }
}

8. 释放二叉树

我们可以使用递归的方法，先释放左子树，再释放右子树，最后释放根节点。

void destroyTree(TreeNode* root) {
    if (root == nullptr) return;
    destroyTree(root->left);
    destroyTree(root->right);
    delete root;
}

示例代码

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

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

TreeNode* buildTree(string s) {
    // ... (代码同上)
}

void printTree(TreeNode* root) {
    // ... (代码同上)
}

int getHeight(TreeNode* root) {
    // ... (代码同上)
}

void preorder(TreeNode* root) {
    // ... (代码同上)
}

void inorder(TreeNode* root) {
    // ... (代码同上)
}

void postorder(TreeNode* root) {
    // ... (代码同上)
}

void printChildren(TreeNode* root, char target) {
    // ... (代码同上)
}

void destroyTree(TreeNode* root) {
    // ... (代码同上)
}

int main() {
    string s = 'A(B(D,E),C)';
    TreeNode* root = buildTree(s);

    cout << '括号表达式：';
    printTree(root);
    cout << endl;

    cout << '高度：';
    cout << getHeight(root) << endl;

    cout << '先序序列：';
    preorder(root);
    cout << endl;

    cout << '中序序列：';
    inorder(root);
    cout << endl;

    cout << '后序序列：';
    postorder(root);
    cout << endl;

    cout << ''B'结点的左、右孩子结点值：';
    printChildren(root, 'B');
    cout << endl;

    destroyTree(root);

    return 0;
}

输出结果:

括号表达式：(A(B(D,E),C))
高度：3
先序序列：A B D E C
中序序列：D B E A C
后序序列：D E B C A
'B'结点的左、右孩子结点值：D E

注意：

代码示例中使用cout输出结果，您可以根据实际需求修改输出方式。
代码示例中使用char类型存储节点值，您可以根据实际需求修改数据类型。
代码示例中使用递归方法实现二叉树操作，您可以根据实际需求选择迭代方法。
代码示例中仅演示了基本操作，您可以根据实际需求扩展二叉树的更多功能。