尚硅谷Java数据结构--二叉树 前序、中序、后序查找

以下是Java实现代码

package DataStructure;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86178
 * Date: 2024-03-01
 * Time: 10:42
 */
public class Tree {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode n1 = new HeroNode(2, "吴用");
        HeroNode n2 = new HeroNode(3, "卢俊义");
        HeroNode n3 = new HeroNode(4, "林冲");
        HeroNode newnode = new HeroNode(5, "关胜");
        tree.setRoot(root);
        root.setLeft(n1);
        root.setRight(n2);
        n2.setRight(n3);
        n2.setLeft(newnode);
        System.out.println("前序查找");
        tree.preSearch(5);
        System.out.println("中序查找");
        tree.infixSearch(5);
        System.out.println("后序查找");
        tree.postSearch(5);
        System.out.println("------------------------------------");
        /*System.out.println("前序遍历");// 1 2 3 5 4
        tree.preOrder();
        System.out.println("中序遍历");// 2 1 5 3 4
        tree.infixOrder();
        System.out.println("后序遍历");// 2 5 4 3 1
        tree.postOrder();*/
    }
}

//todo 定义二叉树
class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder() {
        if (root == null) {
            System.out.println("节点为空");
            return;
        }
        if (root != null)
            root.preOrder();
    }

    //前序查找
    public void preSearch(int no) {
        if(root!=null) {
            HeroNode a=root.preSearch(no);
            System.out.println(a);
        }else{
            System.out.println("null");
        }
    }
    //中序查找
    public void infixSearch(int no) {
        if(root!=null){
            HeroNode a=root.infixSearch(no);
            System.out.println(a);
        }else{
            System.out.println("null");
        }
    }
    //后序查找
    public void postSearch(int no) {
        if(root!=null){
            HeroNode a=root.postSearch(no);
            System.out.println(a);

        }else{
            System.out.println("null");
        }
    }
    //中序遍历
    public void infixOrder() {
        if (root == null) {
            System.out.println("节点为空");
            return;
        }
        if (root != null)
            root.infixOrder();
    }

    //后序遍历
    public void postOrder() {
        if (root == null) {
            System.out.println("节点为空");
            return;
        }
        if (root != null)
            root.postOrder();
    }
}

class HeroNode {
    public static int preCnt;
    public static int infixCnt;
    public static int postCnt;
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

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

    public HeroNode getRight() {
        return right;
    }

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

    public int getNo() {
        return no;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return "HeroNode [no=" + no + " name=" + name + "]";
    }

    //前序遍历
    public void preOrder() {
        //可以进来说明当前节点一定不为null
        System.out.println(this);//先输出当前节点

        if (this.left != null) this.left.preOrder();
        if (this.right != null) this.right.preOrder();
    }

    //前序查找
    public HeroNode preSearch(int no) {
        //todo preCnt++ 需要写在判断相等之前 因为left和right有可能为空
        preCnt++;
        if (this.no == no) {
            System.out.println(preCnt);
            return this;
        }
        HeroNode resNode=null;
        if (this.left != null){
            resNode=this.left.preSearch(no);
        }
        if(resNode!=null)   return resNode;
        if (this.right != null){
            resNode=this.right.preSearch(no);
        }
        return resNode;
    }

    //中序遍历
    public void infixOrder() {

        if (this.left != null) this.left.infixOrder();
        System.out.println(this);//中间输出当前节点
        if (this.right != null) this.right.infixOrder();
    }
    //中序查找
    public HeroNode infixSearch(int no) {
        HeroNode resNode=null;
        if (this.left != null){
            resNode=this.left.infixSearch(no);
        }
        if(resNode!=null)   return resNode;
        infixCnt++;
        if (this.no == no) {
            System.out.println(infixCnt);
            return this;
        }
        if (this.right != null){
            resNode=this.right.infixSearch(no);
        }
        return resNode;
    }

    //后序遍历
    public void postOrder() {

        if (this.left != null) this.left.postOrder();
        if (this.right != null) this.right.postOrder();
        System.out.println(this);//最后输出当前节点

    }

    //后序查找
    public HeroNode postSearch(int no) {
        HeroNode resNode=null;
        if (this.left != null){
            resNode=this.left.postSearch(no);
        }
        if(resNode!=null)   return resNode;
        if (this.right != null){
            resNode=this.right.postSearch(no);
        }
        postCnt++;
        if (this.no == no) {
            System.out.println(postCnt);
            return this;
        }
        return resNode;
    }
}