本文共 2649 字，大约阅读时间需要 8 分钟。

????????

1. ??????????

??????????????????????????????????????????????????????????????????????????????????????????????????????????????

??????????????????????????????????????????????????????????????????????????????????????????????????????????????????

2. ?????

2.1 ??????????

??????????????????????????????????????????????????

2.2 ????

public void prethreadedNodes(HeroNode node) {
    if (node == null) {
        return;
    }
    if (node.getLeft() == null) {
        node.setLeft(pre);
        node.setLeftType(1);
    }
    if (pre != null && pre.getRight() == null) {
        pre.setRight(node);
        pre.setRightType(1);
    }
    pre = node;
    if (node.getLeftType() != 1) {
        prethreadedNodes(node.getLeft());
    }
    if (node.getRightType() != 1) {
        prethreadedNodes(node.getRight());
    }
}

2.3 ????

????????????????????

• 10?????????3?????????1????
• ??????????????1 ? 3 ? 8 ? 10 ? 6 ? 14?

3. ?????

3.1 ??????????

???????????????????????????????????

3.2 ????

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());
}

3.3 ????

????????????????????

• 10?????????3?????????1????
• ??????????????8 ? 3 ? 10 ? 1 ? 14 ? 6?

4. ?????

4.1 ??????????

????????????????????????????????????

4.2 ????

public void lastthreadedNodes(HeroNode node) {
    if (node == null) {
        return;
    }
    lastthreadedNodes(node.getLeft());
    lastthreadedNodes(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;
}

4.3 ????

????????????????????

• 10?????????8?????????3????
• ??????????????8 ? 10 ? 3 ? 14 ? 6 ? 1?

5. ??

???????????????????????????????????????????????????????????????????????????????????????