【二叉树：1】二叉树的遍历、查找以及删除操作（Java编写）

一、基本介绍

1.二叉树

• 每个节点最多拥有两个子节点的树称为二叉树；
• 二叉树的子节点分为：左节点、右节点
• 特殊的二叉树有满二叉树、完全二叉树；
• 满二叉树：二叉树中所有叶节点都在最后一层，且节点总数为2ⁿ-1，n表示二叉树的高度；
• 完全二叉树：二叉树的叶节点分布在最后一层或者倒数第二层，且最后一层叶节点在左面连续，倒数第二层叶节点在右面连续（连续的含义可以理解为节点之间没有空余位置）；

下图为一个普通的二叉树（后面代码编写均基于该二叉树）：

二、二叉树遍历

这里介绍二叉树的先序遍历、中序遍历以及后序遍历算法，这三种遍历方式的主要区别在于：父节点的输出顺序，父节点的输出顺序决定了使用那种遍历算法。

1.先序遍历

• 先输出当前节点；
• 判断其左节点是否为空，若不为空则递归进行前序遍历；
• 判断其右节点是否为空，若不为空则递归进行前序遍历；

    // 前序遍历
    public void preOrder(){
        System.out.println(this);  // 输出当前节点
        if (this.left!=null) {  //打印左子树
            this.left.preOrder();
        }
        if (this.right!=null) {  //打印右子树
            this.right.preOrder();
        }
    }

2.中序遍历

• 判断当前节点的左节点是否为空，若不为空则递归进行中序遍历；
• 输出当前节点；
• 判断当前节点的右节点是否为空，若不为空则递归进行中序遍历；

    // 中序遍历
    public void middleOrder(){
        if (this.left!=null){
            this.left.middleOrder();
        }
        System.out.println(this);
        if (this.right!=null){
            this.right.middleOrder();
        }
    }

3.后序遍历

• 判断当前节点的左节点是否为空，若不为空则递归进行后序遍历；
• 判断当前节点的右节点是否为空，若不为空则递归进行后序遍历；
• 输出当前节点；

    // 后序遍历
    public void postOrder(){
        if (this.left!=null){
            this.left.postOrder();
        }
        if (this.right!=null){
            this.right.postOrder();
        }
        System.out.println(this);

    }

三、二叉树遍历查找

查找方式依据使用的遍历方式的不同可分为：先序遍历查找、中序遍历查找和后序遍历查找。
此处代码编写我的需求是查依据雇员的姓名进行查找，也就是依据节点的name属性查找。

1.先序遍历查找

• 与当前节点进行比较，若找到则直接返回当前节点，否则判断其左节点是否为空，若不为空则使用其左节点进行递归前序遍历查找；
• 若在左节点递归查找过程中找到该节点则直接返回，否则判断当前节点的右节点是否为空，若不为空则进入当前节点的右节点进行递归前序遍历查找；

    // 前序查找
    public EmployeeNode preOrderSearch(String name){
        System.out.println("进入前序遍历");
        if (this.getName().equals(name)){  // 比较当前节点
            return this;
        }
        EmployeeNode tempNode=null;
        if(this.getLeft()!=null){  // 左子树递归查找
            tempNode= this.getLeft().preOrderSearch(name);
        }
        if (tempNode!=null){  // 判断左子树是否找到
            return tempNode;
        }
        if(this.getRight()!=null){  // 右子树递归查找
            tempNode= this.getRight().preOrderSearch(name);
        }
        return tempNode;
    }

2.中序遍历查找

• 首先判断当前节点的左节点是否为空，若不为空则进行左节点递归查找，若在此过程中找到该节点则直接将其返回，否则就与当前节点进行比较；
• 如果比较发现当前节点为查询的节点则直接返回，否则判断其右节点是否为空，若不为空则进行右节点递归查找；

    // 中序查找
    public EmployeeNode middleOrderSearch(String name){
        EmployeeNode tempNode=null;
        if (this.getLeft()!=null){  //左子树递归查找
            tempNode=this.getLeft().middleOrderSearch(name);
        }
        if (tempNode!=null){  // 说明左子树已经找到
            return tempNode;
        }
        System.out.println("进入中序遍历");
        if (this.getName().equals(name)){  //比较当前节点
            return this;
        }
        if (this.getRight()!=null){  //右子树递归查找
            tempNode=this.getRight().middleOrderSearch(name);
        }
        return tempNode;
    }

3.后序遍历查找

• 首先判断当前节点的左节点是否为空，若不为空则进行左节点递归查找，若找到该节点则直接返回，否则判断当前节点的右节点是否为空；
• 若右节点不为空，则进行右节点递归查找，若找到直接返回，否则与当前节点进行比较；

    // 后序查找
    public EmployeeNode postOrderSearch(String name){
        EmployeeNode tempNode=null;
        if (this.getLeft()!=null){  //左子树递归查找
            tempNode=this.getLeft().postOrderSearch(name);
        }
        if (tempNode!=null){  // 说明左子树已经找到
            return tempNode;
        }
        if (this.getRight()!=null){  //右子树递归查找
            tempNode=this.getRight().postOrderSearch(name);
        }
        if (tempNode!=null){  // 说明右子树已经找到
            return tempNode;
        }
        System.out.println("进入后序遍历");
        if (this.getName().equals(name)){  //比较当前节点
            return this;
        }
        return tempNode;
    }

四、二叉树删除（删除节点/子树）

普通二叉树是没有顺序规则可言的，只要当前节点最多只有两个子节点的树就称为二叉树，所以在删除时对于子树调整的规则也没有很严格，这里先简单认识一下如何删除满足删除条件的叶节点或者删除此节点为根节点的子树。此处使用的二叉树是单向二叉树，通过子节点是无法回溯到父节点的，所以我们在进行删除操作时只能判断某节点的子节点是否是需要删除的节点。

• 最开始先判断二叉树是否为空，若不为空，则判断根节点是否满足删除条件，若满足则直接将根节点置空，否则判断子节点；
• 判断当前节点的左节点是否满足删除条件，若满足直接将左节点置空，否则判断右节点；
• 判断当前节点的右节点是否满足删除条件，若满足直接将右节点置空，否则进行子节点递归删除；
• 进行当前节点的左节点递归删除；
• 进行当前节点的右节点递归删除；

    // 删除操作
    public void delete(String name){
        if(this.left!=null && this.left.getName().equals(name)){  // 判断当前节点的左节点是否满足删除条件
                this.left=null;
                return;
        }
        if(this.right!=null && this.right.getName().equals(name)){  // 判断当前节点的右节点是否满足删除条件
            this.right=null;
            return;
        }
        if (this.left!=null ){  // 进行左节点递归删除
            this.left.delete(name);
        }
        if(this.right!=null){  // 进行右节点递归删除
            this.left.delete(name);
        }

    }

完整代码：

package com.north.tree;

// 二叉树相关内容
public class BinaryTreeDemo {
    public static void main(String[] args){
        System.out.println("Hello BinaryTree.");
        BinaryTree tree=new BinaryTree();

        EmployeeNode root = new EmployeeNode(1, "杨俊荣");
        EmployeeNode node2 = new EmployeeNode(2, "周杰伦");
        EmployeeNode node3 = new EmployeeNode(3, "方文山");
        EmployeeNode node4 = new EmployeeNode(4, "浪花兄弟");
        EmployeeNode node5 = new EmployeeNode(5, "南拳妈妈");

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        tree.setRoot(root);

        String name="杨俊荣";
        // 删除
        System.out.println("删除前，前序遍历：");
        tree.preOrder();
        tree.delete(name);
        System.out.println("删除后，前序遍历：");
        tree.preOrder();

        // 遍历
//        tree.preOrder();
//        System.out.println("---------------------------------------------");
//        tree.middleOrder();
//        System.out.println("---------------------------------------------");
//        tree.postOrder();
//        System.out.println("---------------------------------------------");

        // 查找
//        EmployeeNode searchResult=tree.preOrderSearch(name);
//        System.out.println(tree.preOrderSearch(name));
//        System.out.println(tree.preOrderSearch("周杰伦"));
//        System.out.println(tree.preOrderSearch("方文山"));
//        System.out.println(tree.preOrderSearch("杨俊荣"));
//        System.out.println(tree.preOrderSearch("浪花兄弟"));
//        System.out.println(tree.middleOrderSearch(name));
//        System.out.println(tree.postOrderSearch(name));
    }
}


// 构建二叉树
class BinaryTree{
    private EmployeeNode root;

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

    // 前序遍历
    public void preOrder(){
        if (this.root!=null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空，无法遍历！");
        }
    }

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

    // 后序遍历
    public void postOrder(){
        if (this.root!=null){
            this.root.postOrder();
        }else{
            System.out.println("二叉树为空，无法遍历！");
        }
    }

    // 前序查找
    public EmployeeNode preOrderSearch(String name){
        if (this.root!=null){
            return this.root.preOrderSearch(name);
        }else {
            return null;
        }
    }

    // 中序查找
    public EmployeeNode middleOrderSearch(String name){
        if (this.root!=null){
            return this.root.middleOrderSearch(name);
        }else {
            return null;
        }
    }

    // 后序查找
    public EmployeeNode postOrderSearch(String name){
        if (this.root!=null){
            return this.root.postOrderSearch(name);
        }else {
            return null;
        }
    }

    // 删除
    public void delete(String name){
        if(this.root!=null){
            if(this.root.getName().equals(name)) {
                this.root = null;
            }else {
                this.root.delete(name);
            }
        } else{
            System.out.println("二叉树为空，无法删除！");
        }
    }
}


// 构建树节点
class EmployeeNode{
    private int number;
    private String name;
    private EmployeeNode left;
    private EmployeeNode right;

    // 构造器

    public EmployeeNode(int number, String name) {
        this.number = number;
        this.name = name;
    }

    // get、set方法
    public int getNumber() {
        return number;
    }

    public void setNumber(int number) {
        this.number = number;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public EmployeeNode getLeft() {
        return left;
    }

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

    public EmployeeNode getRight() {
        return right;
    }

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

    // 重写toString 方法

    @Override
    public String toString() {
        return "EmployeeNode{" +
                "number=" + number +
                ", 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 middleOrder(){
        if (this.left!=null){
            this.left.middleOrder();
        }
        System.out.println(this);
        if (this.right!=null){
            this.right.middleOrder();
        }
    }

    // 后序遍历
    public void postOrder(){
        if (this.left!=null){
            this.left.postOrder();
        }
        if (this.right!=null){
            this.right.postOrder();
        }
        System.out.println(this);

    }

    // 前序查找
    public EmployeeNode preOrderSearch(String name){
        System.out.println("进入前序遍历");
        if (this.getName().equals(name)){  // 比较当前节点
            return this;
        }
        EmployeeNode tempNode=null;
        if(this.getLeft()!=null){  // 左子树递归查找
            tempNode= this.getLeft().preOrderSearch(name);
        }
        if (tempNode!=null){  // 判断左子树是否找到
            return tempNode;
        }
        if(this.getRight()!=null){  // 右子树递归查找
            tempNode= this.getRight().preOrderSearch(name);
        }
        return tempNode;
    }

    // 中序查找
    public EmployeeNode middleOrderSearch(String name){
        EmployeeNode tempNode=null;
        if (this.getLeft()!=null){  //左子树递归查找
            tempNode=this.getLeft().middleOrderSearch(name);
        }
        if (tempNode!=null){  // 说明左子树已经找到
            return tempNode;
        }
        System.out.println("进入中序遍历");
        if (this.getName().equals(name)){  //比较当前节点
            return this;
        }
        if (this.getRight()!=null){  //右子树递归查找
            tempNode=this.getRight().middleOrderSearch(name);
        }
        return tempNode;
    }

    // 后序查找
    public EmployeeNode postOrderSearch(String name){
        EmployeeNode tempNode=null;
        if (this.getLeft()!=null){  //左子树递归查找
            tempNode=this.getLeft().postOrderSearch(name);
        }
        if (tempNode!=null){  // 说明左子树已经找到
            return tempNode;
        }
        if (this.getRight()!=null){  //右子树递归查找
            tempNode=this.getRight().postOrderSearch(name);
        }
        if (tempNode!=null){  // 说明右子树已经找到
            return tempNode;
        }
        System.out.println("进入后序遍历");
        if (this.getName().equals(name)){  //比较当前节点
            return this;
        }
        return tempNode;
    }

    // 删除操作
    public void delete(String name){
        if(this.left!=null && this.left.getName().equals(name)){
                this.left=null;
                return;
        }
        if(this.right!=null && this.right.getName().equals(name)){
            this.right=null;
            return;
        }
        if (this.left!=null ){
            this.left.delete(name);
        }
        if(this.right!=null){
            this.left.delete(name);
        }

    }
}