C语言编写代码如下要求: 1.先序遍历创建二叉树; 2.中序线索化二叉树; 3.分别通过 找前驱 和 找后继 的方式,遍历中序线索二叉树。
时间: 2024-01-21 08:17:40 浏览: 84
C语言数据结构之线索二叉树及其遍历
下面是符合要求的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
int leftIsThread; // 左子树是否为线索
int rightIsThread; // 右子树是否为线索
} TreeNode;
// 先序遍历创建二叉树
TreeNode* createTree() {
char c;
scanf("%c", &c); // 读入当前结点的值
if (c == '#') { // 如果为 # ,则表示该结点为空
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = c;
root->left = createTree();
root->right = createTree();
root->leftIsThread = 0;
root->rightIsThread = 0;
return root;
}
// 中序线索化二叉树
void inOrderThread(TreeNode* root, TreeNode** pre) {
if (root == NULL) {
return;
}
inOrderThread(root->left, pre);
if (root->left == NULL) { // 左子树为空,建立前驱线索
root->left = *pre;
root->leftIsThread = 1;
}
if (*pre != NULL && (*pre)->right == NULL) { // 前驱结点的右子树为空,建立后继线索
(*pre)->right = root;
(*pre)->rightIsThread = 1;
}
*pre = root;
inOrderThread(root->right, pre);
}
// 找到中序线索二叉树的第一个节点(最左边的节点)
TreeNode* firstNode(TreeNode* root) {
if (root == NULL) {
return NULL;
}
while (root->leftIsThread == 0) {
root = root->left;
}
return root;
}
// 找到某个结点在中序线索二叉树中的后继节点
TreeNode* inOrderSuccessor(TreeNode* node) {
if (node->rightIsThread == 0) { // 如果右子树不是线索,则后继结点为右子树的最左边节点
return firstNode(node->right);
} else { // 如果右子树是线索,则后继结点为右线索
return node->right;
}
}
// 遍历中序线索二叉树
void inOrderTraversal(TreeNode* root) {
TreeNode* cur = firstNode(root);
while (cur != NULL) {
printf("%c ", cur->val);
cur = inOrderSuccessor(cur);
}
}
int main() {
printf("请输入先序遍历序列,其中 # 表示空结点:\n");
TreeNode* root = createTree();
TreeNode* pre = NULL;
inOrderThread(root, &pre);
printf("中序线索化后的二叉树遍历序列为:\n");
inOrderTraversal(root);
return 0;
}
```
注意:以上代码只是一个基本的实现,可能存在一些细节问题和改进的空间。
阅读全文