数据结构 | 线索二叉树

news/2025/3/16 1:21:27/

一、数据结构定义

/* 线索二叉树 */
typedef char ThreadType;
typedef struct ThreadNode {ThreadType data;struct ThreadNode* lchild, * rchild;int ltag, rtag; //左右线索标志
}ThreadNode, *ThreadTree;

二、方法概览

ThreadTree createTree(); //先序方法创建二叉树
void threaded(ThreadNode* q); //对当前结点进行线索化操作
void createInThreadTree(ThreadTree T); //中序线索化二叉树T
void inThread(ThreadTree T); //中序遍历二叉树，边遍历边线索化
void preThread(ThreadTree T); //先序遍历二叉树，边遍历边线索化
void postThread(ThreadTree T); //后序遍历二叉树，边遍历边线索化void visit(ThreadNode* node); //对结点T的操作
ThreadNode* firstNode(ThreadNode* p); // 找到以P为根节点的子树中，中序遍历首先被遍历的节点
ThreadNode* lastNode(ThreadNode* p); // 找到以P为根节点的子树中，中序遍历最后被遍历的节点
ThreadNode* nextNode(ThreadNode* p); // 在中序线索二叉树中找到P的后继节点
ThreadNode* preNode(ThreadNode* p); // 在中序线索二叉树中找到P的前驱节点
void inOrder_thread(ThreadNode* T); // 中序遍历二叉树（利用线索实现的非递归算法，空间复杂度O（1））
void revInOrder_thread(ThreadNode* T); // 逆向中序遍历二叉树

三、方法详解

/*-------- 线索化二叉树 --------*/
//先序方法创建二叉树
ThreadTree createTree() {ThreadTree root;ThreadType data;scanf("%c", &data);if (data == '#') root = NULL;else {root = (ThreadNode*)malloc(sizeof(ThreadNode));root->data = data;root->ltag = root->rtag = 0;root->lchild = createTree();root->rchild = createTree();}return root;
}
//对当前结点进行线索化操作
void threaded(ThreadNode* p) {// 左指针为空，建立前驱线索if (p->lchild == NULL) {p->lchild = pre;p->ltag = 1;}// 建立前驱节点的后继线索if (pre != NULL && pre->rchild == NULL) {pre->rchild = p;pre->rtag = 1;}// 指针后移pre = p;
}
//中序线索化二叉树T
void createInThreadTree(ThreadTree T) {pre = NULL;if (T != NULL) {inThread(T);if (pre->rchild == NULL)pre->rtag = 1;}
}
//中序遍历二叉树，边遍历边线索化
void inThread(ThreadTree T) {if (T != NULL) {inThread(T->lchild);threaded(T);inThread(T->rchild);}
}
//先序遍历二叉树，边遍历边线索化
void preThread(ThreadTree T) {if (T != NULL) {threaded(T);// lchild不是前驱线索时才访问其左孩子// 不加该条件，可能会出现两个指针无限循环打转if(T->ltag==0) preThread(T->lchild);preThread(T->rchild);}
}
//后序遍历二叉树，边遍历边线索化
void postThread(ThreadTree T) {if (T != NULL) {// 不会出现先序遍历的情况// 因为进行 visit(T) 的时候，其左孩子、右孩子已经处理完，不会再访问了postThread(T->lchild);postThread(T->rchild);threaded(T);}
}/*-------- 遍历线索二叉树 --------*/
//对结点T的操作
void visit(ThreadNode* node) {printf("%c ", node->data);
}
// 找到以P为根节点的子树中，中序遍历首先被遍历的节点
ThreadNode* firstNode(ThreadNode* p) {//循环找到中序遍历的最左下角的节点（不一定是叶子节点）while (p->ltag == 0) p = p->lchild;return p;
}
// 找到以P为根节点的子树中，中序遍历最后被遍历的节点
ThreadNode* lastNode(ThreadNode* p) {//循环找到中序遍历的最右下角的节点（不一定是叶子节点）while (p->rtag == 0) p = p->rchild;return p;
}
// 在中序线索二叉树中找到P的后继节点
ThreadNode* nextNode(ThreadNode* p) {// p->rtag = 0(指示P节点的左孩子),返回右子树最左下节点if (p->rtag == 0) return firstNode(p->rchild);// p->rtag = 1(指示线索),直接返回后继线索else return p->rchild;
}
// 在中序线索二叉树中找到P的前驱节点
ThreadNode* preNode(ThreadNode* p) {// p->rtag = 0(指示P节点的右孩子),返回左子树最右下节点if (p->ltag == 0) return lastNode(p->lchild);// p->rtag = 1(指示线索),直接返回前驱线索else return p->lchild;
}
// 中序遍历二叉树（利用线索实现的非递归算法，空间复杂度O（1））
void inOrder_thread(ThreadNode* T) {for (ThreadNode* p = firstNode(T); p != NULL; p = nextNode(p)) {visit(p);}
}
// 逆向中序遍历二叉树
void revInOrder_thread(ThreadNode* T) {for (ThreadNode* p = lastNode(T); p != NULL; p = preNode(p)) {visit(p);}
}

四、运行结果

        main方法代码如下：

int main() {// 输入先序序列 ABD##E#H##CF##G## 创建二叉树printf("输入先序序列创建二叉树:");ThreadTree root = createTree();createInThreadTree(root);printf("\n中序遍历:");inOrder_thread(root);printf("\n逆向中序遍历:");revInOrder_thread(root);
}

        运行结果如下：

 

五、源代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>/* 线索二叉树 */
typedef char ThreadType;
typedef struct ThreadNode {ThreadType data;struct ThreadNode* lchild, * rchild;int ltag, rtag; //左右线索标志
}ThreadNode, *ThreadTree;ThreadTree createTree(); //先序方法创建二叉树
void threaded(ThreadNode* q); //对当前结点进行线索化操作
void createInThreadTree(ThreadTree T); //中序线索化二叉树T
void inThread(ThreadTree T); //中序遍历二叉树，边遍历边线索化
void preThread(ThreadTree T); //先序遍历二叉树，边遍历边线索化
void postThread(ThreadTree T); //后序遍历二叉树，边遍历边线索化void visit(ThreadNode* node); //对结点T的操作
ThreadNode* firstNode(ThreadNode* p); // 找到以P为根节点的子树中，中序遍历首先被遍历的节点
ThreadNode* lastNode(ThreadNode* p); // 找到以P为根节点的子树中，中序遍历最后被遍历的节点
ThreadNode* nextNode(ThreadNode* p); // 在中序线索二叉树中找到P的后继节点
ThreadNode* preNode(ThreadNode* p); // 在中序线索二叉树中找到P的前驱节点
void inOrder_thread(ThreadNode* T); // 中序遍历二叉树（利用线索实现的非递归算法，空间复杂度O（1））
void revInOrder_thread(ThreadNode* T); // 逆向中序遍历二叉树//指向当前访问节点的前驱
ThreadNode* pre = NULL;/*-------- 线索化二叉树 --------*/
//先序方法创建二叉树
ThreadTree createTree() {ThreadTree root;ThreadType data;scanf("%c", &data);if (data == '#') root = NULL;else {root = (ThreadNode*)malloc(sizeof(ThreadNode));root->data = data;root->ltag = root->rtag = 0;root->lchild = createTree();root->rchild = createTree();}return root;
}
//对当前结点进行线索化操作
void threaded(ThreadNode* p) {// 左指针为空，建立前驱线索if (p->lchild == NULL) {p->lchild = pre;p->ltag = 1;}// 建立前驱节点的后继线索if (pre != NULL && pre->rchild == NULL) {pre->rchild = p;pre->rtag = 1;}// 指针后移pre = p;
}
//中序线索化二叉树T
void createInThreadTree(ThreadTree T) {pre = NULL;if (T != NULL) {inThread(T);if (pre->rchild == NULL)pre->rtag = 1;}
}
//中序遍历二叉树，边遍历边线索化
void inThread(ThreadTree T) {if (T != NULL) {inThread(T->lchild);threaded(T);inThread(T->rchild);}
}
//先序遍历二叉树，边遍历边线索化
void preThread(ThreadTree T) {if (T != NULL) {threaded(T);// lchild不是前驱线索时才访问其左孩子// 不加该条件，可能会出现两个指针无限循环打转if(T->ltag==0) preThread(T->lchild);preThread(T->rchild);}
}
//后序遍历二叉树，边遍历边线索化
void postThread(ThreadTree T) {if (T != NULL) {// 不会出现先序遍历的情况// 因为进行 visit(T) 的时候，其左孩子、右孩子已经处理完，不会再访问了postThread(T->lchild);postThread(T->rchild);threaded(T);}
}/*-------- 遍历线索二叉树 --------*/
//对结点T的操作
void visit(ThreadNode* node) {printf("%c ", node->data);
}
// 找到以P为根节点的子树中，中序遍历首先被遍历的节点
ThreadNode* firstNode(ThreadNode* p) {//循环找到中序遍历的最左下角的节点（不一定是叶子节点）while (p->ltag == 0) p = p->lchild;return p;
}
// 找到以P为根节点的子树中，中序遍历最后被遍历的节点
ThreadNode* lastNode(ThreadNode* p) {//循环找到中序遍历的最右下角的节点（不一定是叶子节点）while (p->rtag == 0) p = p->rchild;return p;
}
// 在中序线索二叉树中找到P的后继节点
ThreadNode* nextNode(ThreadNode* p) {// p->rtag = 0(指示P节点的左孩子),返回右子树最左下节点if (p->rtag == 0) return firstNode(p->rchild);// p->rtag = 1(指示线索),直接返回后继线索else return p->rchild;
}
// 在中序线索二叉树中找到P的前驱节点
ThreadNode* preNode(ThreadNode* p) {// p->rtag = 0(指示P节点的右孩子),返回左子树最右下节点if (p->ltag == 0) return lastNode(p->lchild);// p->rtag = 1(指示线索),直接返回前驱线索else return p->lchild;
}
// 中序遍历二叉树（利用线索实现的非递归算法，空间复杂度O（1））
void inOrder_thread(ThreadNode* T) {for (ThreadNode* p = firstNode(T); p != NULL; p = nextNode(p)) {visit(p);}
}
// 逆向中序遍历二叉树
void revInOrder_thread(ThreadNode* T) {for (ThreadNode* p = lastNode(T); p != NULL; p = preNode(p)) {visit(p);}
}int main() {// 输入先序序列 ABD##E#H##CF##G## 创建二叉树printf("输入先序序列创建二叉树:");ThreadTree root = createTree();createInThreadTree(root);printf("\n中序遍历:");inOrder_thread(root);printf("\n逆向中序遍历:");revInOrder_thread(root);
}

http://www.ppmy.cn/news/710033.html

相关文章

在未来人工智能是控制人类，还是当人类的宠物？

在未来人工智能是控制人类，还是当人类的宠物？

人工智能发展至今没有人知道它到底发展到哪个地步了&#xff0c;谁也不知道在世界的哪个角落&#xff0c;有人在秘密研究人工智能的某个领域&#xff0c;进展到哪一步。我们对于人工智能的认知还停留在科幻电影之中&#xff0c;机器人可以成为管家&#xff0c;可以成为医生&…
阅读更多...
Python书籍阅读与记录 6.12 I 字典

Python书籍阅读与记录 6.12 I 字典

我感觉这样记录&#xff0c;对于我来说挺好的。因为我看两端对齐的语句容易走神&#xff0c;这样记录阅读的话&#xff0c;就很少出现之前的情况。 我写的初衷&#xff0c;也是自己来看&#xff0c;所以感觉写的不好的&#xff0c;请保留下意见&#xff0c;谢谢。 里面的每一个…
阅读更多...
勃仔诞生记：Hubbleverse哈勃元宇宙的起源故事

勃仔诞生记：Hubbleverse哈勃元宇宙的起源故事

欢迎来到Hubbleverse &#x1f30d; 关注我们 关注宇宙新鲜事 &#x1f4cc; 预计阅读时长&#xff1a;9分钟 本文仅代表作者个人观点&#xff0c;不代表平台意见&#xff0c;不构成投资建议。 想象一个属于你的世界&#xff0c;一个资源丰富的世界&#xff0c;你可以在其中…
阅读更多...
python书籍阅读与记录6.12 I 字典

python书籍阅读与记录6.12 I 字典

我感觉这样记录&#xff0c;对于我来说挺好的。因为我看两端对齐的语句容易走神&#xff0c;这样记录阅读的话&#xff0c;就很少出现之前的情况。 我写的初衷&#xff0c;也是自己来看&#xff0c;所以感觉写的不好的&#xff0c;请保留下意见&#xff0c;谢谢。 里面的每一个…
阅读更多...
Java 第二周总结1024 面向对象

Java 第二周总结1024 面向对象

1.类和对象的关系 类是抽象的,对象是具体的,类是具有相同属性和方法的对象的集合,对象是类的一个实例,是一个具体的实体 创建类和对象 创建一个类(属性和方法) 通过这个类创建对象 (构造方法) 使用对象名调用属性和方法, 对象名.属性; 对象名.方法名(); 方法的定义 方法定义…
阅读更多...
Python编程从入门到实践 第一部分基础知识 代码合集

Python编程从入门到实践 第一部分基础知识 代码合集

手敲代码合集 第2章 变量和简单数据类型2.1 运行hello_world.py时发生的情况2.2 变量2.3 字符串2.3.1 使用方法修改字符串的大小写2.3.2 合并&#xff08;拼接&#xff09;字符串2.3.3 使用制表符或换行符来添加空白2.3.4 删除空白 2.4 数字2.4.1 整数2.4.2 浮点数2.4.3 使用函…
阅读更多...
【Python编程从入门到实践】学习笔记

【Python编程从入门到实践】学习笔记

0222 不需要分号&#xff0c;不需要规定类型&#xff0c;直接赋值&#xff0c;且中途可以随时修改变量的值 message"Hello Python world!" print(message) message"Hello Python Crash Course world!" print(message)Hello Python world! Hello Python C…
阅读更多...
《Python编程 从入门到实践》 一、基础知识 第六章 字典

《Python编程 从入门到实践》 一、基础知识 第六章 字典

6.1一个简单的字典 来看一个游戏&#xff0c;其中包含一些外星人&#xff0c;这些外星人的颜色和点数各不相同&#xff0c;下面是一个简单的字典&#xff0c;存储了有关特定外星人的信息&#xff1a; alien_0{color:green,points:5} print (alien_0[color]) print (alien_0[p…
阅读更多...
最新文章

Copyright @ 2022~2023