线索二叉树c语言代码
时间: 2023-11-20 13:55:42 浏览: 52
以下是线索二叉树的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义线索二叉树结构体
typedef struct ThreadedBinaryTreeNode {
int data;
struct ThreadedBinaryTreeNode *left, *right;
int ltag, rtag; // 0表示指向左右子树,1表示指向前驱或后继
} ThreadedBinaryTreeNode, *ThreadedBinaryTree;
// 中序遍历线索化
void InThread(ThreadedBinaryTree p, ThreadedBinaryTree *pre) {
if (p != NULL) {
InThread(p->left, pre);
if (p->left == NULL) {
p->left = *pre;
p->ltag = 1;
}
if (*pre != NULL && (*pre)->right == NULL) {
(*pre)->right = p;
(*pre)->rtag = 1;
}
*pre = p;
InThread(p->right, pre);
}
}
// 创建线索二叉树
void CreateInThread(ThreadedBinaryTree *root) {
ThreadedBinaryTree pre = NULL;
if (*root != NULL) {
InThread(*root, &pre);
pre->right = NULL;
pre->rtag = 1;
}
}
// 中序遍历线索二叉树
void InOrderTraverse(ThreadedBinaryTree root) {
ThreadedBinaryTree p = root;
while (p != NULL) {
while (p->ltag == 0) {
p = p->left;
}
printf("%d ", p->data);
while (p->rtag == 1 && p->right != NULL) {
p = p->right;
printf("%d ", p->data);
}
p = p->right;
}
}
// 测试
int main() {
// 创建线索二叉树
ThreadedBinaryTree root = (ThreadedBinaryTree)malloc(sizeof(ThreadedBinaryTreeNode));
root->data = 1;
root->ltag = root->rtag = 0;
root->left = (ThreadedBinaryTree)malloc(sizeof(ThreadedBinaryTreeNode));
root->left->data = 2; root->left->ltag = root->left->rtag = 0;
root->left->left = root->left->right = NULL;
root->right = (ThreadedBinaryTree)malloc(sizeof(ThreadedBinaryTreeNode));
root->right->data = 3;
root->right->ltag = root->right->rtag = 0;
root->right->left = (ThreadedBinaryTree)malloc(sizeof(ThreadedBinaryTreeNode));
root->right->left->data = 4;
root->right->left->ltag = root->right->left->rtag = 0;
root->right->left->left = root->right->left->right = NULL;
root->right->right = (ThreadedBinaryTree)malloc(sizeof(ThreadedBinaryTreeNode));
root->right->right->data = 5;
root->right->right->ltag = root->right->right->rtag = 0;
root->right->right->left = root->right->right->right = NULL;
CreateInThread(&root);
// 中序遍历线索二叉树
InOrderTraverse(root);
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)