线索二叉树的简单写法

package com.xiejianjun.day08.threadBinaryTreeDemo;



public class ThreadBinaryTreeDemo {
    public static void main(String[] args) {
        BinaryNode one = new BinaryNode(1, "one");
        BinaryNode two = new BinaryNode(2, "two");
        BinaryNode three = new BinaryNode(3, "three");
        BinaryNode four = new BinaryNode(4, "four");
        BinaryNode five = new BinaryNode(5, "five");
        one.left = two;
        one.right = three;
        two.left = four;
        three.right = five;
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(one);
        binaryTree.preRootOrder();

        binaryTree.deleteNodeById(4);
        binaryTree.preRootOrder();
    }
}

class BinaryTree {
    public BinaryNode root;

    public void setRoot(BinaryNode root) {
        this.root = root;
    }

    public void preRootOrder() {
        System.out.println("前序遍历根节点");
        if (this.root != null)
            this.root.preOrder();
    }

    public void inRootOrder() {
        System.out.println("中序遍历根节点");
        if (this.root != null)
            this.root.inOrder();
    }

    public void postRootOrder() {
        System.out.println("后序遍历根节点");
        if (this.root != null)
            this.root.postOrder();
    }

    public void deleteNodeById(int id) {
        System.out.printf("开始删除值为%d的结点", id);
        if (this.root == null) {
            System.out.println("空树");
            return;
        }
        if (this.root.id == id) {
            this.root = null;
        } else {
            this.root.deleteNode(id);
        }
    }

}

class BinaryNode {
    public int id;
    public String name;
    public BinaryNode left;
    public BinaryNode right;
    public int leftType = 0;
    public int rightType = 0;
    public BinaryNode pre = null;

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

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

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

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

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

    public void deleteNode(int id) {
        if (this.left != null) {
            if (this.left.id == id) {
                this.left = null;
                return;
            } else {
                this.left.deleteNode(id);
            }
        }

        if (this.right != null) {
            if (this.right.id == id) {
                this.right = null;
            } else {
                this.right.deleteNode(id);
            }
        }

    }

    public boolean isLeaf(BinaryNode node) {
        return node.left == null && node.right == null;
    }


    public void deleteNode2(int id) {
        // 叶子结点那直接删除
        if (this.left != null) {
            if (this.left.id == id) {
                if (isLeaf(left)) this.left = null;
                return;
            } else {
                this.left.deleteNode2(id);
            }
        }

        if (this.right != null) {
            if (this.right.id == id) {
                if (isLeaf(right)) this.right = null;

            } else {
                this.right.deleteNode2(id);
            }
        }

    }

    public void threadTreeNode(BinaryNode node) {
        if (node == null) {
            return;
        }
        // 先中序线索化左子树
        threadTreeNode(node.left);
        // 线索化当前结点
        // 先处理当前结点的前驱结点，如果当前节点的左子树为空，则让其指向前驱结点，并将leftType置为1
        if (node.left == null) {
            node.left = pre;
            node.leftType = 1;
        }
        // 因为树是单向的，所以要在下一个结点处判断前一个结点的右子树是否为空，若为空，则将上一个结点的右子树指向自己，即后继结点的线索化
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.rightType = 1;
        }
        pre = node;
        // 再中序线索化右子树
        threadTreeNode(node.right);
    }


}

关键代码:

public void threadTreeNode(BinaryNode node) {
        if (node == null) {
            return;
        }
        // 先中序线索化左子树
        threadTreeNode(node.left);
        // 线索化当前结点
        // 先处理当前结点的前驱结点，如果当前节点的左子树为空，则让其指向前驱结点，并将leftType置为1
        if (node.left == null) {
            node.left = pre;
            node.leftType = 1;
        }
        // 因为树是单向的，所以要在下一个结点处判断前一个结点的右子树是否为空，若为空，则将上一个结点的右子树指向自己，即后继结点的线索化
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.rightType = 1;
        }
        pre = node;
        // 再中序线索化右子树
        threadTreeNode(node.right);
    }

精髓在于由于二叉树单向的特点，需要设置前驱结点，并且利用了第一个结点无须设置前驱结点的特性，绕开了第一层的设置，非常精妙