念心卓

用户名：uq_80412005216

访问量：2762

签　名：

人不自渡，天也难助

等　　级
排　　名	1591
经　　验	2767
参赛次数	2
文章发表	24
年　　龄	0
在职情况	学生
学　　校	哔哩哔哩大学
专　　业	软件工程

　　自我简介：

TA的其他文章

二叉树的线索化以及线索化遍历（C语言）
浏览：249

堆排序(C语言)
浏览：143

二叉排序树的实现(主要语言是C，只是用了C++的引用)
浏览：58

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

优质题解

二叉树的线索化以及线索化遍历（C语言）

　　作者: 念心卓　　　　发表时间：2022-08-27 22:19:20 浏览：249　|　评论：0　

原题链接：数据结构-线索二叉树

###思路：
1. 首先需要根据先序序列**创建**一个二叉树。
2. 把创建的二叉树进行**中序线索化**。
3. 线索化完成之后，需要进行**中序线索化遍历**。

------------
### 算法思想
- 首先创建线索化二叉树的结构体
```
ltag = 0:lchild指向左孩子
ltag = 1:lchild指向结点的前驱;
rtag = 0:rchild指向右孩子
rtag = 1:rchild指向后继
```
- 根据先序序列创建二叉树
- 进行中序线索化
①定义一个前驱指针`pre`用来指向当前结点的"前一个"结点
②如果当前结点不为`NULL`，就根据中序的思想来递归线索化(**左根右**)
③线索完成之后就根据线索进行**中序线索遍历(左根右)**

### C语言代码
```
//下面用了一点C++的引用(&)
#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
//线索化二叉树的结构
typedef struct ThreadNode {
	ElemType data;
	struct ThreadNode* lchild, * rchild;
	/*
		ltag = 0:lchild指向左孩子
		ltag = 1:lchild指向结点的前驱;
		rtag = 0:rchild指向右孩子
		rtag = 1:rchild指向后继
	*/
	int ltag, rtag;
}ThreadNode,*ThreadTree;

//创建二叉树
void CreatBiTree(ThreadTree& root) {
	ElemType data;
	scanf("%c", &data);
	//data = getchar();
	if (data == ' ')
	{
		root = NULL;
	}
	else
	{
		root = (ThreadNode*)calloc(1, sizeof(ThreadNode));
		root->data = data;
		CreatBiTree(root->lchild);
		CreatBiTree(root->rchild);
	}
}

//中序遍历对二叉树进行线索化
void InThread(ThreadTree& root, ThreadTree& pre) {
	//左根右
	if (root != NULL)
	{
		InThread(root->lchild, pre);//递归线索化左子树
		if (root->lchild == NULL)//如果左子树为空，则建立前驱线索
		{
			root->lchild = pre;
			root->ltag = 1;//建立线索之后修改ltag，表示指向了前驱
		}
		if (pre != NULL && pre->rchild == NULL)
		{
			pre->rchild = root;//建立前驱结点的后继线索
			pre->rtag = 1;
		}
		pre = root;//修改前一个结点，让其指向当前结点
		InThread(root->rchild, pre);//递归线索化右子树
	}
}

//中序遍历创建中序线索二叉树
void CreatInThread(ThreadTree root) {
	ThreadTree pre = NULL;//用来指向当前结点的前一个结点
	if (root != NULL)//非空二叉树，则线索化
	{
		InThread(root,pre);//线索化二叉树
		if (pre->rchild == NULL)//对最后一个结点的处理
		{
			pre->rtag = 1;
		}
		/*pre->rchild = NULL;
		pre->rtag = 1;*/
	}
}

//求中序线索化二叉树中中序序列下的第一个结点
ThreadNode* FirstNode(ThreadNode* p) {
	while (p->ltag == 0)//表示有左子树
	{
		p = p->lchild;//一直找,找到最左下的节点(不一定是叶子结点,只要没有左子树就行)
	}
	return p;//返回最左下的节点
}

//求中序线索化二叉树中中序序列下的后继
ThreadNode* NextNode(ThreadNode* p) {
	if (p->rtag == 0)//如果有右子树
	{
		return FirstNode(p->rchild);//返回右子树中最左下的结点
	}
	return p->rchild;//rtag == 1直接返回后继线索即可
}

//中序线索化二叉树的中序遍历
void ThreadInOrder(ThreadNode *root) {
	//左根右
	for (ThreadNode *p = FirstNode(root);p != NULL;p = NextNode(p))
	{
		printf("%c ", p->data);
	}
}

int main() {
	ThreadTree root;
	CreatBiTree(root);
	CreatInThread(root);
	ThreadInOrder(root);//线索化的中序遍历
	printf("\n");
	return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

念心卓

TA的其他文章

你可能喜欢

地宫取宝（C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

二叉树的线索化以及线索化遍历（C语言）

评论区

精彩推荐

C语言训练-最大数问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C二级辅导-进制转换（C语言代码）

母牛的故事（C语言代码）

杨辉三角（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

10月月赛题解

念心卓

TA的其他文章

你可能喜欢

地宫取宝 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

二叉树的线索化以及线索化遍历（C语言）

评论区

精彩推荐

C语言训练-最大数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C二级辅导-进制转换 （C语言代码）

母牛的故事 （C语言代码）

杨辉三角 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

10月月赛题解

地宫取宝（C语言代码）

　　评论区

C语言训练-最大数问题（C语言代码）

C二级辅导-进制转换（C语言代码）

母牛的故事（C语言代码）

杨辉三角（C语言代码）