算法-线索二叉树

概念性的东西，自行百度。

按照国际管理，直接上代码来分析。

Node节点类

package com.tree.thread;
 
/**
 * Author: lihao
 * Date：2017/8/30
 * Description:ThreadBinaryTree Node
 */
public class Node
{
    private int data;
    private Node left;
    private boolean leftIsThread;        // 左孩子是否为线索
    private Node right;
    private boolean rightIsThread;       // 右孩子是否为线索
 
    public Node(int data)
    {
        this.data = data;
        this.left = null;
        this.leftIsThread = false;
        this.right = null;
        this.rightIsThread = false;
    }
 
    public int getData()
    {
        return data;
    }
 
    public void setData(int data)
    {
        this.data = data;
    }
 
    public Node getLeft()
    {
        return left;
    }
 
    public void setLeft(Node left)
    {
        this.left = left;
    }
 
    public boolean isLeftIsThread()
    {
        return leftIsThread;
    }
 
    public void setLeftIsThread(boolean leftIsThread)
    {
        this.leftIsThread = leftIsThread;
    }
 
    public Node getRight()
    {
        return right;
    }
 
    public void setRight(Node right)
    {
        this.right = right;
    }
 
    public boolean isRightIsThread()
    {
        return rightIsThread;
    }
 
    public void setRightIsThread(boolean rightIsThread)
    {
        this.rightIsThread = rightIsThread;
    }
 
    @Override
    public boolean equals(Object obj)
    {
        if (obj instanceof Node)
        {
            Node temp = (Node) obj;
            if (temp.getData() == this.data)
            {
                return true;
            }
        }
        return false;
    }
 
    @Override
    public int hashCode()
    {
        return super.hashCode() + this.data;
    }
}
JAVA

创建二叉树、二叉树中序线索化(线索化有3种，此处单讲中序)

package com.tree.thread;
 
public class ThreadTree {
    private Node root;         // 根节点
    private Node pre = null;   // 线索化的时候保存前驱
 
    public ThreadTree() {
        this.root = null;
        this.pre = null;
    }
 
    public ThreadTree(int[] data) {
        this.pre = null;
        this.root = createTree(data, 0);   // 创建二叉树
    }
 
    /**
     * 创建二叉树
     */
    public Node createTree(int[] data, int index) {
        if (index >= data.length) {
            return null;
        }
        Node node = new Node(data[index]);
        node.setLeft(createTree(data, 2 * index + 1));
        node.setRight(createTree(data, 2 * index + 2));
        return node;
    }
 
    /**
     * 将以root为根节点的二叉树线索化  中序法
     */
    public void inThread(Node root) {
        if (root != null) {
            inThread(root.getLeft());     // 线索化左孩子
            if (null == root.getLeft())   // 左孩子为空
            {
                root.setLeftIsThread(true);    // 将左孩子设置为线索
                root.setLeft(pre);
            }
            if (pre != null && null == pre.getRight())  // 右孩子为空
            {
                pre.setRightIsThread(true);
                pre.setRight(root);
            }
            pre = root;                 //每次将当前节点设置为pre
            inThread(root.getRight());       // 线索化右孩子
        }
    }
 
    /**
     * 中序遍历线索二叉树
     */
    public void inThreadList(Node root) {
        if (root == null) {
            return;
        }
        //查找中序遍历的起始节点
        while (root != null && !root.isLeftIsThread()) {
            root = root.getLeft();
        }
        while (root != null) {
            System.out.print(root.getData() + ",");
            if (root.isRightIsThread())   // 如果右孩子是线索
            {
                root = root.getRight();
            } else         // 有右孩子
            {
                root = root.getRight();
                while (root != null && !root.isLeftIsThread()) {
                    root = root.getLeft();
                }
            }
        }
 
    }
 
 
    /**
     * 中序遍历
     */
    public void inList(Node root) {
        if (root != null) {
            inList(root.getLeft());
            System.out.print(root.getData() + ",");
            inList(root.getRight());
        }
    }
 
    public Node getRoot() {
        return root;
    }
 
    public void setRoot(Node root) {
        this.root = root;
    }
}
JAVA