本文共 3611 字，大约阅读时间需要 12 分钟。

������������������BST������������������������

BST������������

������������������BST���������������������������������������������������������������������������������������������������

typedef struct TreeNode {
    int data;    // ���������
    struct TreeNode* left;  // ���������������
    struct TreeNode* right; // ���������������
} BST, *BinTree;

������������

���������BST������������������������������������������������

• ������������

  void Insert(BinTree& BST, int x)
  ������������������������ BST ������������������������������������������������������������������

• ������������

  void Delete(BinTree& BST, int x)
  ��������������������� BST ���������������������
  Delete������������������������������������������������������������������������

• ���������������

  BinTree FindMin(BinTree BST)
  ������ BST ������������������������������������

• ���������������

  BinTree FindMax(BinTree BST)
  ������ BST ������������������������������������

• ������������

  BinTree FindElem(BinTree BST, int x)
  ������������ BST ������������������������������������������������ NULL���

• ������������

  void MidOrder(BinTree BST)
  ������ BST ���������������������������������������������������������

������������������

void Insert(BinTree& BST, int x) {
    if (BST == NULL) {
        BST = (BinTree)malloc(sizeof(struct TreeNode));
        BST->data = x;
        BST->left = NULL;
        BST->right = NULL;
        return;
    } else if (x > BST->data) {
        Insert(BST->right, x);
    } else if (x < BST->data) {
        Insert(BST->left, x);
    }
}

������������������

���������������������������������������

������������������������

BinTree FindMin(BinTree BST) {
    if (BST == NULL) return NULL;
    while (BST->left != NULL) {
        BST = BST->left;
    }
    return BST;
}
BinTree FindMax(BinTree BST) {
    if (BST == NULL) return NULL;
    while (BST->right != NULL) {
        BST = BST->right;
    }
    return BST;
}

������������������

BinTree FindElem(BinTree BST, int x) {
    if (BST == NULL) return NULL;
    else if (x > BST->data) {
        BST = FindElem(BST->right, x);
    } else if (x < BST->data) {
        BST = FindElem(BST->left, x);
    }
    return BST;
}

������������������

void MidOrder(BinTree BST) {
    if (BST != NULL) {
        MidOrder(BST->left);
        printf("%d", BST->data);
        MidOrder(BST->right);
    }
}

������������������������

������������������������������������������������������������������������

• ������������
• ������������
• ������������
• ������������
• ���������������
• ���������������

������������������

������ Insert ��� Delete ������������������������������������������������������������������������������������������������������������������������ 1 ��� 5 ���������������������������������

3 5 4 2

������������ 5��������������� 1���

������

BST ������������������������������������������������������������������������������������������������������������������������������������������������������������������BST ��������������������������������������������������������������������������������������������������� BST ���������������������������������������