线索二叉树
利用空指针域来真存放结点的前驱和后继信息
定义：
- 前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~
- 线索：指向前驱或后继结点的指针称为~
- 线索二叉树：加上线索的二叉链表表示的二叉树叫~
- 线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~
实现：
- 在有n个结点的二叉链表中必定有n+1个空链域
- 在线索二叉树的结点中增加两个标志域(0指结点，1左前右后)
- ltag :若 ltag=0, lchild 域指向左孩子；
- 若 ltar=1, lchild域指向其前驱
- rtag :若 rtag =0, rchild 域指向右孩子；
- 若 rtag=1, rchild域指向其后继
例如：遍历中序线索二叉树
在中序线索二叉树中找结点后继的方法：
（1）若rtag=1, 则rchild域直接指向其后继
（2）若rtag=0, 则结点的后继应是其右子树的左链尾（ltag=1)的结点
在中序线索二叉树中找结点前驱的方法：
（1）若ltag=1, 则lchild域直接指向其前驱
（2）若ltag=0, 则结点的前驱应是其左子树的右链尾（rtag=1)的结点
树和森林
树的存储结构有：双亲表示法、孩子表示法、孩子兄弟表示法。
1．双亲存储表示法
用一组地址连续的存储单元来存放树的结点，每个结点有两个域：
data域-----存放结点的信息；
parent域-----存放该结点唯一的双亲结点的位置（数组下标）
双亲表示法的存储结构描述为：
#define MaxTreeSize 100
typedef char DataType；
typedef struct{
DataType data；
int parent；
} PTreeNode；
typedef struct {
PTreeNode nodes[MaxTreeSize];
int r,n；//根结点的位置和结点个数
}PTree；
PTree T；
2、孩子表示法
把每个结点的孩子结点排列起来，看作线性表，且以单链表做存储结构。
孩子表示法的存储结构描述为：
typedef struct Cnode {
int child;
struct CNode *next;
} Cnode; /*孩子结点类型说明*/
typedef struct {
DataType data;
Cnode *firstchild;
} PTNode; /*数组的每个元素的类型说明*/
typedef struct {
PTNode nodes[MaxTreeSize];
int n,root;
} Ctree;
3、孩子兄弟表示法
用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。由于结点中的两个指针指示的分别为“孩子”和“兄弟”，故称为“孩子-兄弟链表”。( 左孩右兄 )
树的孩子兄弟链表的存储结构描述为：
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
} CSNode, *CSTree;
孩子兄弟存储结构的 优点 是可以方便地实现树和二叉树的相互转换和树的各种操作；
缺点 是查找当前结点的双亲结点比较麻烦。 解决方法：增设parent域。
森林转换成二叉树
转换原则：
(1)将森林中的每棵树转换成等价的二叉树；
(2)保留第一棵二叉树，从第二棵二叉树开始，依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，所有二叉树依此相连。
树转化为二叉树的意义 ：
1、因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。
2、所有的树中，2度树的链域（存储空间）利用率最高。
树和森林的遍历
1．树的遍历
所谓树的遍历，就是按照某种顺序依次访问树中各个结点，并使得每个结点只被访问一次。也就是把非线性结构的树结点变成线性序列的一种方式。
树的遍历方法有：
按广度优先遍历（即按层次遍历）
按深度优先遍历，又可分为：前序遍历和后序遍历
2．森林的遍历
森林的遍历可分为 前序遍历 与 中序遍历
Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。
它的内容包括：
- 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
- 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
- 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
- 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
- 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
- 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
- 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
- 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw
目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：
想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询
同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。
