编写程序,接收T的先序遍历序列string,根据string,建立T的二叉链表:btnode *creatTree(char *string): 其中,btnode为二叉链表的结点结构;string为T的先序遍历序列
时间: 2024-05-10 17:19:07 浏览: 77
以下是一个示例程序,实现了根据给定的先序遍历序列构建二叉树的功能:
```c++
#include <iostream>
#include <cstring>
using namespace std;
// 二叉树结点结构体
struct btnode {
char val;
btnode *left;
btnode *right;
btnode(char x) : val(x), left(nullptr), right(nullptr) {}
};
// 递归创建二叉树
btnode *createTreeHelper(char *&str) {
if (*str == '\0') return nullptr;
btnode *node = new btnode(*str);
++str;
node->left = createTreeHelper(str);
node->right = createTreeHelper(str);
return node;
}
// 创建二叉树的函数接口
btnode *createTree(char *string) {
if (string == nullptr) return nullptr;
char *str = string;
return createTreeHelper(str);
}
// 中序遍历二叉树
void inorderTraversal(btnode *root) {
if (root == nullptr) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
char str[] = "ABD##E##CF###";
btnode *root = createTree(str);
inorderTraversal(root); // 输出:D B E A F C
return 0;
}
```
程序中的 `createTree` 函数接收一个先序遍历序列的字符串,并返回构建好的二叉树的根结点。在实现中,我们使用了一个指向字符数组的指针 `str`,通过递归调用 `createTreeHelper` 函数来完成二叉树的构建。在 `createTreeHelper` 函数中,我们首先通过指针 `str` 获取当前结点的值,然后递归创建左右子树,并将左右子树的根结点链接到当前结点上。最后返回根结点即可。
为了验证程序的正确性,我们实现了一个 `inorderTraversal` 函数来对构建好的二叉树进行中序遍历,以此输出二叉树的结点值,供读者参考。
阅读全文