内容来自尚硅谷Java数据结构与java算法（Java数据结构与算法）_哔哩哔哩_bilibili

写在前面:本文内容大致和原视频内老师的笔记内容相同，会偶尔插入自己的注释和理解，尽量会完成作业

本次作业完成了，有借鉴部分，跟着debug跑过一遍后能看懂，但是如果自己写，还是有点难度

10.3.1先看一个问题

将数列{1,3,6,8,10,14}构建成一棵二叉树 n+1 = 7

1.      当我们对上面的二叉树进行中序遍历时，数列为{8,3,10,1,6,14}

2.      但是6,8,10,14 这几个节点的左右指针，并没有完全的利用上.

3.      如果我们希望充分的利用各个节点的左右指针，让各个节点可以指向自己的前后节点,怎么办?

4.      解决方案-线索二叉树

10.3.2线索二叉树的基本介绍

1.      n个结点的二叉链表中含有n+1【公式2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索")

2.      这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种

3.      一个结点的前一个结点，称为前驱结点

4.      一个结点的后一个结点，称为后继结点

10.3.3线索二叉树的应用案例

应用案例说明:将下面的二叉树，进行中序线索二叉树。中序遍历的数列为{8,3,10,1,14,6}

思路分析 中序遍历结果：{8,3,10,1,14,6}

说明:当线索化二叉树后，Node节点的属性left和right，有如下情况:

1.      left 指向的是左子树,也可能是指向的前驱节点.比如①节点left 指向的左子树,而⑩节点的 left 指向的就是前驱节点.

2.      right指向的是右子树，也可能是指向后继节点，比如①节点right 指向的是右子树，而⑩节点的right 指向的是后继节点.

代码实现

10.3.4遍历线索化二叉树

1)说明:对前面的中序线索化的二叉树，进行遍历

2)分析:因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致。

3)代码:

10.3.5线索化二叉树课后作业

我这里讲解了中序线索化二叉树，前序线索化二叉树和后序线索化二叉树的分析思路类似，同学们作为课后作业完成.

作业完成了，但是没有完成，代码上面有

借鉴了CSDN的一位大佬的解答

我根据大佬解答结合韩老师的代码，才完成了这次作业，运行起来是没有问题了，理解起来还需要时间，主要是后序遍历线索化树有点难度

https://blog.csdn.net/UncleMing5371/article/details/54176252

https://blog.csdn.net/UncleMing5371/article/details/54291221