树

二叉树

树的遍历（递归）

树的深度

后续遍历算法的变种，求左子树高度，求右子树高度，选取最大深度+1（+1因为要带上根节点）

总结

二叉树层序遍历

辅助队列

访问该节点时需要将该节点的左右孩子入队列

算法实现

1. 将根节点入队
2. 循环（条件队列不为空）
3. 队列头元素出队
4. 访问节点visit()自定义操作
5. 将访问节点的左孩子入队 将右孩子入队。

由遍历序列构造二叉树

不同二叉树遍历序列

一个前、中、后序和层序遍历能对应多种二叉树形态

结论

必须要有中序遍历

前序+中序 构造二叉树

1. 根据前序遍历确定 根节点为A 对应到中序遍历中， 可以推导出右子树为E 而 B、D、C为左子树

2. 

3. 对应前序遍历

4. 

5. 根据前序遍历可以推导出D为左子树的根节点。

6. 

7. 对应到中序遍历中

8. 

9. 可以推出 B为左孩子节点 C为右孩子节点

10. 

前序+中序序列主要先从前序遍历序列找到根节点，对应到中序遍历序列，找到左孩子与右孩子，一直重复此过程

举例

手推

后续+中序构造二叉树

必须先找到根节点，对应中序序列找到左孩子与右孩子，在再看左孩子与右孩子的根节点，重复此过程

举例

层序+中序构造二叉树

层序遍历先访问的是根节点 ，在访问左子树的根节点，右子树的根节点。

1. 先找到根节点
2. 对应到中序遍历中 找到左子树 与右子树
3. 层序遍历最先访问的是根节点
4. 重复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){

    }
}