二叉搜索树

1.概念

与二叉树相比，二叉搜索树的每个节点左孩子关键字小于等于该节点关键字，右孩子关键字大于等于该节点关键字。即：

node.left.key ≦ node.key ≦ node.right.key

/**
 * struct treeNode
 * @author liebert
 * @member int key 关键字
 * @member struct treeNode * parent 父节点
 * @member struct treeNode *left 左孩子
 * @member struct treeNode *right 右孩子
 */
typedef struct treeNode {
    int key;
    struct treeNode *parent = NULL;
    struct treeNode *left   = NULL;
    struct treeNode *right  = NULL;
} treeNode, *pTreeNode;

2.查找

（1）查找指定关键字节点

/**
 * searchTreeNode
 * @author liebert
 * @param pTreeNode root 待分割数组
 * @param int key 关键字
 */
pTreeNode *searchTreeNode(pTreeNode root, k)
{
    pTreeNode n = root;
    if (n == NULL || k == n.key){
        return n;
    } else if (k < n.key) {
        searchTree(n->left, k);
    } else {
        searchTree(n->right, k);
    }
}

（2）查找最小关键字节点

/**
 * searchTreeMaxNode
 * @author liebert
 * @param pTreeNode root 树根
 * @return 最小关键字节点
 */
pTreeNode searchTreeMinNode (pTreeNode root)
{
    pTreeNode n = root;

    while(n->left != NULL){
        n = n->left;
    }
    return n;
}

（3）查找最大关键字节点

/**
 * searchTreeMaxNode
 * @author liebert
 * @param pTreeNode root 树根
 * @return 最大关键字节点
 */
pTreeNode searchTreeMaxNode (pTreeNode root)
{
    pTreeNode n = root;

    while(n->right != NULL){
        n = n->right;
    }
    return n;

}

2.插入

从树根开始，根据节点关键字值查找其位置，如果树根节点为空，那么当前节点就直接作为树根节点。

/**
 * insertTreeNode
 * @author liebert
 * @param pTreeNode root 树根
 * @param pTreeNode node 带插入节点
 */
void insertTreeNode (pTreeNode root, pTreeNode node)
{
    pTreeNode temp = root;
    pTreeNode ptemp = NULL;

    if(root == NULL){
        root = node;
        return;
    }

    while (temp != NULL) {
        if (temp->key < node->key) {
            ptemp = temp;
            temp = node->right;
        } else {
            ptemp = temp;
            temp = node->left;
        }
    }

    node->parent = ptemp;
    if (ptemp->key < node->key) {
        ptemp->left = node;
    } else {
        ptemp->right = node;
    }
}

3.删除

（1）如果要删除的节点A没有孩子节点，那么直接删除A节点即可。

image

（2）如果要删除的节点A只有一个孩子B，那么直接将B节点提升到A节点位置即可。

（3）如果要删除的节点A左右两个孩子B、C都在，并且右孩子C的左孩子为空（也就是C节点是以C为根的最小关键字节点），那么将A节点插入到C节点的左孩子位置，然后将C节点提升至A节点位置即可。

（4）如果要删除的节点A左右两个孩子B、C都在，并且右孩子C的左孩子不为空，那么就需要找到以C节点为根的最小关键字节点D，然后以D为树根，将D的父亲节点移至D的右孩子位置，将删除节点A的左孩子B节点移至D的左孩子位置，最后将D移至删除节点A的位置即可。

由于父子节点之间是双向的关系，因此为了维护好这种关系，对于节点的移动操作进行了封装。

移动节点：

void transplant(pTreeNode root, pTreeNode s, pTreeNode d)
{
    if (d.parent == NULL) {
        root = s;
    } else if (d.parent.left == d){
        d.parent.left = s;
    } else {
        d.parent.right = s;
    }
    s.parent = d.parent;
}

删除节点：

/**
 * deleteTreeNode
 * @author liebert
 * @param pTreeNode root 树根
 * @param pTreeNode node 待删除节点
 */
void deleteTreeNode (pTreeNode root, pTreeNode node)
{
    pTreeNode minNode;
    // 如果node子节点为空
    if (node.left == NULL && node.right == NULL) {
        if (node.parent.left == node) {
            node.parent.left = NULL;
        } else {
            node.parent.right = NULL;
        }
    } else if (node.left == NULL) {
        transplant(root, node->right, node);
    } else if (node.right == NULL) {
        transplant(root, node->left, node);
    } else {
        minNode = searchTreeMinNode(node);
        if (minNode.parent != node) {
            transplant(root, minNode, minNode->right);
            minNode.right = node.right;
            minNode.right.parent = minNode;
        }
        minNode.left = node.left;
        minNode.left.parent = minNode;
    }
}