二叉树链表中有很多空指针，比如叶子节点，会有左右孩子两个空指针。如何把这些空指针利用起来呢？那就是线索二叉树
在这些节点上，可以存储按照二叉树某种遍历顺序的前后节点，这样就不需要每次都遍历二叉树，从而快速点位节点。
哪一种遍历顺序是最有效的呢？要求是最好有两个空指针的节点在非空节点的中间，这样就可以记录前前驱后继节点。 这个遍历方法叫中序遍历方法。这样包含线索的二叉树，叫做线索二叉树
线索二叉树节点
因为不是所有的节点都包含两个空指针，如果只含有一个空指针的时候，就无法判断，另一个非空指针是指向前驱或者后继或者是孩子节点，所以，在节点结构中增加2bit，用于指示是指针的类型。
首先定义数据类型
定义节点：注意枚举的使用，默认从0开始
只有构建了线索二叉树，才能使用非迭代的方法，通过前驱和后继的方法，通过迭代遍历二叉树 。
线索二叉树其实是一个线性双循环链表，里面有一个很关键的头结点，这个是线性表中的结构，不同于根节点
树节点 创建中序线索二叉树 遍历中序线索二叉树 创建前序线索二叉树 遍历前序线索二叉树 参考：https://bl...
1、线索二叉树的引入 在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或...
定义二叉树创建方法 对二叉树进行中序线索化 遍历线索二叉树 测试
线索二叉树构成 线索化的节点 实现
** 顺序存储 ** 线索化二叉树 线索化代码实现
二叉树链表中有很多空指针，比如叶子节点，会有左右孩子两个空指针。如何把这些空指针利用起来呢？那就是线索二叉树 在这...
原链接：理解线索二叉树|CloudWong 线索二叉树原理 遍历二叉树的其实就是以一定规则将二叉树中的结点排列成一...
题目：线索二叉树的更新所谓线索二叉树的更新是指在线索二叉树中插入一个结点或者删除一个结点。一般情况下，这些操作有可...
定义 在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历...
概念 在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行...
本文标题：2018-03-28 线索二叉树
本文链接：https://www.haomeiwen.com/subject/dllycftx.html
网友评论