二叉树

1、二叉树类型

• 满二叉树：所有的叶子节点都在最后一层，节点数为2^n-1
• 完全二叉树：满足所有节点存在左右节点

2、二叉树遍历

• 前序遍历：先输出父节点，再遍历左子树和右子树；
• 中序遍历：先遍历左子树，再输出父节点，再遍历右子树；
• 后序遍历：先遍历左子树，再遍历右子树，再输出父节点

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

        BinaryTree binaryTree = new BinaryTree();

        HeroNode root = new HeroNode(1, "刘备");
        HeroNode node2 = new HeroNode(2, "赵云");
        HeroNode node3 = new HeroNode(3, "关羽");
        HeroNode node4 = new HeroNode(4, "张飞");
        HeroNode node5 = new HeroNode(5, "马超");

        root.setLeftNode(node2);
        root.setRightNode(node3);
        node3.setRightNode(node4);
        node3.setLeftNode(node5);

        int no = 4;
        //测试，前序遍历
        System.out.println("前序遍历---------");
        binaryTree.setRoot(root);
        binaryTree.preOrder();
        HeroNode heroNode = binaryTree.preOrder(no);    //前序查找
        System.out.println("查到no:"+no+"信息，"+"name="+heroNode.getName());

        //测试，中序遍历
        System.out.println("中序遍历---------");
        binaryTree.setRoot(root);
        binaryTree.infixOrder();
        HeroNode heroNode1 = binaryTree.infixOrder(no);     //中序查找
        System.out.println("查到no:"+no+"信息，"+"name="+heroNode1.getName());

        //测试，后序遍历
        System.out.println("后序遍历---------");
        binaryTree.setRoot(root);
        binaryTree.backOrder();
        HeroNode heroNode2 = binaryTree.backOrder(no);//后序查找
        System.out.println("查到no:"+no+"信息，"+"name="+heroNode2.getName());
    }
}


// 定义BinaryTree树
class BinaryTree{

    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 HeroNode preOrder(int no){
        HeroNode heroNode = null;
        if (this.root!=null){
            heroNode = this.root.preOrder(no);
        }else {
            System.out.println("没有查到额");
        }
        return heroNode;
    }

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

    //中序查找
    public HeroNode infixOrder(int no){
        HeroNode heroNode =null;
        if (this.root!=null){
          heroNode =  this.root.infixOrder(no);
        }else {
            System.out.println("没有查到额");
        }
        return heroNode;
    }

    public void backOrder(){
        if (this.root!=null){
            this.root.backOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

//    后序查找
    public HeroNode backOrder(int no){
        HeroNode h = null;
        if (this.root!=null){
          h=  this.root.backOrder(no);
        }else {
            System.out.println("没有查到额");
        }
        return h;
    }
}

// 创建HeroNode 节点
class HeroNode{

   private int no;
   private String name;
   private HeroNode leftNode;
   private HeroNode rightNode;

    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 getLeftNode() {
        return leftNode;
    }

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

    public HeroNode getRightNode() {
        return rightNode;
    }

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

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



    // 编写前序遍历的方法
    public void preOrder(){

        System.out.println(this); //输出父节点

        // 递归向左子树前序遍历
        if (this.leftNode!=null){
            this.leftNode.preOrder();
        }
        // 递归向右子树前序遍历
        if (this.rightNode!=null){
            this.rightNode.preOrder();
        }
    }

    // 编写中序遍历的方法
    public void infixOrder(){
        if (this.leftNode!=null){
            this.leftNode.infixOrder();
        }

        System.out.println(this);

        if (this.rightNode!=null){
            this.rightNode.infixOrder();
        }
    }

    // 编写后序遍历的方法
    public void backOrder(){
        if (this.leftNode!=null){
            this.leftNode.backOrder();
        }

        if (this.rightNode!=null){
            this.rightNode.backOrder();
        }
        System.out.println(this);
    }


    // 前序遍历查找
    public HeroNode preOrder(int no){

        System.out.println("前序查询no");
        if (this.no == no){
            return this;
        }
        HeroNode resNode = null;

        if (this.leftNode != null ){
           resNode = this.leftNode.preOrder(no);
        }
        if (resNode !=null){
            return resNode;
        }
        if (this.rightNode!=null){
            resNode =   this.rightNode.preOrder(no);
        }
        if (resNode !=null){
            return resNode;
        }

        return resNode;
    }

    // 中序查找
    public HeroNode infixOrder(int no){

        HeroNode heroNode = null;
        if (this.leftNode!=null){
           heroNode = leftNode.infixOrder(no);
        }
        if (heroNode!=null){
            return heroNode;
        }

        System.out.println("中序查找开始");
        if (this.no == no){
            return this;
        }

        if (this.rightNode!=null){
            heroNode = this.rightNode.infixOrder(no);
        }

        if (heroNode!=null){
            return heroNode;
        }
        return heroNode;
    }

    /*  后序查找
    * */
    public HeroNode backOrder(int no){

        HeroNode heroNode = null;
        if (this.leftNode!=null){
            heroNode = this.leftNode.backOrder(no);
        }
        if (heroNode !=null){
            return heroNode;
        }
        if (this.rightNode!= null){
            heroNode = this.rightNode.backOrder(no);
        }
        if (heroNode !=null){
            return heroNode;
        }

        System.out.println("开始后序查找");
        if (this.no == no){
            return this;
        }
        return heroNode;
    }

}

持续更新中.................