数据结构与算法__04--二叉树后序线索化与后序线索化遍历（Java语言版）

(目录)

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

本文介绍了二叉树后序线索化与后序线索化遍历。

1.1 后序线索化二叉树

//后序线索化二叉树   8,10,3,14,6,1
public void threadedPostNode(HeroNode node) {
    if (node == null) {
        return;
    }
    //线索化左子树
    threadedPostNode(node.getLeft());
 
    //线索化右子树
    threadedPostNode(node.getRight());
    //线索化当前节点
    if (node.getLeft() == null) {
        node.setLeft(pre);
        node.setLeftType(1);
    }
    if (pre != null && pre.getRight() == null) {
        pre.setRight(node);
        pre.setRightType(1);
    }
    pre = node;
}

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

public void threadedPostList() {//8,10,3,14,6,1
    HeroNode node = root;
    while(node != null && node.getLeftType()!=1) {
        node = node.getLeft();
    }
 
    HeroNode pre = null;
    while(node != null) {
        //右节点是线索
        if (node.getRightType() == 1) {
            System.out.println(node);
            pre = node;
            node = node.getRight();
 
        } else {
            //如果上个处理的节点是当前节点的右节点
            if (node.getRight() == pre) {
                System.out.println(node);
                if (node == root) {
                    return;
                }
 
                pre = node;
                node = node.getParent();
 
            } else {    //如果从左节点的进入则找到有子树的最左节点
                node = node.getRight();
                while (node != null && node.getLeftType() !=1) {
                    node = node.getLeft();
                }
            }
        }
    }
}