设计一个算法,输出二叉树的先序序列、中序序列、后序序列
时间: 2023-12-08 13:04:23 浏览: 31
以下是输出二叉树先序、中序、后序遍历序列的算法:
```
// 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 输出二叉树先序遍历序列
void preorderTraversal(TreeNode* root, vector<int>& res) {
if (root) {
res.push_back(root->val);
preorderTraversal(root->left, res);
preorderTraversal(root->right, res);
}
}
// 输出二叉树中序遍历序列
void inorderTraversal(TreeNode* root, vector<int>& res) {
if (root) {
inorderTraversal(root->left, res);
res.push_back(root->val);
inorderTraversal(root->right, res);
}
}
// 输出二叉树后序遍历序列
void postorderTraversal(TreeNode* root, vector<int>& res) {
if (root) {
postorderTraversal(root->left, res);
postorderTraversal(root->right, res);
res.push_back(root->val);
}
}
// 测试代码
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
vector<int> res;
// 输出先序遍历序列
preorderTraversal(root, res);
for (auto i : res) {
cout << i << " ";
}
cout << endl;
res.clear();
// 输出中序遍历序列
inorderTraversal(root, res);
for (auto i : res) {
cout << i << " ";
}
cout << endl;
res.clear();
// 输出后序遍历序列
postorderTraversal(root, res);
for (auto i : res) {
cout << i << " ";
}
cout << endl;
return 0;
}
```
这个算法的时间复杂度是 $O(n)$,其中 $n$ 是二叉树的节点数。因为每个节点会被访问一次,所以时间复杂度是线性的。