给我用c语言写一串中序线索化二叉树的代码
时间: 2023-11-18 20:06:18 浏览: 67
下面是用 C 语言实现中序线索化二叉树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
//定义二叉树结点的结构体
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
int ltag, rtag; //新增线索标志
};
//创建二叉树结点
struct TreeNode* createNode(int val) {
struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
node->ltag = 0;
node->rtag = 0;
return node;
}
//中序线索化二叉树函数
void inorderThread(struct TreeNode* root, struct TreeNode** pre) {
if (root == NULL) {
return;
}
inorderThread(root->left, pre);
if (root->left == NULL) { //如果当前结点没有左子结点,建立前驱线索
root->left = *pre;
root->ltag = 1;
}
if (*pre != NULL && (*pre)->right == NULL) { //如果前驱结点没有右子结点,建立后继线索
(*pre)->right = root;
(*pre)->rtag = 1;
}
*pre = root; //更新前驱结点
inorderThread(root->right, pre);
}
//中序遍历中序线索化的二叉树
void inorderTraversal(struct TreeNode* root) {
while (root != NULL) {
while (root->ltag == 0) { //如果当前结点有左子结点,一直向左走
root = root->left;
}
printf("%d ", root->val); //输出当前结点的值
while (root->rtag == 1 && root->right != NULL) { //如果当前结点有后继线索,一直向右走
root = root->right;
printf("%d ", root->val); //输出后继结点的值
}
root = root->right; //否则就转向右子树
}
}
int main() {
//创建一个二叉树
struct TreeNode* root = createNode(4);
root->left = createNode(2);
root->left->left = createNode(1);
root->left->right = createNode(3);
root->right = createNode(6);
root->right->left = createNode(5);
root->right->right = createNode(7);
//中序线索化二叉树
struct TreeNode* pre = NULL;
inorderThread(root, &pre);
//中序遍历中序线索化的二叉树
inorderTraversal(root);
return 0;
}
```
在以上代码中,我们定义了一个 `struct TreeNode` 结构体,表示二叉树的结点。在结构体中新增了两个属性 `ltag` 和 `rtag`,用于表示该结点是否为前驱或后继线索。我们使用 `createNode` 函数来创建一个二叉树结点。
在 `inorderThread` 函数中,我们采用递归的方式对二叉树进行中序遍历。在遍历过程中,我们根据当前结点是否有左子结点或前驱结点是否有右子结点来判断是否需要建立线索。同时,我们还需要更新前驱结点。
在 `inorderTraversal` 函数中,我们采用迭代的方式对中序线索化的二叉树进行中序遍历。在遍历过程中,我们需要判断当前结点是否有左子结点或后继结点是否为线索,以确定需要走向哪个结点。
最后,在 `main` 函数中,我们使用 `createNode` 函数创建了一个二叉树,并对其进行中序线索化和中序遍历。
阅读全文