目录
题目要求
读入用户输入的一串前序遍历的字符串，根据此字符串建立一个链式二叉树
例如前序遍历的字符串为：ABC##DE#G##F### ；其中 "#" 表示空树
链式二叉树示意图
以此图的链式二叉树为例子
那么此链式二叉树前序遍历转换为字符串是："123###45##6##"
代码实现
实现前所需要的函数：
// 申请新节点
BTNode* BuyNode(BTDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
// 判断是否申请成功
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
// 初始化
newnode->data = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
// 前序遍历
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
// 根 -> 左子树 -> 右子树
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}前序序列创建链式二叉树：
BTNode* CreateTree(char* a, int* pi)
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = BuyNode(a[*pi] - '0');
(*pi)++;
root->left = CreateTree(a, pi);
root->right = CreateTree(a, pi);
return root;
}代码解析：
在前几章讲过，变量 i 在每个栈帧中都是独立的，所以不能传值，而是传址
第一个 if 语句用于判断是否是空，是空的话就返回空
再创建链式二叉树的节点，并且 pi++
且节点的左右子树就再次递归创建，根据判断字符串 a
最后返回 root 就是根节点的指针
代码验证：