查找指定节点(二分查找)

  public static Position Find(ElementType X, TreeNode BST) {
        while (BST) {
            if (X < BST -> data) {
                BST = BST -> left;
            } else if (X > BST -> data) {
                BST = BST -> right;
            } else return BST;
        }
        return NULL;
    }

• 找最大元素和最小元素同理，查找效率取决于树的高度

插入指定节点

public static TreeNode Insert(ElementType X, TreeNode BST) {
        if (!BST) {
            BST = new TreeNode();
            BST -> data = X;
            BST -> left = NULL;
            BST -> right = NULL;
        } else {
            if (X > BST -> data) {
                BST -> right = Insert(X, BST -> right);
            }
            if (X < BST -> data) {
                BST -> left = Insert(X, BST -> left);
            }
        }
        return BST;
    }

• 插入节点插在叶子那一层

删除指定节点

• 情况一：删除节点为叶节点，直接删除
• 情况二：删除节点有一个孩子节点，然他的父节点直接连接他的孩子节点
• 情况三：删除节点有左右孩子节点，取左子树最大或右子树最小代替（因为他们一定没有两个儿子节点），所以找到它之后就可以按情况二的方式删除

public static TreeNode Delete(ElementType X, TreeNode BST) {
        TreeNode tmp;
        if (!BST) {
            System.out.println("没有匹配的节点");
        } else if (X < BST -> data) {
            BST -> left = Delete(X, BST -> left);
        } else if (X > BST -> data) {
            BST -> right = Delete(X, BST -> right);
        } else {
            if (BST -> right && BST -> left) {
                tmp = FindMin(BST -> right);
                BST -> data = tmp -> data;
                BST -> right = Delete(X, BST -> right);
            } else {
                tmp = BST;
                if (!BST -> left) {
                    BST = BST -> right;
                } else if (!BST -> right) {
                    BST = BST -> left;
                }
                free(tmp);
            }
        }
    }