树结构_二叉搜索树

二叉搜索树的结构与其操作

结构 BinNode - BinTree - Position

1. 树结点数据Data
2. 左子树Left
3. 右子树Right

查找 - 递归

1. 判空BST
2. 如果元素X大于结点数据，向右递归
3. 如果元素X小于结点数据，向左递归
4. 如果相等，直接返回

查找 - 非递归

1. 循环遍历二叉树BST
2. 如果结点数据大于元素X，BST指向左子树
3. 如果结点数据小于元素X，BST指向右子树
4. 如果相等，跳出并返回BST

找最小值

1. 如果二叉树BST不为空
2. 树BST的左子树不为空则一直向左查找，直到最左树

找最大值

1. 如果二叉树BST不为空
2. 树BST的右子树不为空则一直向右查找，直到最右树

插入结点

1. 如果BST树为空，说明找到插入位置，
2. 为BST申请结点空间，将插入值X赋值给结点，并初始化左、右子树为NULL
3. 如果插入值X小于结点元素，递归向左子树插入
4. 如果插入值X大于结点元素，递归向右子树插入

删除结点

1. 判断树BST是否为空
2. 如果待删元素X小于结点值，递归向左删除元素
3. 如果待删元素X大于结点值，递归向右删除元素
4. 找到了要删除的元素,且该元素有两个孩子
5. 从左子树中找到最大子树填充删除结点，或是从右子树中找到最小子树填充
6. 将找到的最大结点或最小结点的值覆盖到当前待结点
7. 从右子树中删除最小元素结点，或是在左子树中删除最大元素结点
8. 如果只有右孩子或无结点, 当前结点被右子树覆盖
9. 如果只有左孩子，当前结点被左子树覆盖
10. 释放当前结点

#include <stdlib.h>
#include <stdio.h>

typedef int ElementType;
typedef struct BinNode *BinTree;

/**
 * 二叉搜索树结构
 * 查找+找大+找小+插入+删除（递归+循环）5
 */
struct BinNode {
    // 1.树结点数据
    ElementType Data;
    // 2.左子树
    BinTree Left;
    // 3.右子树
    BinTree Right;
};
typedef BinTree Position;

// 查找 - 递归
Position Find(BinTree BST, ElementType X) {
    // 1.判空
    if (!BST) {
        return NULL;
        // 2.如果元素X大于结点数据，向右递归
    } else if (BST->Data > X) {
        Find(BST->Left, X);
        // 3.如果元素X小于结点数据，向左递归
    } else if (BST->Data < X) {
        Find(BST->Right, X);
    }
    // 4.如果相等，直接返回
    return BST;
}

// 查找 - 非递归
Position FindX(BinTree BST, ElementType X) {
    // 1.循环遍历二叉树BST
    while (BST) {
        // 2.如果结点数据大于元素X，BST指向左子树
        if (BST->Data > X) {
            BST = BST->Left;
            //3.如果结点数据小于元素X，BST指向右子树
        } else if (BST->Data < X) {
            BST = BST->Right;
        } else {
            //4.如果相等，跳出并返回BST
            break;
        }
    }
    return BST;
}

// 找最小值
Position FindMin(BinTree BST) {
    // 1.如果二叉树BST不为空
    if (BST) {
        // 2.树BST的左子树不为空则一直向左查找，直到最左树
        while (BST->Left) {
            BST = BST->Left;
        }
    }
    return BST;
}

// 找最大值
Position FindMax(BinTree BST) {
    // 1.如果二叉树BST不为空
    if (BST) {
        // 2.树BST的右子树不为空则一直向右查找，直到最右树
        while (BST->Right) {
            BST = BST->Right;
        }
    }
    return BST;
}

// 插入结点
BinTree Insert(BinTree BST, ElementType X) {
    // 1.如果BST树为空，说明找到插入位置，
    if (!BST) {
        // 2.为BST申请结点空间，将插入值X赋值给结点，并初始化左、右子树为NULL
        BST = (BinTree) malloc(sizeof(struct BinNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    } else {
        // 3.如果插入值X小于结点元素，递归向左子树插入
        if (BST->Data > X) {
            BST->Left = Insert(BST->Left, X);
        } else if (BST->Data < X) {
            // 4.如果插入值X大于结点元素，递归向右子树插入
            BST->Right = Insert(BST->Right, X);
        }
    }
    return BST;
}

// 删除结点
BinTree Delete(BinTree BST, ElementType X) {
    Position Tmp;
    // 1.判断树BST是否为空
    if (!BST) {
        printf("Not Found\n");
    } else {
        // 2.如果待删元素X小于结点值，递归向左删除元素
        if (X < BST->Data) {
            BST->Left = Delete(BST->Left, X);
            // 3.如果待删元素X大于结点值，递归向右删除元素
        } else if (X > BST->Data) {
            BST->Right = Delete(BST->Right, X);
        } else {
            // 4.找到了要删除的元素,且该元素有两个孩子
            if (BST->Left && BST->Right) {
                // 分两步走，先删替换该结点(有2子)的值，再删除右最小或左最大的结点
                // 5.从左子树中找到最大子树填充删除结点，或是从右子树中找到最小子树填充
                Tmp = FindMin(BST->Right);
                // 6.将找到的最大结点或最小结点的值覆盖到当前待结点
                BST->Data = Tmp->Data;
                // 7.从右子树中删除最小元素结点，或是在左子树中删除最大元素结点
                BST->Right = Delete(BST->Right, BST->Data);
            } else {
                Tmp = BST;
                // 8.如果只有右孩子或无结点, 当前结点被右子树覆盖
                if (!BST->Left) {
                    BST = BST->Right;
                } else {
                    // 9.如果只有左孩子，当前结点被左子树覆盖
                    BST = BST->Left;
                }
                // 10.释放当前结点
                free(Tmp);
            }
        }
    }
    return BST;
}