线索二叉树的基本操作c语言代码
时间: 2023-09-11 08:07:26 浏览: 55
以下是线索二叉树的基本操作c语言代码:
定义线索二叉树节点结构体:
```c
typedef struct ThreadNode {
int data; // 节点数据
struct ThreadNode *lchild, *rchild; // 左右孩子指针
int ltag, rtag; // 左右线索标记
} ThreadNode, *ThreadTree;
```
初始化线索二叉树:
```c
void InitThreadTree(ThreadTree *tree) {
*tree = NULL;
}
```
创建线索二叉树:
```c
void CreateThreadTree(ThreadTree *tree) {
int data;
scanf("%d", &data);
if (data == -1) {
*tree = NULL;
} else {
*tree = (ThreadNode *)malloc(sizeof(ThreadNode));
(*tree)->data = data;
CreateThreadTree(&(*tree)->lchild);
CreateThreadTree(&(*tree)->rchild);
}
}
```
中序遍历线索化:
```c
ThreadNode *last = NULL; // 记录上一个被遍历的节点
void InThread(ThreadTree tree) {
if (tree) {
// 先处理左子树
InThread(tree->lchild);
// 处理当前节点
if (!tree->lchild) { // 左孩子不存在,建立左线索
tree->lchild = last;
tree->ltag = 1;
}
if (last && !last->rchild) { // 上一个节点的右孩子不存在,建立右线索
last->rchild = tree;
last->rtag = 1;
}
last = tree; // 更新上一个被遍历的节点
// 再处理右子树
InThread(tree->rchild);
}
}
```
中序遍历线索二叉树:
```c
void InOrder(ThreadTree tree) {
ThreadNode *p = tree;
while (p) {
while (p->ltag == 0) {
p = p->lchild;
}
printf("%d ", p->data);
while (p->rtag == 1 && p->rchild) {
p = p->rchild;
printf("%d ", p->data);
}
p = p->rchild;
}
}
```
相关推荐
![](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)