c语言已知二叉树先序和中序序列,唯一地构造一棵二叉树并且验证其正确性
时间: 2024-01-23 11:42:01 浏览: 65
可以使用递归方法构造二叉树,具体步骤如下:
1. 在先序序列中找到根节点(即第一个节点),并创建一个新的二叉树节点。
2. 在中序序列中找到根节点的位置,将中序序列分为左子树和右子树两部分。
3. 递归构造左子树,将左子树的根节点作为当前节点的左子节点。
4. 递归构造右子树,将右子树的根节点作为当前节点的右子节点。
5. 返回当前节点。
构造完成后,可以对比原先的先序和中序序列,验证构造的二叉树是否正确。
以下是 C 语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 在先序序列中查找根节点
int findRoot(char* preOrder, int preStart, int preEnd, char rootVal) {
int i;
for (i = preStart; i <= preEnd; i++) {
if (preOrder[i] == rootVal) {
return i;
}
}
return -1;
}
// 构造二叉树
TreeNode* buildTree(char* preOrder, int preStart, int preEnd, char* inOrder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preOrder[preStart];
int rootIndex = findRoot(inOrder, inStart, inEnd, root->val);
int leftSize = rootIndex - inStart;
root->left = buildTree(preOrder, preStart + 1, preStart + leftSize, inOrder, inStart, rootIndex - 1);
root->right = buildTree(preOrder, preStart + leftSize + 1, preEnd, inOrder, rootIndex + 1, inEnd);
return root;
}
// 验证二叉树
int validateTree(TreeNode* root, char* preOrder, int* preIndex, char* inOrder, int inStart, int inEnd) {
if (!root) {
return 1;
}
if (*preIndex >= strlen(preOrder) || root->val != preOrder[*preIndex]) {
return 0;
}
(*preIndex)++;
int rootIndex = findRoot(inOrder, inStart, inEnd, root->val);
if (rootIndex == -1) {
return 0;
}
if (!validateTree(root->left, preOrder, preIndex, inOrder, inStart, rootIndex - 1)) {
return 0;
}
if (!validateTree(root->right, preOrder, preIndex, inOrder, rootIndex + 1, inEnd)) {
return 0;
}
return 1;
}
int main() {
char preOrder[] = {'A', 'B', 'D', 'E', 'C', 'F', 'G'};
char inOrder[] = {'D', 'B', 'E', 'A', 'F', 'C', 'G'};
TreeNode* root = buildTree(preOrder, 0, strlen(preOrder) - 1, inOrder, 0, strlen(inOrder) - 1);
int preIndex = 0;
if (validateTree(root, preOrder, &preIndex, inOrder, 0, strlen(inOrder) - 1)) {
printf("The tree is valid.\n");
} else {
printf("The tree is invalid.\n");
}
return 0;
}
```
输出结果为:
```
The tree is valid.
```
说明构造的二叉树正确。
阅读全文