[数据结构与算法]线索化二叉树

思路

左边是原二叉树，线索化二叉树就是将二叉树中左右指针为空的地方指向其前驱和后继节点，变为右图的样子。?

?代码

核心方法：

//再遍历自身
            //设置前驱节点
        if (root.getLeft() == null){
            root.setLeft(proNote);
            root.setLeftType(1);
        }
            //设置后继节点
        if (proNote != null && proNote.getRight() == null){
            this.proNote.setRight(root);
            proNote.setRightType(1);
        }
        proNote = root;

先设置前驱节点，再设置后继节点时，pre是指向当前的节点的，root已经指向当前节点的父节点了，所以要设置proNote了。当回溯时就将pro赋值为root。

public void midClue(Hero2 root){

        if (root == null){
            System.out.println("二叉树为空");
            return;
        }
        //先遍历左孩子
        if (root.getLeft() != null){
            midClue(root.getLeft());
        }
        //再遍历自身
            //设置前驱节点
        if (root.getLeft() == null){
            root.setLeft(proNote);
            root.setLeftType(1);
        }
            //设置后继节点
        if (proNote != null && proNote.getRight() == null){
            this.proNote.setRight(root);
            proNote.setRightType(1);
        }
        proNote = root;

        //最后遍历右孩子
        if (root.getRight() != null){
            midClue(root.getRight());
        }
    }

总体代码?

package DataStructures.BinaryTree;

/**
 * @author ：ALi
 * @date ：Created in 2021/11/29 19:42
 * @description：线索化二叉树
 * @modified By：
 * @version: $
 */
public class BinaryTree {
    public static void main(String[] args) {

        Hero2 root2 = new Hero2(1, "宋江");
        Hero2 hero12 = new Hero2(3, "吴用");
        Hero2 hero22 = new Hero2(6, "卢俊义");
        Hero2 hero32 = new Hero2(8, "林冲");
        Hero2 hero42 = new Hero2(14, "卢俊义");
        Hero2 hero52 = new Hero2(10, "林冲");
        root2.setLeft(hero12);
        root2.setRight(hero22);
        hero12.setLeft(hero32);
        hero12.setRight(hero52);
        hero22.setLeft(hero42);

        HeroList2 binaryTree2 = new HeroList2();
        binaryTree2.setHead(root2);
        binaryTree2.midClue(root2);
        System.out.println(hero52.getLeft());
        System.out.println(hero52.getRight());
    }

}

class Hero2 {
    private int id;
    private String name;
    private Hero2 left;
    private Hero2 right;
    private int LeftType;//0是左孩子，1是前驱节点
    private int RightType;//0是右孩子，1是后继节点

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    public Hero2() {
    }

    public Hero2(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Hero2{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public void setLeft(Hero2 left) {
        this.left = left;
    }

    public void setRight(Hero2 right) {
        this.right = right;
    }

    public Hero2 getLeft() {
        return left;
    }

    public Hero2 getRight() {
        return right;
    }

    public void setId(int id) {
        this.id = id;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getLeftType() {
        return LeftType;
    }

    public void setLeftType(int leftType) {
        LeftType = leftType;
    }

    public int getRightType() {
        return RightType;
    }

    public void setRightType(int rightType) {
        RightType = rightType;
    }
}
class HeroList2 {
    private Hero2 head;
    private Hero2 proNote = null;

    public HeroList2() {
    }

    @Override
    public String toString() {
        return "HeroList2{" +
                "head=" + head +
                ", proNote=" + proNote +
                '}';
    }

    public void setHead(Hero2 head) {
        this.head = head;
    }

    public Hero2 getHead() {
        return head;
    }

    public Hero2 getProNote() {
        return proNote;
    }

    public void setProNote(Hero2 proNote) {
        this.proNote = proNote;
    }

    public void midClue(Hero2 root){

        if (root == null){
            System.out.println("二叉树为空");
            return;
        }
        //先遍历左孩子
        if (root.getLeft() != null){
            midClue(root.getLeft());
        }
        //再遍历自身
            //设置前驱节点
        if (root.getLeft() == null){
            root.setLeft(proNote);
            root.setLeftType(1);
        }
            //设置后继节点
        if (proNote != null && proNote.getRight() == null){
            this.proNote.setRight(root);
            proNote.setRightType(1);
        }
        proNote = root;

        //最后遍历右孩子
        if (root.getRight() != null){
            midClue(root.getRight());
        }
    }
}