本文共 7202 字，大约阅读时间需要 24 分钟。

前序遍历: 先输出父节点，再遍历左子树和右子树

中序遍历: 先遍历左子树，再输出父节点，再遍历右子树

后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点

看输出父节点的顺序，就确定是前序，中序还是后序

对下面二叉树进行前中后续遍历和查找及节点的删除

package com.whb.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.setRoot(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        // 前序遍历        // 前序遍历的次数 ：4//		System.out.println("前序遍历方式~~~");//		HeroNode resNode = binaryTree.preOrderSearch(5);//		if (resNode != null) {
   //			System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());//		} else {
   //			System.out.printf("没有找到 no = %d 的英雄", 5);//		}        // 中序遍历查找        // 中序遍历3次//		System.out.println("中序遍历方式~~~");//		HeroNode resNode = binaryTree.infixOrderSearch(5);//		if (resNode != null) {
   //			System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());//		} else {
   //			System.out.printf("没有找到 no = %d 的英雄", 5);//		}        // 后序遍历查找        // 后序遍历查找的次数  2次//		System.out.println("后序遍历方式~~~");//		HeroNode resNode = binaryTree.postOrderSearch(5);//		if (resNode != null) {
   //			System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());//		} else {
   //			System.out.printf("没有找到 no = %d 的英雄", 5);//		}        // 测试删除结点        System.out.println("删除前,前序遍历");        binaryTree.preOrder(); //  1,2,3,5,4        binaryTree.delNode(5);        // binaryTree.delNode(3);        System.out.println("删除后，前序遍历");        binaryTree.preOrder(); // 1,2,3,4    }}class BinaryTree{
       private HeroNode root;    public void setRoot(HeroNode 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.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 preOrderSearch(int no) {
           if(root != null) {
               return root.preOrderSearch(no);        } else {
               return null;        }    }    // 中序遍历查找    public HeroNode infixOrderSearch(int no) {
           if(root != null) {
               return root.infixOrderSearch(no);        }else {
               return null;        }    }    // 后序遍历查找    public HeroNode postOrderSearch(int no) {
           if(root != null) {
               return this.root.postOrderSearch(no);        }else {
               return null;        }    }}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;    }    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.right.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);    }    // 前序遍历查找    public HeroNode preOrderSearch(int no){
           System.out.println("进入前序遍历");        if (this.no == no){
               return this;        }        HeroNode resNode = null;        if (this.left != null){
               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;        }        System.out.println("进入中序查找");        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.postOrderSearch(no);        }        if (resNode != null){
               return resNode;        }        if (this.right != null){
               resNode = this.right.postOrderSearch(no);        }        if (resNode != null){
               return resNode;        }        System.out.println("进入后序查找");        if (this.no == no){
               resNode = this;        }        return resNode;    }}

转载地址：http://jmski.baihongyu.com/