java实现二叉树的基本操作
    一、二叉树的定义
    树是计算机科学中的一种基本数据结构，表示以分层方式存储的数据集合。树是由节点和边组成的，每个节点都有一个父节点和零个或多个子节点。每个节点可以对应于一定数据，因此树也可以被视作提供快速查的一种方式。若树中每个节点最多只能有两个子节点，则被称为二叉树（Binary Tree）。二叉树是一种递归定义的数据结构，它或者为空集，或者由一个根节点以及左右子树组成。如果左子树非空，则左子树上所有节点的数值均小于或等于根节点的数值；如果右子树非空，则右子树上所有节点的数值均大于或等于根节点的数值；左右子树本身也分别是二叉树。
    在计算机中实现二叉树，通常使用指针来表示节点之间的关系。在Java中，定义一个二叉树节点类的代码如下：
    ```
    public class BinaryTree {
        int key;
        BinaryTree left;
        BinaryTree right;
        public BinaryTree(int key) {
            this.key = key;
        }
    }
    ```
    在这个类中，key字段表示该节点的数值；left和right字段分别表示这个节点的左右子节点。
    1. 插入节点
    若要在二叉树中插入一个节点，首先需要遍历二叉树，到一个位置使得插入新节点后，依然满足二叉树的定义。插入节点的代码可以写成下面这个形式：
    ```
    public void insert(int key) {
        BinaryTree node = new BinaryTree(key);
        if (root == null) {
            root = node;
            return;
        }
二叉树定义        BinaryTree temp = root;
        while (true) {
            if (key < temp.key) {
                if (temp.left == null) {
                    temp.left = node;
                    break;
                }
                temp = temp.left;
            } else {
                if (temp.right == null) {
                    temp.right = node;
                    break;
                }
                temp = temp.right;
            }
        }
    }
    ```
    上面的代码首先创建了一个新的二叉树节点，然后判断二叉树根是否为空，若为空，则将这个节点作为根节点。否则，从根节点开始，逐层比较使用键值key和当前节点的键值的大小，直到到一个空子节点为止，将新节点插入在那里。
    2. 删除节点
    删除一个节点时，需要按照二叉树的特定规则调整，因此需实现特定的算法。有三种情况需要考虑：
    1）删除的节点没有子节点。这种情况很简单，只需将该节点的父节点的左或右指针设置为空即可。
    2）删除的节点有一个子节点。还是比较容易处理，只需将删除节点的子节点连接到删除节点的父节点即可。
    3）删除的节点有两个子节点。这种情况相对比较复杂。需要到该节点右子树中的最小值节点（即右子树中的最左节点），然后将该节点的值赋给被删除节点，并删除这个最小值节点。
    删除节点的代码可以使用下面这种形式：
    ```
    public void deleteNode(int key) {
        if (root == null)
            return;
        BinaryTree current = root;
        BinaryTree parent = null;
        boolean isLeftChild = false;
        while (current != null && current.key != key) {
            parent = current;
            if (key < current.key) {
                current = current.left;
                isLeftChild = true;
            } else {
                current = current.right;
                isLeftChild = false;
            }
        }
        if (current == null)
            return;
        // 情况1：删除的是叶子节点
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        // 情况2：删除的节点只有一个子节点
        else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        }
        // 情况3：删除的节点有两个子节点
        else {
            BinaryTree successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。