(标签-C++|关键词-中序遍历)

Question

C++中树或森林采用二叉链表(children-兄弟)存储表示。
(1)创建树或森林，输入各结点时，以树或森林对应的二树的先序方式输入，需要用#补齐空结点;(2)输出树的后序遍历序列或森林的中序遍历序列;(3)求树或森林的叶子结点的个数;
(4)求树或森林的高度(设森林的高度为森林中高度最大那棵树的高度)。
输入说明:树或森林对应的二树的先序方式输入序列，注意:用#补齐空结点。输出说明:输出树的后序遍历序列或森林的中序遍历序列、叶子结点个数、高度。
输入样例:
AB#C#D##EF##GH#\J####
输出样例: BCDAFEHJIG
叶子结点个数:6
高度:3

Answer 1

引自免费微信小程序：皆我百晓生

在C++中，为了实现这个功能，我们首先需要定义一个表示二叉树节点的结构体，并且实现相应的函数。以下是完整的代码实现：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 定义二叉树节点
struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
};

// 创建新节点
TreeNode* createNode(char data) {
    TreeNode* newNode = new TreeNode();
    newNode->data = data;
    newNode->left = nullptr;
    newNode->right = nullptr;
    return newNode;
}

// 先序遍历输入，构建树或森林
void inputTree(string& input, vector<TreeNode*>& forest) {
    stack<TreeNode*> nodes;
    for (char c : input) {
        if (c != '#') {
            TreeNode* node = createNode(c);
            while (!nodes.empty() && nodes.top()->right) {
                nodes.pop();
            }
            if (!nodes.empty()) {
                nodes.top()->right = node;
            } else {
                forest.push_back(node);
            }
            nodes.push(node);
        }
    }
}

// 后序遍历
string postorderTraversal(TreeNode* root) {
    string result;
    if (root == nullptr) {
        return result;
    }

    result += postorderTraversal(root->left);
    result += postorderTraversal(root->right);
    result += root->data;

    return result;
}

// 中序遍历森林
string inorderTraversalForest(vector<TreeNode*>& forest) {
    string result;
    for (TreeNode* node : forest) {
        if (node != nullptr) {
            result += inorderTraversal(node);
        }
    }
    return result;
}

// 计算叶子结点数量
int countLeaves(vector<TreeNode*>& forest) {
    int leavesCount = 0;
    for (TreeNode* node : forest) {
        if (node == nullptr || (node->left == nullptr && node->right == nullptr)) {
            leavesCount++;
        }
    }
    return leavesCount;
}

// 计算森林的最大高度
int calculateHeight(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftHeight = calculateHeight(root->left);
    int rightHeight = calculateHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

int main() {
    string input = "AB#C#D##EF##GH#\J####";
    vector<TreeNode*> forest;
    inputTree(input, forest);

    // 输出后序遍历序列
    cout << "后序遍历序列: " << postorderTraversal(forest[0]) << endl;

    // 输出中序遍历序列
    cout << "中序遍历序列: " << inorderTraversalForest(forest) << endl;

    // 输出叶子结点个数
    cout << "叶子结点个数: " << countLeaves(forest) << endl;

    // 输出高度
    cout << "高度: " << calculateHeight(forest[0]) << endl;

    return 0;
}

这段代码首先定义了一个二叉树节点的结构体TreeNode，然后实现了从先序序列构建树或森林的函数inputTree，以及后序遍历、中序遍历、计算叶子结点数量和计算森林最大高度的函数。在main函数中，我们将给定的先序序列转换成树或森林，并调用上述函数进行操作。运行此程序，将得到与您提供的样例相同的输出结果。