java实现二叉树的创建和遍历

  • Post author:
  • Post category:java


package src.com.zhang.tree;


public class BinaryTreeDemo {
    public static void main(String[] args) {

        BinaryTree binaryTree=new BinaryTree();
        HeroNode11 root = new HeroNode11(1, "11");
        HeroNode11 heroNode111 = new HeroNode11(2, "22");
        HeroNode11 heroNode112 = new HeroNode11(3, "33");
        HeroNode11 heroNode113 = new HeroNode11(4, "44");
        root.setLeft(heroNode111);
        root.setRight(heroNode112);
        heroNode112.setRight(heroNode113);
        binaryTree.setRoot(root);
        binaryTree.delNode(1);
        System.out.println("前序遍历:");
        binaryTree.preOrder();
//        System.out.println("中序遍历");
//        binaryTree.infixOrder();
//        System.out.println("后序遍历");
//        binaryTree.postOrder();

//        System.out.println("前序查找2");
//        HeroNode11 heroNode11 = binaryTree.preOrderSearch(2);
//        System.out.println(heroNode11);
//        System.out.println("中序查找1");
//        HeroNode11 heroNode12 = binaryTree.infixOrderSearch(1);
//        System.out.println(heroNode12);
//        System.out.println("后序查找4");
//        HeroNode11 heroNode14 = binaryTree.infixOrderSearch(4);
//        System.out.println(heroNode14);

    }
}


class BinaryTree{
    private HeroNode11 root;
    public void setRoot(HeroNode11 root){
        this.root=root;
    }
    public void delNode(int no){
        if (root!=null){
            if (root.getNo()==no){
                root=null;
            }else {
            root.delNode(no);
            }
        }
        else {
            System.out.println("空树");
        }
    }

    public void preOrder(){
        if (this.root!=null){
            //这里的this.root是HeroNode11类型的,所以会调用HeroNode11里面的方法
            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 HeroNode11 preOrderSearch(int no){
        if (root!=null){
           return root.preOrderSearch(no);
        }
        else {
            return null;
        }
    }

    public HeroNode11 infixOrderSearch(int no){
        if (root!=null){
            return root.infixOrderSearch(no);
        }
        else {
            return null;
        }
    }

    public HeroNode11 postOrderSearch(int no){
        if (root!=null){
            return root.postOrderSearch(no);
        }
        else {
            return null;
        }
    }
}


class HeroNode11{
    private int no;
    private String name;
    private HeroNode11 left;
    private HeroNode11 right;

    public HeroNode11(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 HeroNode11 getLeft() {
        return left;
    }

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

    public HeroNode11 getRight() {
        return right;
    }

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

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public void delNode(int no){
        if (this.left!=null && this.left.no==no){
            this.left=null;
            return;
        }
        if (this.right!=null && this.left.no==no){
            this.right=null;
            return;
        }

        if (this.left!=null){
            this.left.delNode(no);

        }
        if (this.right!=null){
            this.right.delNode(no);
        }
    }


    //前序遍历
    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);
   }

    /**
     *
     * @param no 查找的编号
     * @return 如果找到就返回HeroNode11,找不到返回null
     */
   //前序查找
    public HeroNode11 preOrderSearch(int no){
        if (this.no==no){
            return this;
        }
        HeroNode11 resNode=null;
        if (this.left!=null){
            resNode=this.left.preOrderSearch(no);
        }
        if (resNode!=null){
            return resNode;
        }
        if (this.right!=null){
            resNode=this.preOrderSearch(no);
        }
        return resNode;
    }

    //中序遍历查找
    public HeroNode11 infixOrderSearch(int no){
        HeroNode11 resNode=null;
        if(this.left!=null){
            resNode=this.left.infixOrderSearch(no);
        }
        if (resNode!=null){
            return resNode;
        }

        if (this.no==no){
            return this;
        }

        if (this.right!=null){
            resNode=this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    //后序遍历查找
    public HeroNode11 postOrderSearch(int no){
        HeroNode11 resNode=null;
        if (this.left!=null){
            resNode=this.left.postOrderSearch(no);
        }
        if (resNode!=null){
            return resNode;
        }

        if (this.right!=null){
            resNode=this.postOrderSearch(no);
        }
        if (resNode!=null){
            resNode=this.postOrderSearch(no);
        }
        return resNode;
    }
}



版权声明:本文为qq_55278081原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。