【Java数据结构】二叉树、线索二叉树

看B站的数据结构视频照着打的，留着自己复习方便看。

二叉树：

package demo5;

public class TreeNode {
    //节点的权
    int value;
    //左右儿子
    TreeNode leftNode;
    TreeNode rightNode;

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

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

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

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

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

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

    //前序查找
    public TreeNode frontSearch(int i){
        TreeNode target=null;
        //对比当前节点值
        if (this.value==i){
            return this;
            //当前节点的值不是要查找的节点
        }else {
            //查找左儿子
            if (leftNode!=null){
                target = leftNode.frontSearch(i);
            }
            //如果不为空，说明在左儿子已经找到
            if (target!=null){
                return target;
            }
            //查找右儿子
            if (rightNode!=null){
                target = rightNode.frontSearch(i);
            }
        }
        return target;
    }

    //删除一个树
    public void delete(int i){
        TreeNode parent =this;
        //判断左儿子
        if (parent.leftNode!=null&&parent.leftNode.value==i){
            parent.leftNode=null;
            return;
        }
        //判断右儿子
        if (parent.rightNode!=null&&parent.rightNode.value==i){
            parent.rightNode=null;
            return;
        }
        //递归检查并删除左儿子
        parent=leftNode;
        if (parent!=null){
            parent.delete(i);
        }
        //递归检查并删除右儿子
        parent=rightNode;
        if (parent!=null){
            parent.delete(i);
        }
    }

}

package demo5;

public class BinaryTree {
    TreeNode root;

    //设置根节点
    public void setRoot(TreeNode root) {
        this.root = root;
    }

    //获取根节点
    public TreeNode getRoot() {
        return root;
    }

    public void frontShow(){
        if (root!=null){
            root.frontShow();
        }

    }

    public void midShow(){
        if (root!=null){
            root.midShow();
        }
    }

    public void afterShow(){
        if (root!=null){
            root.afterShow();
        }
    }

    public TreeNode frontSearch(int i){
        return root.frontSearch(i);
    }

    public void delete(int i){
        if(root.value==i){
            root=null;
        }else {
            root.delete(i);
        }
    }

}

package demo5;

public class TestBinaryTree {
    public static void main(String[] args) {
        //创建一棵树
        BinaryTree binTree = new BinaryTree();
        //创建一个根节点
        TreeNode root = new TreeNode(1);
        //把节点赋给树
        binTree.setRoot(root);
        //创建一个左节点
        TreeNode rootL = new TreeNode(2);
        //把新创建的节点设置为根节点的子节点
        root.setLeftNode(rootL);
        //右节点
        TreeNode rootR = new TreeNode(3);
        root.setRightNode(rootR);


        //为第二层的左节点创建两个子节点
        rootL.setLeftNode(new TreeNode(4));
        rootL.setRightNode(new TreeNode(5));
        //为第二层的右节点创建两个子节点
        rootR.setLeftNode(new TreeNode(6));
        rootR.setRightNode(new TreeNode(7));
        //前序遍历
        binTree.frontShow();
        System.out.println("===========");
        //中序遍历
        binTree.midShow();
        System.out.println("===========");
        //后序遍历
        binTree.afterShow();
        System.out.println("===========");

        //前序查找
        TreeNode result = binTree.frontSearch(3);
        System.out.println(result);
        System.out.println("===========");

        //删除一个子树
        binTree.delete(1);
        binTree.frontShow();
     }
}

链式存储二叉树：

package demo6;

public class ArrayBinaryTree {
    int[] data;

    public ArrayBinaryTree(int[] data){
        this.data=data;
    }

    public void frontShow(){
        frontShow(0);
    }

    //前序遍历
    public void frontShow(int index){
        if (data==null||data.length==0){
            return;
        }
        //先遍历当前节点的内容
        System.out.println(data[index]);
        //2*index+1:处理左子树
        if (2*index+1<data.length){
            frontShow(2*index+1);
        }
        //2*index+2:处理右子树
        if (2*index+2<data.length){
            frontShow(2*index+2);
        }
    }

}

```java
package demo6;

public class TestArrayBinaryTree {
    public static void main(String[] args) {
        int[] data=new int[]{1,2,3,4,5,6,7};
        ArrayBinaryTree tree = new ArrayBinaryTree(data);
        //前序遍历
        tree.frontShow();
    }
}

线索二叉树：

```java
package demo7;

public class ThreadedNode {
    //节点的权
    int value;
    //左右儿子
    ThreadedNode leftNode;
    ThreadedNode rightNode;

    //标识指针类型
    int leftType;
    int rightType;

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

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

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

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

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

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

    //前序查找
    public ThreadedNode frontSearch(int i){
        ThreadedNode target=null;
        //对比当前节点值
        if (this.value==i){
            return this;
            //当前节点的值不是要查找的节点
        }else {
            //查找左儿子
            if (leftNode!=null){
                target = leftNode.frontSearch(i);
            }
            //如果不为空，说明在左儿子已经找到
            if (target!=null){
                return target;
            }
            //查找右儿子
            if (rightNode!=null){
                target = rightNode.frontSearch(i);
            }
        }
        return target;
    }

    //删除一个树
    public void delete(int i){
        ThreadedNode parent =this;
        //判断左儿子
        if (parent.leftNode!=null&&parent.leftNode.value==i){
            parent.leftNode=null;
            return;
        }
        //判断右儿子
        if (parent.rightNode!=null&&parent.rightNode.value==i){
            parent.rightNode=null;
            return;
        }
        //递归检查并删除左儿子
        parent=leftNode;
        if (parent!=null){
            parent.delete(i);
        }
        //递归检查并删除右儿子
        parent=rightNode;
        if (parent!=null){
            parent.delete(i);
        }
    }

}

package demo7;

public class ThreadedBinaryTree {
    ThreadedNode root;
    //临时存储前驱节点
    ThreadedNode pre =null;

    //遍历线索二叉树
    public void threadIterate(){
        //用于临时存储当前遍历节点
        ThreadedNode 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;
        }
    }

    //设置根节点
    public void setRoot(ThreadedNode root) {
        this.root = root;
    }

    //中序线索化二叉树
    public void threadNodes(){
        threadNodes(root);
    }
    public void threadNodes(ThreadedNode node){
        //当前节点如果为null，直接返回
        if (node==null){
            return;
        }
        //处理左子树
        threadNodes(node.leftNode);
        //处理前驱节点
        if (node.leftNode==null){
            //让当前节点的左指针指向前驱节点
            node.leftNode=pre;
            //改变当前节点左指针的类型
            node.leftType=1;
        }
        //处理前驱的右指针，如果前驱节点的右指针是null(没有指向右子树）
        if (pre.rightNode==null){
            //让前驱节点的右指针指向当前节点
            pre.rightNode=node;
            //改变前驱节点的右指针类型
            pre.rightType=1;
        }

        //每处理一个节点，当前节点是下一个节点的前驱节点
        pre=node;
        //处理右子树
        threadNodes(node.rightNode);
    }


    //获取根节点
    public ThreadedNode getRoot() {
        return root;
    }

    public void frontShow(){
        if (root!=null){
            root.frontShow();
        }

    }

    public void midShow(){
        if (root!=null){
            root.midShow();
        }
    }

    public void afterShow(){
        if (root!=null){
            root.afterShow();
        }
    }

    public ThreadedNode frontSearch(int i){
        return root.frontSearch(i);
    }

    public void delete(int i){
        if(root.value==i){
            root=null;
        }else {
            root.delete(i);
        }
    }

}

package demo7;

import demo5.BinaryTree;

public class TestThreadedBinaryTree {
    public static void main(String[] args) {
        //创建一棵树
        BinaryTree binTree = new BinaryTree();
        //创建一个根节点
        ThreadedNode root = new ThreadedNode(1);
        //把节点赋给树
        BinaryTree.setRoot(root);
        //创建一个左节点
        ThreadedNode rootL = new ThreadedNode(2);
        //把新创建的节点设置为根节点的子节点
        root.setLeftNode(rootL);
        //右节点
        ThreadedNode rootR = new ThreadedNode(3);
        root.setRightNode(rootR);


        //为第二层的左节点创建两个子节点
        rootL.setLeftNode(new ThreadedNode(4));
        ThreadedNode fiveNode = new ThreadedNode(5)
        rootL.setRightNode(fiveNode);
        //为第二层的右节点创建两个子节点
//        rootR.setLeftNode(new TreeNode(6));
//        rootR.setRightNode(new TreeNode(7));

        System.out.println("===========");

        //中序遍历数
        binTree.minShow();
        System.out.println("============");
        //中前线索化二叉树
        binTree.threadNodes();
        //获取5节点的后继节点
        ThreadedNode afterFive = fiveNode.rightNode;
        System.out.println(afterFive.value);





//        //中序遍历
//        binTree.midShow();
//        System.out.println("===========");
//        //后序遍历
//        binTree.afterShow();
//        System.out.println("===========");
//
//        //前序查找
//        TreeNode result = binTree.frontSearch(3);
//        System.out.println(result);
//        System.out.println("===========");
//
//        //删除一个子树
//        binTree.delete(1);
//        binTree.frontShow();

        //中前线索化二叉树
        binTree.threadNodes();
        binTree.threadIterate();
     }
}