带你了解Java数据结构和算法之二叉树

前言

二叉树是计算机科学中的重要数据结构之一，可以用于实现许多算法和系统。本文将介绍二叉树的基本概念、常见操作、遍历方式等内容，并通过示例详细展示其应用。

二叉树的定义

二叉树是一种树形结构，其每个节点最多有两个子节点，被称为左子节点和右子节点。二叉树具有以下几个特点：

• 每个节点最多有两个子节点
• 左子树和右子树也是二叉树
• 如果二叉树的左子树不为空，则左子树上所有节点的值小于此节点的值
• 如果二叉树的右子树不为空，则右子树上所有节点的值大于此节点的值

二叉树的操作

插入节点

要插入一个节点，在访问其父节点的时候，需要对其值进行比较。如果比父节点值小，就在左子树中插入，否则就在右子树中插入。如下是在 Java 中插入节点的代码示例：

public void insert(int value){
    if(root == null){
        root = new TreeNode(value);
    }else{
        root.insert(value);
    }
}

查找节点

查找节点可以通过递归方式完成，如果查找到的节点的值等于要查找的值，则返回该节点，否则在左子树和右子树中继续查找。如下是在 Java 中查找节点的代码示例：

public TreeNode find(int value){
    if(root == null){
        return null;
    }else{
        return root.find(value);
    }
}

删除节点

删除节点时如果要删除的节点没有子节点，则直接删除；如果有一个子节点，则用其子节点代替删除节点；如果有两个子节点，则找到右子树上最小的节点，将其值赋给要删除的节点，再删除这个最小节点。如下是在 Java 中删除节点的代码示例：

public void delete(int value){
    root = delete(root, value);
}

private TreeNode delete(TreeNode subTree, int value){
    if(subTree == null){
        return null;
    }
    if(value < subTree.val){
        subTree.left = delete(subTree.left, value);
    }else if(value > subTree.val){
        subTree.right = delete(subTree.right, value);
    }else{
        if(subTree.left != null && subTree.right != null){
            subTree.val = findMin(subTree.right).val;
            subTree.right = delete(subTree.right, subTree.val);
        }else{
            subTree = (subTree.left != null) ? subTree.left : subTree.right;
        }
    }
    return subTree;
}

private TreeNode findMin(TreeNode subTree){
    while(subTree.left != null){
        subTree = subTree.left;
    }
    return subTree;
}

二叉树的遍历方式

前序遍历

前序遍历是以根-左-右的顺序进行遍历，即先访问节点，然后遍历左子树，最后遍历右子树。如下是 Java 中实现前序遍历的代码示例：

public void preOrder(TreeNode treeNode){
    if(treeNode != null){
        System.out.println(treeNode.val);
        preOrder(treeNode.left);
        preOrder(treeNode.right);
    }
}

中序遍历

中序遍历是以左-根-右的顺序进行遍历，即先遍历左子树，然后访问节点，最后遍历右子树。如下是 Java 中实现中序遍历的代码示例：

public void inOrder(TreeNode treeNode){
    if(treeNode != null){
        preOrder(treeNode.left);
        System.out.println(treeNode.val);
        preOrder(treeNode.right);
    }
}

后序遍历

后序遍历是以左-右-根的顺序进行遍历，即先遍历左子树，然后遍历右子树，最后访问节点。如下是 Java 中实现后序遍历的代码示例：

public void postOrder(TreeNode treeNode){
    if(treeNode != null){
        preOrder(treeNode.left);
        preOrder(treeNode.right);
        System.out.println(treeNode.val);
    }
}

示例说明

以下是一个使用递归方式创建并添加节点的示例：

public void recursiveInsert(int value, TreeNode treeNode){
    if(root == null){
        root = new TreeNode(value);
    }else{
        if(value < treeNode.val){
            if(treeNode.left != null){
                recursiveInsert(value, treeNode.left);
            }else{
                System.out.println("Inserted " + value + " to left of node " + treeNode.val);
                treeNode.left = new TreeNode(value);
            }
        }else if(value > treeNode.val){
            if(treeNode.right != null){
                recursiveInsert(value, treeNode.right);
            }else{
                System.out.println("Inserted " + value + " to right of node " + treeNode.val);
                treeNode.right = new TreeNode(value);
            }
        }
    }
}

以下是一个使用前序遍历输出节点值的示例：

public void preOrderPrint(TreeNode treeNode){
    if(treeNode != null){
        System.out.print(treeNode.val + " ");
        preOrderPrint(treeNode.left);
        preOrderPrint(treeNode.right);
    }
}

通过以上示例，可以更好地理解如何对二叉树进行操作及遍历。