当前位置: 首页 > news >正文

第五章 树与二叉树 四、线索树(手算与代码实现)

一、定义

1.线索树是一种二叉树,它在每个节点上增加了两个指针,分别指向其前驱和后继。

2.这些指针称为“线索”,因此线索树也叫做“线索化二叉树”。

3.在线索树中,所有的叶子节点都被线索化,使得遍历树的过程可以更加高效地进行。

4.同时,线索树可以在O(1)的时间复杂度内找到任意节点的前驱和后继,而不需要遍历整个树。

二、存储结构(链式存储)

typedef struct BiNode{int data;struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;typedef struct ThreadNode{int data;struct ThreadNode *lchild,*rchild;int ltag,rtag;//左右线索标志
}ThreadNode,*ThreadTree;

ltag==1时,表示lchild指向前驱;

ltag==0时,表示lchild指向左孩子;

rtag==1时,表示rchild指向后继;

rtag==0时,表示rchild指向右孩子;

三、三种线索二叉树

1、手算线索二叉树

(1)中序线索二叉树

1.首先使用中序遍历为每个结点标上序号

2.我们跟着序号来画线索,首先判断D结点,它的没有前驱结点,所以它的前驱线索指向NULL,后继指针指向G

3.接着判断序号为2的结点G,它的前驱是D,后继是B

4.结点B的前驱是G,后继是E,但是在步骤三3中已经找到了它的前驱,而且结点B的指针已经有指向的结点了,所以不能再分配线索指针。

5.依此类推得到中序线索二叉树

(2)先序线索二叉树

1.步骤和中序相同,最重要的就是给结点打上序号,而且要把每个结点的左右孩子指针用完

(3)后序线索二叉树

1.直接上答案,同时要记住一个原则,左孩子指针指向该节点的前驱,右孩子指针指向后继。

(左前驱,右后继)

2、代码实现线索二叉树

(1)中序线索二叉树

#include "stdio.h"
#include "stdlib.h"typedef struct ThreadNode {char data;struct ThreadNode *lchild, *rchild;int ltag, rtag; // 左右线索标志
} ThreadNode, *ThreadTree;ThreadTree pre = NULL; // 使用单一指针void visit(ThreadNode *q) {if (q->lchild == NULL) {q->lchild = pre;q->ltag = 1;}if (pre != NULL && pre->rchild == NULL) {pre->rchild = q;pre->rtag = 1;}pre = q; // 直接赋值给 pre,不需要解引用
}// 中序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T) {if (T != NULL) {InThread(T->lchild); // 中序遍历左子树visit(T); // 访问根节点InThread(T->rchild); // 中序遍历右子树}
}void CreateInThread(ThreadTree T) {pre = NULL;if (T != NULL) {InThread(T);if (pre->rchild == NULL) {pre->rtag = 1;}}
}

(2)先序线索二叉树

#include "stdio.h"
#include "stdlib.h"typedef struct ThreadNode {char data;struct ThreadNode *lchild, *rchild;int ltag, rtag; // 左右线索标志
} ThreadNode, *ThreadTree;ThreadTree pre = NULL; // 使用单一指针void visit(ThreadNode *q) {if (q->lchild == NULL) {q->lchild = pre;q->ltag = 1;}if (pre != NULL && pre->rchild == NULL) {pre->rchild = q;pre->rtag = 1;}pre = q; // 直接赋值给 pre,不需要解引用
}// 先序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T) {if (T != NULL) {visit(T); // 访问根节点if(T->ltag == 0)                                    //判断是否为前驱线索InThread(T->lchild); // 中序遍历左子树InThread(T->rchild); // 中序遍历右子树}
}void CreateInThread(ThreadTree T) {pre = NULL;if (T != NULL) {InThread(T);if (pre->rchild == NULL) {pre->rtag = 1;}}
}

(3)后序线索二叉树

#include "stdio.h"
#include "stdlib.h"typedef struct ThreadNode {char data;struct ThreadNode *lchild, *rchild;int ltag, rtag; // 左右线索标志
} ThreadNode, *ThreadTree;ThreadTree pre = NULL; // 使用单一指针void visit(ThreadNode *q) {if (q->lchild == NULL) {q->lchild = pre;q->ltag = 1;}if (pre != NULL && pre->rchild == NULL) {pre->rchild = q;pre->rtag = 1;}pre = q; // 直接赋值给 pre,不需要解引用
}// 后序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T) {if (T != NULL) {InThread(T->lchild); // 中序遍历左子树InThread(T->rchild); // 中序遍历右子树visit(T); // 访问根节点}
}void CreateInThread(ThreadTree T) {pre = NULL;if (T != NULL) {InThread(T);if (pre->rchild == NULL) {pre->rtag = 1;}}
}

http://www.lryc.cn/news/148570.html

相关文章:

  • 服务器前后端学习理解
  • python-数据分析-numpy、pandas、matplotlib的常用方法
  • ChatGPT⼊门到精通(5):ChatGPT 和Claude区别
  • ChatGPT 总结数据分析的所有知识点
  • hadoop-HDFS
  • 0202hdfs的shell操作-hadoop-大数据学习
  • 生活小记-挂号信
  • 3D点云处理:基于PCA的计算点云位姿(占位待整理)
  • 本地私有仓库、harbor私有仓库部署与管理
  • 尚硅谷SpringMVC (5-8)
  • jupyter notebook中查看python版本的解决方案
  • 动态字符串 String (完整源码)
  • 【深度学习】实验05 构造神经网络示例
  • 用了这么久SpringBoot却还不知道的一个小技巧
  • Websocket、SessionCookie、前端基础知识
  • 【云原生进阶之PaaS中间件】第一章Redis-2.4缓存更新机制
  • Qt——事件处理详解
  • 基于位置管理的企业员工考勤打卡系统设计 微信小程序
  • adb 查找应用包名,应用 Activity 等信息
  • 八、SpringBoot集成Kafka
  • 联网智能实时监控静电离子风机的工作流程
  • 第12章 微信支付
  • Java基础二十二(对集合元素排序比较)
  • (15)线程的实例认识:同步,异步,并发,并发回调,事件,异步线程,UI线程
  • 长胜证券:华为“黑科技”点燃A股炒作激情
  • Kubernetes(k8s)上部署redis5.0.14
  • frida动态调试入门01——定位关键代码
  • ASP.NET Core 8 的配置类 Configuration
  • MySql增量恢复
  • 设计模式--装饰者模式(Decorator Pattern)