线索化二叉树

    简而言之，n个结点的二叉树会形成n+1个空的指针域，那么就会造成指针的浪费，所以用这些空的指针指向该结点的在某种次序下的前驱或者后继结点的指针。这些指针称为线索，加上线索的二叉树称为线索二叉树。

二叉树的遍历的本质是将一个复杂的非线性结构转换为线性结构，使得每个节点都有了唯一的前驱和后继。（第一个节点无前驱，最后一个节点无后继）对于二叉树的一个节点，查找其左右子节点是方便的，其前驱后继只有在遍历中得到。

• 优点：利用线索化二叉树进行中序遍历时，不需要采用堆栈处理，速度比一般二叉树的遍历快，且节约存储空间，任意一个节点都能直接找到它的前驱和后继节点
• 不足：节点的插入和删除比较麻烦，且速度也比较慢。线索子树不能共用。

package Tree;

/**
 * @author ChrisPeng
 * @date 2022/3/15 21:43
 */
public class ThreadedBinaryTree {
    public static void main(String[] args) {
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        ThreadedBinaryTreeBuild tree = new ThreadedBinaryTreeBuild();
        tree.setRoot(root);
        tree.threadedNodes();

        //测试
        HeroNode leftNode = node5.getLeft();
        HeroNode rightNode = node5.getRight();
        System.out.println("10号节点的前驱节点是=" + leftNode);
        System.out.println("10号节点的后继节点是=" + rightNode);
    }
}

/**
 * n个节点的二叉链表中含有n+1个空指针域，利用二叉链表中的空指针域
 * 存放指向该节点在某种遍历次序下的前驱和后继节点的指针（这种附加的指针称为线索）
 * 加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树
 * 一个节点的前一个节点称为前驱节点
 * 一个节点的后一个节点，称为后继节点
 */
class ThreadedBinaryTreeBuild{
    private HeroNode root;
    //为了实现线索化，需要创建要给指向当前节点的前驱节点的指针
    private HeroNode pre = null;//总是保留前一个节点
    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //重载threadednodes方法
    public void threadedNodes(){
        this.threadedNodes(root);//为的是不在外层判断到底是不是空
    }
    // 中序线索化的操作

    /**
     *
     * @param node 当前线索化的节点
     */
    public void threadedNodes(HeroNode node){
        if (node == null)
            return;
        //线索化左子树
        threadedNodes(node.getLeft());
        //线索化中间节点
        //处理当前节点的前驱节点
        if (node.getLeft() == null){
            //让当前节点的做指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针的类型
            node.setLeftType(1);
        }
        //处理后继节点
        if (pre != null && pre.getRight() == null){
            //前驱节点的右指针指向当前节点
            pre.setRight(node);
            //修改前驱节点的右指针类型
            pre.setRightType(1);
        }
        //每处理一个节点后，让当前节点是下一个节点的前驱节点
        pre = node;
        //线索化右子树
        threadedNodes(node.getRight());
    }

    //删除节点
    public void delNote(int no){
        if (root != null){
            this.root = root;
            if (root.getNo() == no)
                root = null;
            else
                root.delNode(no);
        }else
            System.out.println("空树，不能删除！");
    }

    public void preOrder(){
        if (this.root != null)
            this.root.preOrder();
        else
            System.out.println("二叉树为空，无法遍历！");
    }
    public void infixOrder(){
        if (this.root != null)
            this.root.infixOrder();
        else
            System.out.println("二叉树为空，无法遍历！");
    }
    public void postOrder(){
        if (this.root != null)
            this.root.postOrder();
        else
            System.out.println("二叉树为空，无法遍历！");
    }

    public HeroNode preOrderSearch(int no){
        if (root != null)
            return root.preOrderSearch(no);
        else
            return null;
    }

    public HeroNode infixOrderSearch(int no){
        if (root != null)
            return root.infixOrderSearch(no);
        else
            return null;
    }
    public HeroNode postOrderSearch(int no){
        if (root != null)
            return root.postOrderSearch(no);
        else
            return null;
    }
}

class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;
    /**
     * 如果lefttype==0，表示指向的是左子树，如果是1则表示指向的是前驱节点
     * 如果righttype==0，则表示指向的是右子树，如果1表示指向后继节点
     */
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public HeroNode(int no, String name) {//一个node只有两个属性：编号和姓名
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

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

    public HeroNode getLeft() {
        return left;
    }

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

    public HeroNode getRight() {
        return right;
    }

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

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
    //递归删除节点
    public void delNode(int no){
        if (this.left != null && this.left.no == no){
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no){
            this.left = null;
            return;
        }
        if (this.left != null){
            this.left.delNode(no);
        }
        if (this.right != null){
            this.right.delNode(no);
        }
    }

    //前序遍历
    public void preOrder(){
        System.out.println(this);
        if (this.left != null)
            this.left.preOrder();
        if (this.right != null)
            this.left.preOrder();
    }
    public void infixOrder(){
        if (this.left != null)
            this.left.infixOrder();

        System.out.println(this);
        if (this.right != null)
            this.right.infixOrder();
    }

    public void postOrder(){
        if (this.left != null)
            this.left.postOrder();
        if (this.right != null)
            this.right.postOrder();
        System.out.println(this);
    }

    //前序查找
    public HeroNode preOrderSearch(int no){
        System.out.println("前序遍历...");
        if (this.no == no)
            return this;
        HeroNode resNode = null;
        if (this.left != null)
            resNode = this.left.preOrderSearch(no);
        if (resNode != null)
            return resNode;
        if (this.right != null)
            resNode = this.right.preOrderSearch(no);
        return resNode;
    }
    //终须查找
    public HeroNode infixOrderSearch(int no){
        HeroNode resNode = null;
        if (this.left != null)
            resNode = this.left.preOrderSearch(no);
        if (resNode != null)
            return resNode;
        System.out.println("中序遍历...");
        if (this.no == no)
            return this;

        if (this.right != null)
            resNode = this.right.preOrderSearch(no);
        return resNode;
    }
    public HeroNode postOrderSearch(int no){

        HeroNode resNode = null;
        if (this.left != null)
            resNode = this.left.preOrderSearch(no);
        if (this.right != null)
            resNode = this.right.preOrderSearch(no);
        if (resNode != null)
            return resNode;
        System.out.println("后序遍历...");
        if (this.no == no)
            return this;

        return resNode;
    }
}

• 线索化二叉树的遍历：

  线索化之后，各个节点的指向有所变化，因此原来的遍历方式不能再使用，需要使用新的方式遍历线索化二叉树，各个节点可以通过线性方式遍历，无需使用递归的方式，提高了遍历的效率，遍历的次序应该和中序遍历保持一致.

  就是先找到有前驱节点的节点（刚开始肯定是叶子节点，然后遍历有rightType的节点输出，然后将当前节点设置为右边的节点，进行下一轮的遍历）

  public void threadedList(){
          //存储当前遍历的节点
          HeroNode node = root;
          while (node != null){
              //循环的找到leftType==1的节点
              while (node.getLeftType() == 0)
                  node = node.getLeft();
              //打印当前的节点
              System.out.println(node);
              //如果当前节点的右指针指向的是后继节点，就一直输出
              while (node.getRightType() == 1){
                  node = node.getRight();
                  System.out.println(node);
              }
              //替换这个遍历的节点
              node = node.getRight();
          }
      }

赏

谢谢你请我吃糖果