下面是给定一棵二叉树的先序遍历序列和中序遍历序列,输出后序遍历序列的c语言代码
时间: 2023-12-30 13:02:27 浏览: 88
数据结构实验报告8-树-求二叉树先序、中序、后序遍历次序的第k个访问结点-实验内容与要求.docx
以下是二叉树后序遍历的 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
char data;
struct Node *left;
struct Node *right;
}Node, *pNode;
Node *createTree(char *preorder, char *inorder, int length)
{
if(preorder == NULL || inorder == NULL || length <= 0)
return NULL;
Node *root = (Node*)malloc(sizeof(Node));
root->data = *preorder;
int rootIndex = 0;
while(rootIndex < length && *(inorder + rootIndex) != *preorder)
++rootIndex;
if(rootIndex >= length)
return NULL;
root->left = createTree(preorder + 1, inorder, rootIndex);
root->right = createTree(preorder + rootIndex + 1, inorder + rootIndex + 1, length - rootIndex - 1);
return root;
}
void postorderTraversal(Node *root)
{
if(root == NULL)
return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->data);
}
int main()
{
char preorder[] = "ABDECFG";
char inorder[] = "DBEAFCG";
int length = sizeof(preorder) / sizeof(char);
Node *root = createTree(preorder, inorder, length);
printf("The postorder traversal of the binary tree is: ");
postorderTraversal(root);
return 0;
}
```
其中,createTree 函数用于根据给定的先序遍历序列和中序遍历序列构建二叉树,postorderTraversal 函数用于输出后序遍历序列。需要注意的是,以上代码中的二叉树假定没有重复的节点。
阅读全文