Java数据结构06——树

1.why:

数组&链表&树

?

?

2. 大纲

?

2.1前中后序

public class HeroNode {
    private int no;
    private String name;
    private  HeroNode left;//默认为null
    private HeroNode right;//默认为null

    public HeroNode(int no, String name) {
        this.no = no;
        this.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 HeroNode getLeft() {
        return left;
    }

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

    public HeroNode getRight() {
        return right;
    }

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

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
    //遍历
    //编写前序遍历方法,被谁调用this就是谁
    public void preOrder(){
        System.out.println(this);//先输出父节点
        //递归先左子树前遍历
        if(this.left!=null){
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if (this.right!=null){
            this.right.preOrder();
        }
    };

    //编写中序遍历方法
    public void infixOrder(){
        //递归先左子树前遍历
        if(this.left!=null){
            this.left.infixOrder();
        }
        //再输出父节点
        System.out.println(this);
        //递归向右子树前序遍历
        if (this.right!=null){
            this.right.infixOrder();
        }
    };

    //编写后序遍历方法
    public void postOrder(){
        //递归先左子树前遍历
        if(this.left!=null){
            this.left.postOrder();
        }
        //递归向右子树前序遍历
        if (this.right!=null){
            this.right.postOrder();
        }
        //最后输出父节点
        System.out.println(this);
    };

  

}

2.2查找节点

 //查找
    //前序查找
    public HeroNode preSearch(int HeroNo){
        //判断当前节点是不是
        if (this.getNo()==HeroNo){
            return this;
        };
        //左子树前序查找
        //如果左递归前序查找节点，找到结点，则返回
        HeroNode resNode = null;//辅助节点

        if (this.getLeft()!=null) {
            resNode =this.getLeft().preSearch(HeroNo);
        }
        //resNode不为空才返回，因为右子树仍未查找
        if (resNode!=null){
            return resNode;
        }
        if (this.getRight()!=null){
            resNode = this.getRight().preSearch(HeroNo);
        }
        return resNode;
    }

    //中序查找
    public HeroNode infixSearch(int HeroNo){

        //左子树前序查找
        //如果左递归前序查找节点，找到结点，则返回
        HeroNode resNode = null;//辅助节点

        if (this.getLeft()!=null) {
            resNode =this.getLeft().preSearch(HeroNo);
        }
        //resNode不为空才返回，因为右子树仍未查找
        if (resNode!=null){
            return resNode;
        };
        //判断当前节点是不是
        if (this.getNo()==HeroNo){
            return this;
        }
        //查找右子树
        if (this.getRight()!=null){
            resNode = this.getRight().preSearch(HeroNo);
        }
        return resNode;
    }

    //后序查找
    public HeroNode postSearch(int HeroNo){
        //左子树前序查找
        //如果左递归前序查找节点，找到结点，则返回
        HeroNode resNode = null;//辅助节点
        if (this.getLeft()!=null) {
            resNode =this.getLeft().preSearch(HeroNo);
        }
        //resNode不为空才返回，因为右子树仍未查找
        if (resNode!=null){
            return resNode;
        };
        if (this.getRight()!=null){
            resNode = this.getRight().preSearch(HeroNo);
        }
        if (resNode!=null){
            return resNode;
        };
        //最后判断当前节点是不是
        if (this.getNo()==HeroNo){
            return this;
        };
        return resNode;
    }

2.3删除节点（基本）?

//删除
    public void deleteNode(int HeroNo){
        //判断左子节点
        if (this.left!=null && this.left.getNo()==HeroNo){
            this.left=null;
            return;
        }
        //判断右子节点
        if (this.right!=null&&this.right.getNo()==HeroNo){
            this.right=null;
            return;
        }
        //遍历左子树
        if (this.left!=null){
            this.left.deleteNode(HeroNo);
        }
        if(this.right!=null){
            this.right.deleteNode(HeroNo);
        }
    }

2.4二叉树 （root节点）

public class BinaryTree {
    //root
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    };
    //遍历二叉树
    //前序遍历
    public void preOrder(){
        if (this.root!=null){
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

    //中序遍历
    public void infixOrder(){
        if (this.root!=null){
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

    //后续遍历
    public void postOrder(){
        if (this.root!=null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

    //查找二叉树指定节点
    //前序查找
    public HeroNode preSearch(int HeroNo){
        if (this.root!=null){
            return this.root.preSearch(HeroNo);
        }else {
            return null;
        }
    }
    //中序查找
    public HeroNode infixSearch(int HeroNo){
        if (this.root!=null){
            return this.root.infixSearch(HeroNo);
        }else {
            return null;
        }
    }
    //后序查找
    public HeroNode postSearch(int HeroNo){
        if (this.root!=null){
            return this.root.postSearch(HeroNo);
        }else {
            return null;
        }
    }
    public void delNode(int HeroNo){
        if(root!=null){
            if (root.getNo()==HeroNo){
                root=null;
            }else {
                root.deleteNode(HeroNo);
            }
        }else {
            System.out.println("空树，无法删除");
        }
    }
}

2.5顺序存储二叉树??（为完全二叉树，公式）

public class ArrBinaryTree {

    private int [] arr;//存储结点的数组

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }
    //重载
    public void preOrder(){
        preOrder(0);
    }
    public void infixOrder(){
        infixOrder(0);
    }
    /**
     *
     * @param index  arr[index]=i
     */
    //前序
    public void preOrder(int index){
        if(arr == null ||arr.length==0){
            System.out.println("数组为空");
        }
        System.out.println(arr[index]);
        //向左递归遍历
        if ((index*2+1)<arr.length){
            preOrder(2*index+1);

        }
        //向右递归遍历
        if ((index*2+2)<arr.length){
            preOrder(2* index+2);
        }
    }
    //中序
    public void infixOrder(int index){
        if(arr == null ||arr.length==0){
            System.out.println("数组为空");
        }
        //向左递归遍历
        if ((index*2+1)<arr.length){
            infixOrder(index*2+1);
        }
        System.out.println(arr[index]);
        //向右递归遍历
        if ((index*2+2)<arr.length){
            infixOrder(2* index+2);
        }
    }
}

?2.6线索化二叉树（节点左右节点类型、前驱指针）

?

?

public class ThreadBinaryTree {
    private HeroNode root;

    //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
    // 在递归进行线索化时，pre总是保留前一个结点
    //pre指针
    private HeroNode pre =null;

    public HeroNode getRoot() {
        return root;
    }

    public HeroNode getPre() {
        return pre;
    }

    public void setPre(HeroNode pre) {
        this.pre = pre;
    }

    public void setRoot(HeroNode root) {
        this.root = root;
    };
    //重载threadNodes()
    public void threadedNodes(){
        this.threadedNodes(root);
    }



    /*多回顾*/
//    //中序线索化二叉树
    public void threadedNodes(HeroNode node){
        //递归找到最左节点，然后返回
        if (node == null) {
            return;
        }
        //先线索化左子树
        threadedNodes(node.getLeft());

        //线索化当前节点
        if (node.getLeft()==null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        //key！！！
        if (pre!=null&&pre.getRight()==null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre=node;

        //线索化右子树
        threadedNodes(node.getRight());

    };

    //***提高：中序、后序***
    //遍历线索化二叉树
    public void threadedList(){
        HeroNode node = root;
        while (root!=null){
            while(node!=null){
                //循环的找到leftType ==1的结点，第一个找到就是8结点
                // 后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化
                // 处理后的有效结点
                while (node.getLeftType()==0){
                    node=node.getLeft();
                }
                System.out.println(node);
                while (node.getRightType()==1){
                    node=node.getRight();
                    System.out.println(node);
                }
                //替换这个遍历点（对于原本就有右结点的）!!!
                node=node.getRight();
            }
        }
    }

    //遍历二叉树
    //前序遍历
    public void preOrder(){
        if (this.root!=null){
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

    //中序遍历
    public void infixOrder(){
        if (this.root!=null){
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

    //后续遍历
    public void postOrder(){
        if (this.root!=null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

    //查找二叉树指定节点
    //前序查找
    public HeroNode preSearch(int HeroNo){
        if (this.root!=null){
            return this.root.preSearch(HeroNo);
        }else {
            return null;
        }
    }
    //中序查找
    public HeroNode infixSearch(int HeroNo){
        if (this.root!=null){
            return this.root.infixSearch(HeroNo);
        }else {
            return null;
        }
    }
    //后序查找
    public HeroNode postSearch(int HeroNo){
        if (this.root!=null){
            return this.root.postSearch(HeroNo);
        }else {
            return null;
        }
    }
    public void delNode(int HeroNo){
        if(root!=null){
            if (root.getNo()==HeroNo){
                root=null;
            }else {
                root.deleteNode(HeroNo);
            }
        }else {
            System.out.println("空树，无法删除");
        }
    }
}

?