建立一棵二叉树(采用二叉链表存储方式); 2.输出该二叉树结点的前序遍历、中序遍历、后序遍历序列。
时间: 2024-05-05 08:19:12 浏览: 100
编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序和按层遍历的算法
5星 · 资源好评率100%
好的,我可以为您解答这个问题。
首先,要建立一棵二叉树,我们需要先定义二叉树结点的结构体,包含三个成员:数据域,左子树指针和右子树指针。
```
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
接下来,可以通过递归方式实现构建二叉树的方法。具体步骤如下:
1. 读入当前节点的值;
2. 构造一个新节点,并将其值设为当前节点的值;
3. 递归构建左子树;
4. 递归构建右子树;
5. 如果当前节点为空,则返回NULL,否则返回当前节点。
```
TreeNode* buildTree() {
int val;
cin >> val;
if (val == -1) {
return NULL;
}
TreeNode* root = new TreeNode(val);
root->left = buildTree();
root->right = buildTree();
return root;
}
```
接下来,我们可以分别实现前序、中序和后序遍历算法,这里采用递归方式:
前序遍历:根节点 -> 左子树 -> 右子树
```
void preorderTraversal(TreeNode* root) {
if (!root) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
```
中序遍历:左子树 -> 根节点 -> 右子树
```
void inorderTraversal(TreeNode* root) {
if (!root) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
```
后序遍历:左子树 -> 右子树 -> 根节点
```
void postorderTraversal(TreeNode* root) {
if (!root) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
```
最后,我们就可以在 main 函数中调用上述函数完成题目要求了:
```
int main() {
TreeNode* root = buildTree();
cout << "前序遍历:" << endl;
preorderTraversal(root);
cout << endl;
cout << "中序遍历:" << endl;
inorderTraversal(root);
cout << endl;
cout << "后序遍历:" << endl;
postorderTraversal(root);
cout << endl;
return 0;
}
```
希望这个答案对您有所帮助!
阅读全文