树
二叉树
树的遍历（递归）
树的深度
后续遍历算法的变种，求左子树高度，求右子树高度，选取最大深度+1（+1因为要带上根节点）
总结
二叉树层序遍历
辅助队列
访问该节点时需要将该节点的左右孩子入队列
算法实现
- 将根节点入队
- 循环（条件队列不为空）
- 队列头元素出队
- 访问节点visit()自定义操作
- 将访问节点的左孩子入队 将右孩子入队。
由遍历序列构造二叉树
不同二叉树遍历序列
一个前、中、后序和层序遍历能对应多种二叉树形态
结论
必须要有中序遍历
前序+中序 构造二叉树
-
根据前序遍历确定 根节点为A 对应到中序遍历中， 可以推导出右子树为E 而 B、D、C为左子树
-
-
对应前序遍历
-
-
根据前序遍历可以推导出D为左子树的根节点。
-
-
对应到中序遍历中
-
-
可以推出 B为左孩子节点 C为右孩子节点
-
前序+中序序列主要先从前序遍历序列找到根节点，对应到中序遍历序列，找到左孩子与右孩子，一直重复此过程
举例
手推
后续+中序构造二叉树
必须先找到根节点，对应中序序列找到左孩子与右孩子，在再看左孩子与右孩子的根节点，重复此过程
举例
层序+中序构造二叉树
层序遍历先访问的是根节点 ，在访问左子树的根节点，右子树的根节点。
- 先找到根节点
- 对应到中序遍历中 找到左子树 与右子树
- 层序遍历最先访问的是根节点
- 重复2
举例
手推
特殊情况 左子树为空
总结
必须有中序序列才能构造二叉树
线索二叉树
二叉树的中序遍历
当要查找一个元素、寻找一个元素的前驱，一个元素的后继，只能从头到尾遍历一遍二叉树，普通的二叉树已经不能满足需要。
中序线索二叉树
D无后继指向Null
根据中序遍历的序列，将叶子节点的前驱使用左孩子指针指向。后继用右孩子指向。使得寻找二叉树元素的前驱后继更加简单
存在问题：例如A节点的右指针指向了C，而不是它的后继节点F。
线索二叉树的存储结构
相对于普通的二叉树多了两个标志位： tag==0标志指向的是孩子，tag为1标志指向线索。
存储视角
先序线索二叉树
存储视角
后续线索二叉树
存储视角
总结
二叉树线索化代码实现
土办法实现
使用pre 指针指向访问节点的前驱节点，用q指针记录当前访问节点。
中序线索化
使用pre指针指向前驱。并且线索化右孩子（修改后继），q指针指向当前节点，线索化左孩子（修改前驱）。
完整代码
先序线索化
后续线索化
线索化java代码实现
TreeNode 定义
package wangdao.TreeNode;
/**
* @description:
* @author: hanmingbao
* @create: 2022-05-10 14:26
* 线索化二叉树
**/ //定义二叉树
class TreeNode {
String data;
TreeNode left;
TreeNode right;
int ltag; //线索标志位 0 标志位指向左孩子节点 1表示指向前驱
int rtag;// 0 标志位指向右孩子节点 1表示指向后继
TreeNode() {
}
public TreeNode(String data, int ltag, int rtag) {
this.data = data;
this.left = left;
this.right = right;
}
public TreeNode(String data, TreeNode left, TreeNode right, int ltag, int rtag) {
this.data = data;
this.left = left;
this.right = right;
this.ltag = ltag;
this.rtag = rtag;
}
@Override
public String toString() {
return "TreeNode{" +
"data='" + data + '\'' +
", left=" + left +
", right=" + right +
", ltag=" + ltag +
", rtag=" + rtag +
'}';
}
}
后续线索化实现
package wangdao.TreeNode;
/**
* @author 韩明保
* @version 1.0
* @description: TODO 线索化二叉树
* @date 2022/5/10 16:55
*/
public class ThreadNode {
public static void main(String[] args) {
TreeNode root=new TreeNode("A",0,0);
TreeNode treeNodeB=new TreeNode("B",0,0);
TreeNode treeNodeC=new TreeNode("C",0,0);
TreeNode treeNodeD=new TreeNode("D",0,0);
TreeNode treeNodeE=new TreeNode("E",0,0);
TreeNode treeNodeF=new TreeNode("F",0,0);
TreeNode treeNodeG =new TreeNode("G",0,0);
//构建的二叉树
root.left=treeNodeB;
root.right=treeNodeC;
treeNodeB.left=treeNodeD;
treeNodeB.right=treeNodeE;
treeNodeC.left=treeNodeF;
treeNodeC.right=null;
treeNodeD.left=null;
treeNodeD.right=treeNodeG;
treeNodeE.left=null;
treeNodeE.right=null;
treeNodeF.left=null;
treeNodeF.right=null;
Soulution soulution=new Soulution();
System.out.println("中序线索化");
soulution.createThreadTree(root);
soulution.visitThreadNode(root);
}
}
class Soulution{
//指向当前访问节点的前驱
TreeNode pre;
//线索化二叉树
public void createThreadTree(TreeNode node){
pre=null;
if (node!=null){
inorder(node);
if (pre.right==null){//处理最后一个节点
pre.rtag=1;
}
}
}
public void inorder(TreeNode node){
if (node!=null){
//左子树
inorder(node.left);
//根
visit(node);
//右子树
inorder(node.right);
}
}
public void visit(TreeNode cur){
if (cur.left==null){ //当前节点左子树为空 线索化左子树
cur.left=pre;
cur.ltag=1;
}
if (pre!=null && pre.right==null){ //建立前驱节点的后继线索化
pre.right=cur;
cur.rtag=1;
}
pre=cur;
System.out.println(cur.ltag+" "+cur.data+"\t"+cur.rtag);
}
public void visitThreadNode(TreeNode cur){
}
}