线索二叉树原理、中序线索化(Java实现)

一、线索二叉树原理

20170106111258885.jpg

中序遍历

D , B , A , E ,C, F

通过观察上面的二叉链表,存在着若干个没有指向的空指针域。对于一个有n个节点的二叉链表,每个节点有指向左右节点的2个指针域,整个二叉链表存在2n个指针域。而n个节点的二叉链表有n-1条分支线,那么空指针域的个数=2n-(n-1) = n+1个空指针域,从存储空间的角度来看,这n+1个空指针域浪费了内存资源。

从另外一个角度来分析,如果我们想知道按中序方式遍历二叉链表时B节点的前驱节点或者后继节点时,必须要按中序方式遍历二叉链表才能够知道结果,每次需要结果时都需要进行一次遍历,是否可以考虑提前存储这种前驱和后继的关系来提高时间效率呢?
综合以上两方面的分析,可以通过充分利用二叉链表中的空指针域,存放节点在某种遍历方式下的前驱和后继节点的指针。我们把这种指向前驱和后继的指针成为线索,加上线索的二叉链表成为线索链表,对应的二叉树就成为“线索二叉树(Threaded Binary Tree)” 。

简而言之就是利用二叉树的空的节点,如果这个节点,存在某种遍历的前驱和后驱,就将这个节点的left指向前驱,right指向后驱

二、构建线索二叉树过程

20170107161320086.jpg

中序遍历

H , D , I, B ,E, A ,F ,C, G

三、代码实现

  • 节点类
class TreeNode{
    private String data;//数据域
    private TreeNode left;//左指针域
    private TreeNode right;//右指针域

    boolean isLeftThread = false;   //左指针域类型  false:指向子节点、true:前驱或后继线索
    boolean isRightThread = false;  //右指针域类型  false:指向子节点、true:前驱或后继线索

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public boolean isLeftThread() {
        return isLeftThread;
    }

    public void setLeftThread(boolean leftThread) {
        isLeftThread = leftThread;
    }

    public boolean isRightThread() {
        return isRightThread;
    }

    public void setRightThread(boolean rightThread) {
        isRightThread = rightThread;
    }

    public TreeNode getLeft() {
        return left;
    }

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

    public TreeNode getRight() {
        return right;
    }

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

    public TreeNode(String data){
        this.data=data;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "data='" + data + '\'' +
                ", isLeftThread=" + isLeftThread +
                ", isRightThread=" + isRightThread +
                '}';
    }
}
  • 二叉树

/**
 * 线索化二叉树
 * @Author zhangyukang
 * @Date 2020/5/11 12:56
 * @Version 1.0
 **/
public class ThreadBinaryTree {

    private TreeNode root;//二叉树根节点

    private TreeNode pre;//指向前驱

    public TreeNode getRoot() {
        return root;
    }

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

    /**
     * 中序线索化二叉树
     * @param current 当前要线索的节点
     */
    void inThreadOrder(TreeNode current){
        if(current==null){
            return;
        }
        //先线索化左子树
        inThreadOrder(current.getLeft());

        //线索化当前节点
        if(current.getLeft()==null){
            current.setLeft(pre);
            current.setLeftThread(true);
        }
        if(pre!=null&&pre.getRight()==null){
            pre.setRight(current);
            pre.setRightThread(true);
        }

        pre=current;

        //后线索化右子树
        inThreadOrder(current.getRight());
    }

    /**
     * 前序遍历二叉树
     * @param current
     */
    public void preOrder(TreeNode current){
        if(current!=null){
            System.out.print(current.getData()+"\t");
            preOrder(current.getLeft());
            preOrder(current.getRight());
        }
    }

    /**
     * 中序遍历二叉树
     * @param current
     */
    public void infixOrder(TreeNode current){
        if(current!=null){
            infixOrder(current.getLeft());
            System.out.print(current.getData()+"\t");
            infixOrder(current.getRight());
        }
    }
    /**
     * 后序遍历二叉树
     * @param current
     */
    public void postOrder(TreeNode current){
        if(current!=null){
            postOrder(current.getLeft());
            postOrder(current.getRight());
            System.out.print(current.getData()+"\t");
        }
    }


    @Test
    public void test(){
        /**
         *       1
         *     /   |
         *    2     3
         *   / \    / \
         *  4   6  7   5
         */
        ThreadBinaryTree threadBinaryTree = new ThreadBinaryTree();
        threadBinaryTree.setRoot(new TreeNode("1"));
        threadBinaryTree.getRoot().setLeft(new TreeNode("2"));
        threadBinaryTree.getRoot().setRight(new TreeNode("3"));
        threadBinaryTree.getRoot().getLeft().setLeft(new TreeNode("4"));
        threadBinaryTree.getRoot().getLeft().setRight(new TreeNode("6"));
        threadBinaryTree.getRoot().getRight().setRight(new TreeNode("5"));
        threadBinaryTree.getRoot().getRight().setLeft(new TreeNode("7"));



        threadBinaryTree.preOrder(threadBinaryTree.getRoot());
        System.out.println("前序遍历");//1,2,4,6,3,7,5
        threadBinaryTree.infixOrder(threadBinaryTree.getRoot());
        System.out.println("中序遍历");//4,2,6,1,7,3,5
        threadBinaryTree.postOrder(threadBinaryTree.getRoot());
        System.out.println("后序遍历");//4,6,2,7.5,3,1

        //中序线索化二叉树
        threadBinaryTree.inThreadOrder(threadBinaryTree.getRoot());

    }

}

# 二叉树  

评论

公众号:mumuser

企鹅群:932154986

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×