用c++写一段代码给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
时间: 2024-01-21 15:40:58 浏览: 86
二叉树的先序、中序、后序、分层遍历C++实现
4星 · 用户满意度95%
好的,关于二叉树的层序遍历,我可以给您提供以下的 C 代码实现:
```
#include<stdio.h>
#include<stdlib.h>
//定义二叉树节点结构体
struct Node
{
int value;
struct Node* left;
struct Node* right;
};
//创建新节点函数
struct Node* newNode(int value)
{
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
//查找中序遍历中根节点位置
int findRoot(int* inOrder, int start, int end, int value)
{
int i;
for(i = start; i <= end; i++)
{
if(inOrder[i] == value)
return i;
}
return -1; //找不到,返回-1
}
//根据后序序列和中序序列构建二叉树函数
struct Node* buildTree(int* inOrder, int* postOrder, int start, int end, int* postIndex)
{
if(start > end)
return NULL;
struct Node* node = newNode(postOrder[*postIndex]);
(*postIndex)--;
if(start == end)
return node;
int rootIndex = findRoot(inOrder, start, end, node->value);
node->right = buildTree(inOrder, postOrder, rootIndex + 1, end, postIndex);
node->left = buildTree(inOrder, postOrder, start, rootIndex - 1, postIndex);
return node;
}
//计算二叉树高度函数
int getHeight(struct Node* node)
{
if(node == NULL)
return 0;
int leftHeight = getHeight(node->left);
int rightHeight = getHeight(node->right);
return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
}
//输出二叉树指定深度节点值函数
void printLevel(struct Node* node, int level)
{
if(node == NULL)
return;
if(level == 1)
printf("%d ", node->value);
else if(level > 1)
{
printLevel(node->left, level - 1);
printLevel(node->right, level - 1);
}
}
//输出层序遍历序列函数
void printLevelOrder(struct Node* root)
{
int height = getHeight(root);
for(int i = 1; i <= height; i++)
{
printLevel(root, i);
}
}
//主函数
int main()
{
int inOrder[] = {9, 3, 15, 20, 7}; //中序遍历序列
int postOrder[] = {9, 15, 7, 20, 3}; //后序遍历序列
int n = sizeof(inOrder) / sizeof(inOrder[0]);
int postIndex = n - 1; //后序序列的最后一个节点是根节点
struct Node* root = buildTree(inOrder, postOrder, 0, n - 1, &postIndex); //构建二叉树
printf("层序遍历序列为:");
printLevelOrder(root); //输出层序遍历序列
return 0;
}
```
这段代码可以按照题目要求输入一棵二叉树的后序遍历和中序遍历序列,然后输出其层序遍历序列。如果您有其他问题,也可以随时询问我哦。
阅读全文