这里是11.1随笔。
题目留档:二叉树遍历应用
代码:#include
include
// 二叉树节点结构体
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
// 根据先序遍历字符串构建二叉树
TreeNode* buildTree(std::string preorder, int& index) {
char ch = preorder[index];
if (ch == '#') {
index++;
return NULL;
}
TreeNode* root = new TreeNode(ch);
index++;
root->left = buildTree(preorder, index);
root->right = buildTree(preorder, index);
return root;
}
// 中序遍历二叉树并输出结果
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
std::cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
std::string preorder;
std::cin >> preorder;
int index = 0;
TreeNode* root = buildTree(preorder, index);
inorderTraversal(root);
std::cout << std::endl;
return 0;
}