用c++编写一段程序实现如下功能:采用递归计算方式实现按任意顺序(先序、中序、后序)手动输入创建一个二叉树,再按照其他顺序输出遍历序列
时间: 2024-05-14 12:15:49 浏览: 93
C语言实现二叉树的前序、中序、后续遍历(递归法)
好的,我明白了。以下是您所需的C语言代码,用于递归地创建二叉树并按照指定的遍历顺序输出:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *left;
struct node *right;
}Node; //定义二叉树节点
Node* create_node(int value) //创建一个新的节点
{
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
Node* build_tree(int *preorder, int *inorder, int pStart, int pEnd, int iStart, int iEnd)
{
if (pStart > pEnd) //如果遍历序列为空,则返回NULL
{
return NULL;
}
int rootValue = preorder[pStart]; //根据先序遍历的第一个元素获取二叉树根节点的值
int rootIndex = iStart; //在中序遍历序列中查找二叉树根节点的位置
while (rootIndex <= iEnd && inorder[rootIndex] != rootValue)
{
rootIndex++;
}
Node* root = create_node(rootValue);
int leftSubtreeSize = rootIndex - iStart; //计算左子树的大小
root->left = build_tree(preorder, inorder, pStart + 1, pStart + leftSubtreeSize, iStart, rootIndex - 1); //递归创建左子树
root->right = build_tree(preorder, inorder, pStart + leftSubtreeSize + 1, pEnd, rootIndex + 1, iEnd); //递归创建右子树
return root; //返回二叉树根节点
}
void preorder_traversal(Node *root) //先序遍历
{
if (root != NULL)
{
printf("%d ", root->data);
preorder_traversal(root->left);
preorder_traversal(root->right);
}
}
void inorder_traversal(Node *root) //中序遍历
{
if (root != NULL)
{
inorder_traversal(root->left);
printf("%d ", root->data);
inorder_traversal(root->right);
}
}
void postorder_traversal(Node *root) //后序遍历
{
if (root != NULL)
{
postorder_traversal(root->left);
postorder_traversal(root->right);
printf("%d ", root->data);
}
}
int main()
{
int n;
printf("请输入二叉树节点数量:\n");
scanf("%d", &n);
int *preorder = (int*)malloc(sizeof(int) * n);
int *inorder = (int*)malloc(sizeof(int) * n);
printf("请输入二叉树的前序遍历序列:\n");
for (int i = 0; i < n; i++)
{
scanf("%d", &preorder[i]);
}
printf("请输入二叉树的中序遍历序列:\n");
for (int i = 0; i < n; i++)
{
scanf("%d", &inorder[i]);
}
Node *root = build_tree(preorder, inorder, 0, n-1, 0, n-1);
printf("按照先序遍历的顺序输出遍历序列:\n");
preorder_traversal(root);
printf("\n按照中序遍历的顺序输出遍历序列:\n");
inorder_traversal(root);
printf("\n按照后序遍历的顺序输出遍历序列:\n");
postorder_traversal(root);
return 0;
}
```
请注意,以上代码并未实现任意遍历方式。如果您需要实现其他遍历方式(如广度优先遍历等),您可以参考以下代码来实现:
```c
void bfs_traversal(Node *root) //广度优先遍历
{
if (root == NULL)
{
return;
}
queue<Node*> q;
q.push(root);
while (!q.empty())
{
Node *p = q.front();
q.pop();
printf("%d ", p->data);
if (p->left != NULL)
{
q.push(p->left);
}
if (p->right != NULL)
{
q.push(p->right);
}
}
}
```
这段代码使用了队列来实现广度优先遍历,您也可以使用栈来实现深度优先遍历(如先序遍历、中序遍历、后序遍历)。
希望以上代码对您有所帮助!
阅读全文