)给定一个二又树的后序序列DGEBHFCA,中序序列DBEGAHCF,要求输出二又树的先续序列char * getPost(char postAl ] . char inAl 1 int N),用c语言写
时间: 2024-03-23 21:38:43 浏览: 16
好的,根据您提供的后序序列和中序序列,我们可以采用递归的方式构建出这棵二叉树,然后再采用先序遍历的方式输出先序序列。以下是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BiTree {
char data;
struct BiTree *lchild, *rchild;
}BiTree;
int findPosition(char *str, char ch) { // 查找字符在字符串中的位置
char *p = strchr(str, ch);
if (p == NULL) return -1;
return (int)(p - str);
}
BiTree *buildTree(char *postAl, char *inAl, int postStart, int postEnd, int inStart, int inEnd) { // 构建二叉树
if (postStart > postEnd || inStart > inEnd) return NULL;
char rootValue = postAl[postEnd]; // 后序遍历的最后一个元素为根节点
int rootPosition = findPosition(inAl, rootValue); // 在中序遍历中查找根节点
BiTree *root = (BiTree *)malloc(sizeof(BiTree));
root->data = rootValue;
root->lchild = buildTree(postAl, inAl, postStart, postStart + rootPosition - inStart - 1, inStart, rootPosition - 1); // 构建左子树
root->rchild = buildTree(postAl, inAl, postStart + rootPosition - inStart, postEnd - 1, rootPosition + 1, inEnd); // 构建右子树
return root;
}
void preOrder(BiTree *root, char *preAl, int *preIndex) { // 先序遍历
if (root == NULL) return;
preAl[(*preIndex)++] = root->data;
preOrder(root->lchild, preAl, preIndex);
preOrder(root->rchild, preAl, preIndex);
}
char *getPost(char *postAl, char *inAl, int N) { // 获取先序遍历序列
BiTree *root = buildTree(postAl, inAl, 0, N - 1, 0, N - 1);
char *preAl = (char *)malloc(sizeof(char) * (N + 1));
int preIndex = 0;
preOrder(root, preAl, &preIndex);
preAl[N] = '\0';
free(root);
return preAl;
}
int main() {
char postAl[] = "DGEBHFCA";
char inAl[] = "DBEGAHCF";
char *preAl = getPost(postAl, inAl, strlen(postAl));
printf("%s\n", preAl);
free(preAl);
return 0;
}
```
这里我们首先定义了一个`BiTree`结构体,其中包含了节点的数据和左右子树的指针。`findPosition`函数用于查找字符在字符串中的位置,采用了`strchr`函数库,用于在字符串中查找特定字符。`buildTree`函数则是递归构建二叉树,根据后序遍历序列和中序遍历序列的特点,我们可以将问题转化为构建左右子树的问题。`preOrder`函数采用先序遍历的方式输出先序序列。最后,`getPost`函数调用`buildTree`函数构建二叉树,并调用`preOrder`函数输出先序序列。
需要注意的是,在构建二叉树后,需要手动释放二叉树节点的内存,避免内存泄漏。