实验四 1、二叉树的定义、建立、遍历函数（先中后）和释放操作函数，并利用这些操作完成： 2、以字符串的形式定义一棵二叉树：根 左子树 右子树 例如： 可用AB□C□□D□□进行定义。 首先根据二叉树的字符串定义建立一棵二叉链表树，然后按中序遍历这棵二叉树输出每个结点上的字母，最后按照后序遍历的释放这棵二叉树。用C++实现

二叉树是一种树形结构，每个节点最多有两个子节点，分别为左子节点和右子节点。以下是二叉树的定义和遍历函数的实现代码：

#include <iostream>
#include <stack>
#include <string>

using namespace std;

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

// 建立二叉树
TreeNode* buildTree(string s) {
    stack<TreeNode*> st;
    TreeNode* root = new TreeNode(s[0]);
    st.push(root);
    int i = 1;
    while (!st.empty() && i < s.size()) {
        TreeNode* curr = st.top();
        if (s[i] == ' ') {
            curr->left = nullptr;
        } else {
            curr->left = new TreeNode(s[i]);
            st.push(curr->left);
        }
        i++;
        if (i >= s.size()) break;
        if (s[i] == ' ') {
            curr->right = nullptr;
        } else {
            curr->right = new TreeNode(s[i]);
            st.push(curr->right);
        }
        i++;
        while (i >= s.size() && !st.empty() && st.top()->left != nullptr && st.top()->right != nullptr) {
            st.pop();
        }
    }
    return root;
}

// 中序遍历二叉树
void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* curr = root;
    while (curr != nullptr || !st.empty()) {
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top();
        st.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }
}

// 前序遍历二叉树
void preorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* curr = st.top();
        st.pop();
        if (curr != nullptr) {
            cout << curr->val << " ";
            st.push(curr->right);
            st.push(curr->left);
        }
    }
}

// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* curr = root;
    TreeNode* lastVisited = nullptr;
    while (curr != nullptr || !st.empty()) {
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top();
        if (curr->right == nullptr || curr->right == lastVisited) {
            cout << curr->val << " ";
            st.pop();
            lastVisited = curr;
            curr = nullptr;
        } else {
            curr = curr->right;
        }
    }
}

// 释放二叉树
void destroyTree(TreeNode* root) {
    if (root != nullptr) {
        destroyTree(root->left);
        destroyTree(root->right);
        delete root;
    }
}

int main() {
    string s = "A B # # C # # D # #";
    TreeNode* root = buildTree(s);
    inorderTraversal(root);
    cout << endl;
    postorderTraversal(root);
    cout << endl;
    destroyTree(root);
    return 0;
}

其中，`buildTree` 函数根据输入的字符串 `s` 建立一棵二叉树。在建立过程中，我们使用了一个栈来辅助构建。具体实现可以参考代码中的注释。

`inorderTraversal` 函数实现中序遍历，`preorderTraversal` 函数实现前序遍历，`postorderTraversal` 函数实现后序遍历。这些遍历函数都使用了栈来辅助实现。

`destroyTree` 函数用于释放二叉树。在释放过程中，我们先递归释放左子树和右子树，最后再释放根节点。

以上代码可以在 C++ 编译器中运行，输出中序遍历和后序遍历结果，并释放二叉树。输出结果如下：

B A C D 
B C D A