（二叉树学习）-----（中序）线索化二叉树------2020.3.7

1、线索化二叉树：

1）线索化二叉树：把二叉树中的空闲空间利用起来，例如4的左子树为空，右子树为空，右子树设为后继节点2，5的左子树设为前驱节点---2，5的右子树设为后继节点----1。

2）线索化二叉树遍历时，不再需要递归，递归所占用的空间大，利用while循环就可以解决。

2、代码分享：

package ThreadTree;

import erchashu.TreeNode;

public class ThreadNode {
    //节点的权
    int value;
    //左儿子
    ThreadNode leftNode;
    //右儿子
    ThreadNode rightNode;
    //标识指针类型
    int leftType;
    int rightType;
    //默认为0，表示一个节点的左子树指的就是它的左子树，一个节点的右子树指的就是它的右子树

    public ThreadNode(int value) {
        this.value = value;
    }

    public void setLeftNode(ThreadNode leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(ThreadNode rightNode) {
        this.rightNode = rightNode;
    }

    //前序遍历
    public void frontShow() {
        //当前节点的内容
        System.out.println(value);
        //左节点
        if (leftNode != null) {
            leftNode.frontShow();
        }
        //右节点
        if (rightNode != null) {
            rightNode.frontShow();
        }
    }
}

package ThreadTree;

public class ThreadBinaryTree {
    //根节点
    ThreadNode root;
    //设置根节点
    public void setRoot(ThreadNode root){
        this.root=root;
    }
    //获取根节点
    public ThreadNode getRoot(){
        return this.root;
    }

    ThreadNode pre=null;
    //临时存储前驱节点，写不写都是null


    //中序线索化二叉树
    public void threadNode(){
        threadNode(root);
    }
    public void threadNode(ThreadNode node){
        //如果当前节点node为空，直接返回
        if(node==null){
            return;
        }
        //处理左子树
        threadNode(node.leftNode);
        //处理自己
        if(node.leftNode==null){
            //让当前节点的左指针指向前驱节点
            node.leftNode=pre;
            //改变当前节点左指针的类型
            node.leftType=1;
        }
        if(pre!=null && pre.rightNode==null){
            //让前驱节点的右指针指向当前节点
            pre.rightNode=node;
            //改变前驱节点的右指针类型
            pre.rightType=1;
        }
        //每处理一个节点，当前节点是下一个节点的前驱节点
        pre=node;


        //处理右子树
        threadNode(node.rightNode);
    }

    //遍历线索二叉树
    public void threadIterate(){
        //用于临时存储当前遍历节点
        ThreadNode node=root;
        while(node!=null){
            //循环找到最开始的节点
            while(node.leftType==0){
                node=node.leftNode;
            }
            //打印当前节点的值
            System.out.println(node.value);
            //如果当前节点的右指针指向的是后继节点，可能后继节点还有后继节点
            while(node.rightType==1){
                node=node.rightNode;
                System.out.println(node.value);
            }
            //替换遍历的节点
            node=node.rightNode;


        }
    }



    //前序遍历
    //binaryTree是外面的框框，真正要干事也不干，实际上干事的是root节点里面的方法。
    public void frontShow(){
        if(root!=null){
            root.frontShow();
        }

    }
}

package ThreadTree;

import erchashu.TreeNode;
import erchashu.binaryTree;

public class ThreadTreeDemo1 {
    public static void main(String[] args){
        //创建一棵树
        ThreadBinaryTree btree=new ThreadBinaryTree();
        //创建一个根节点
        ThreadNode root=new ThreadNode(1);
        //把根节点放到树里面
        btree.setRoot(root);
        //创建根节点的左儿子和右儿子
        ThreadNode rootLeftNode=new ThreadNode(2);
        ThreadNode rootRightNode=new ThreadNode(3);
        //设置根节点的左儿子和右儿子
        root.setLeftNode(rootLeftNode);
        root.setRightNode(rootRightNode);
        //为第二层的左节点创建两个子节点
        rootLeftNode.setLeftNode(new ThreadNode(4));
        rootLeftNode.setRightNode(new ThreadNode(5));
        //为第二层的右节点创建两个子节点
        rootRightNode.setLeftNode(new ThreadNode(6));
        rootRightNode.setRightNode(new ThreadNode(7));
        //前序遍历
        System.out.println("前序遍历：");
        btree.frontShow();//
        //中序线索化二叉树
        System.out.println("中序线索化二叉树遍历：");
        btree.threadNode();
        btree.threadIterate();
    }
}

分享一个写线索二叉树：好的博客：

https://blog.****.net/UncleMing5371/article/details/54176252

（二叉树学习）-----（中序）线索化二叉树------2020.3.7

相关推荐