数据结构--二叉树的线索化

布满荆棘的人生 2023-10-03 18:57 55阅读 0赞

中序线索化--代码实现、一边遍历，一边线索化

注意：1.非空二叉树才能线索化

2.无论是先序，中序，后序 都要在最后 处理最后一个节点，rchild=null，rtag = 0

为什么线索化？答：为了找前驱和后继

![f4ba8d5f6c7f4e778728c38e7212afbe.png][]

全部的代码实现

![1b6835ec7a92453bb32753a71bf4fbc1.png][]

先序线索化--代码实现

注意：在遍历的时候，会有一个问题，你在线索化后，你的D节点 线索指向前驱的时候，然后，去看G，G线索没有问题，当你回到B时发现，B的左子树依然有 子树，就会去线索化B，B已经线索化过了，就会一直转圈圈。

解决方案：在遍历时加上ltag 的条件，ltag =0 就是已经线索化过了，可以不用去线索化了

![14362bee93874ab0929406035cec5a4a.png][]

![c2d150f2224a4980a1125a1bca226a41.png][]

后序线索化--代码实现

![efc62252081a4b829b0f56c247633f0f.png][]

中序线索二叉树找中序后继

找中序后继-- 一定有右子树，如果右子树，是最后一个节点，就直接找后继就行，如果不是最后一个节点，需要找到右子树的 最左下节点。

p->rtag ==1 ,就是没有右子树了，线索化了，可以使用next = p->rchild 直接找到后继

p->rtag ==0,就是有右子树，你需要找到右子树的 最左下节点，然后返回后继线索

![458f00c38f2a47b1944bb4e3ff4b1209.png][]

中序线索二叉树找 中序前驱

找中序前驱--一定有左子树，如果左子树，是最后一个节点，就直接找前驱就行，如果不是最后一个节点，需要找到左子树的 最右下节点。

![e7d2da5b962445d5b779848a87811610.png][]

先序线索二叉树找 先序后继

![f90889c495de4a3eaba30dfff4953c38.png][]

先序线索二叉树 找 先序前驱

因为 你是用的二叉链表 根左右 ，你找到不到 先序前驱，除非用土办法从头开始先序遍历，还有一种就是 三叉链表，有个指针指向父节点

![a1399d8661d84d5a818c5c58e1aa86ad.png][]

用三叉链表找 先序前驱，有四种情况

![1bb9b8ac95ae4cee8fdcacbd9b75adbe.png][]

后序线索二叉树找后序前驱![400a280777b543068cfb15074c6779cb.png][]

后序线索二叉树 找后序节点，和（ 用三叉链表找 先序前驱）相似![8072de9edfa841ca95e5a1c9b445525c.png][]

总结

![7197edce5cf444a9992c4a2e8e996f53.png][]

[f4ba8d5f6c7f4e778728c38e7212afbe.png]: https://img-blog.csdnimg.cn/f4ba8d5f6c7f4e778728c38e7212afbe.png
[1b6835ec7a92453bb32753a71bf4fbc1.png]: https://img-blog.csdnimg.cn/1b6835ec7a92453bb32753a71bf4fbc1.png
[14362bee93874ab0929406035cec5a4a.png]: https://img-blog.csdnimg.cn/14362bee93874ab0929406035cec5a4a.png
[c2d150f2224a4980a1125a1bca226a41.png]: https://img-blog.csdnimg.cn/c2d150f2224a4980a1125a1bca226a41.png
[efc62252081a4b829b0f56c247633f0f.png]: https://img-blog.csdnimg.cn/efc62252081a4b829b0f56c247633f0f.png
[458f00c38f2a47b1944bb4e3ff4b1209.png]: https://img-blog.csdnimg.cn/458f00c38f2a47b1944bb4e3ff4b1209.png
[e7d2da5b962445d5b779848a87811610.png]: https://img-blog.csdnimg.cn/e7d2da5b962445d5b779848a87811610.png
[f90889c495de4a3eaba30dfff4953c38.png]: https://img-blog.csdnimg.cn/f90889c495de4a3eaba30dfff4953c38.png
[a1399d8661d84d5a818c5c58e1aa86ad.png]: https://img-blog.csdnimg.cn/a1399d8661d84d5a818c5c58e1aa86ad.png
[1bb9b8ac95ae4cee8fdcacbd9b75adbe.png]: https://img-blog.csdnimg.cn/1bb9b8ac95ae4cee8fdcacbd9b75adbe.png
[400a280777b543068cfb15074c6779cb.png]: https://img-blog.csdnimg.cn/400a280777b543068cfb15074c6779cb.png
[8072de9edfa841ca95e5a1c9b445525c.png]: https://img-blog.csdnimg.cn/8072de9edfa841ca95e5a1c9b445525c.png
[7197edce5cf444a9992c4a2e8e996f53.png]: https://img-blog.csdnimg.cn/7197edce5cf444a9992c4a2e8e996f53.png