中序线索二叉树的简单实现（Java）

中序线索二叉树的简单实现（Java）

二叉树的代码稍微有点抽象，并且运用了递归，猛一看会有点难以理解，建议在了解理论知识的前提下，在草稿纸上画一个二叉树，结合代码实现线索二叉树。

1.定义结点

package tree.cluetree;

public class Node {

    private int no;

    private String name;

    private Node left;

    private Node right;

    // 0表示左子树 1表示前驱结点
    private int noLeft;

    // 0表示右子树 1表示后继结点
    private int noRight;

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", 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 Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

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

    public int getNoLeft() {
        return noLeft;
    }

    public void setNoLeft(int noLeft) {
        this.noLeft = noLeft;
    }

    public int getNoRight() {
        return noRight;
    }

    public void setNoRight(int noRight) {
        this.noRight = noRight;
    }

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

}

2.定义线索二叉树

package tree.cluetree;

public class ClueTree {

    private Node root;

    // 初始化前驱结点
    private Node pre = null;

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

    
    public void clueNode(Node node) {
        if (node == null) {
            return;
        }

        // 线索化左子树
        clueNode(node.getLeft());

        // 左下结点为中序遍历第一个结点，前驱结点设为空
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setNoLeft(1);
        }

        // 如果当前节点的前驱结点不为空并且其右子树为空，则把当前结点设为其前驱结点的后继结点
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setNoRight(1);
        }


        pre = node;

        clueNode(node.getRight());

    }

    // 中序遍历线索二叉树
    public void clueList() {
        Node node = root;

        while (node != null) {
            while (node.getNoLeft() == 0) {
                node = node.getLeft();
            }

            System.out.println(node);

            while (node.getNoRight() == 1) {
                node = node.getRight();
                System.out.println(node);
            }

            node = node.getRight();
        }
    }

}

3.简单测试

package tree.cluetree;

import tree.cluetree.Node;

public class Test {
    public static void main(String[] args) {

        Node root = new Node(0, "zzz");
        Node node1 = new Node(1, "aaa");
        Node node2 = new Node(2, "bbb");
        Node node3 = new Node(3, "ccc");
        Node node4 = new Node(4, "ddd");
        Node node5 = new Node(5, "eee");
        Node node6 = new Node(6, "fff");


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

        ClueTree t = new ClueTree();
        t.setRoot(root);

        // 把普通二叉树线索化为线索二叉树
        t.clueNode(root);

        t.clueList();

        System.out.println("node4节点的前驱是：" + node4.getLeft().getNo() + "  后继节点是:" + node4.getRight().getNo() );



    }

}