@toc

1 二叉树中序线索化与中序线索化遍历

1.1 重载中序线索化二叉树

public void threadedNode() {
    threadedNode(root);
}

1.2 中序遍历线索化二叉树的方法

public void threadedList() {
    //定义一个变量，存储当前遍历的结点，从root开始
    HeroNode node = root;
    while (node != null) {
        //循环的找到leftType == 1的结点，第一个找到就是8结点
        //后面随着遍历而变化,因为当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();
 
    }
}

1.3 中序线索化二叉树

public void threadedNode(HeroNode node) {
    if (node == null) {
        return;
    }
    //线索化左子树
    threadedNode(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;
    //线索化右子树
    threadedNode(node.getRight());
}