Java——二叉树的前序、中序、后序遍历及前、中、后序查找

本文主要是介绍Java——二叉树的前序、中序、后序遍历及前、中、后序查找，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

package tree;

/**
 * 二叉树的前序遍历、中序遍历、后序遍历
 */
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.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        binaryTree.setHead(root);

		System.out.println("前序遍历"); // 1,2,3,5,4
		binaryTree.preOrder();

//		System.out.println("中序遍历");
//	    binaryTree.infixOrder(); // 2,1,5,3,4
//
//		System.out.println("后序遍历");
//		binaryTree.postOrder(); // 2,5,4,3,1
        System.out.println("开始删除节点~");
        binaryTree.delNode(5);
        System.out.println("删除后的结果：");
        binaryTree.preOrder();

    }
}


class BinaryTree{
    private HeroNode head;

    public void setHead(HeroNode head) {
        this.head = head;
    }

    public void preOrder(){
        if (head != null){
            head.preOrder();
        }else {
            System.out.println("BinaryTree is empty!");
        }
    }

    public void infixOrder(){
        if (head != null){
            head.infixOrder();
        }else{
            System.out.println("BinaryTree is empty!");
        }
    }

    public void postOrder(){
        if (head != null){
            head.postOrder();
        }else{
            System.out.println("BinaryTree is empty!");
        }
    }

    //前序遍历查找
    public HeroNode preOrderSearch(int no) {
        if(head != null) {
            return head.preOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序遍历查找
    public HeroNode infixOrderSearch(int no) {
        if(head != null) {
            return head.infixOrderSearch(no);
        }else {
            return null;
        }
    }
    //后序遍历查找
    public HeroNode postOrderSearch(int no) {
        if(head != null) {
            return this.head.postOrderSearch(no);
        }else {
            return null;
        }
    }

    //删除节点
    public void delNode(int no) {
        if (head != null) {
            if (head.getNo() != no) {
                head.delNode(no);
            } else {
                head = null;
            }
        } else {
            System.out.println("tree is empty! can't delete!");
        }
    }
}


class HeroNode{
    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 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 + '\'' +
                '}';
    }

    //前序遍历
    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 找到就返回该节点，没有就反悔null
     */
    public HeroNode preOrderSearch(int no){
        if (this.no == no){//表示当前的就是要找的，直接返回
            return this;
        }

        HeroNode resNode = null;

        if (this.left != null){
            //如果向下递归中找到了，则一定会返回一个HeroNode节点
            //然后开始回溯
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null){//此时就表示找到了
            return resNode;
        }

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

        return resNode;
    }

    //中序遍历查找
    public HeroNode infixOrderSearch(int no){

        HeroNode 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 HeroNode postOrderSearch(int no){
        HeroNode resNode = null;
        if (this.left != null){
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null){
            return resNode;
        }
        if (this.right != null){
            resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null){
            return resNode;
        }
        if (this.no == no){
            return this;
        }
        return resNode;
    }

    //删除节点,注意这个时候的删除没有办法删除本节点，只能删除子节点
    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);
        }
    }



}

这篇关于Java——二叉树的前序、中序、后序遍历及前、中、后序查找的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！