二叉排序树

1.编写SearchBST(T,key)，InsertBST(T,key)伪代码与实现

• SearchBST(T,key)伪代码：

  bool SearchBST(BSTNode* T, KeyType key)
  {
      if (T 空)
      {
          cout << "no" << endl;
          return false;
      }
  
      if (T->key == key)
      {
          cout << "yes" << endl;
          return true;
      }
      if (key < T->key)
          return 左子树递归;
      else
          return 右子树递归;
  }
  

• InsertBST(T,key)伪代码：

  InsertBST(T, key) {
  	if (T空)
  	{
  		T = new BSTNode;
  		T->key = key;             //key赋给根结点
  		左右子树设为空；
  	}
  	else if (key == T->key)
  		return;
  	else if (k < T->key)         
  		return 左子树递归;
  	else                          
  		return 右子树递归;
  }
  

• 实现:

  • 代码：

    bool SearchBST(BSTNode* T, KeyType key)
    {
        if (T == NULL)
        {
            cout << "no" << endl;
            return false;
        }
    
        if (T->key == key)
        {
            cout << "yes" << endl;
            return true;
        }
        if (key < T->key)
            return SearchBST(T->lchild, key);
        else
            return SearchBST(T->rchild, key);
    }
    int InsertBST(BSTNode*& T, KeyType key)
    {
        if (T == NULL)
        {
            T = new BSTNode;
            T->key = key;
            T->lchild = T->rchild = NULL;
            return 1;
        }
        else if (key == T->key)
            return 0;
        else if (key < T->key)
            return InsertBST(T->lchild, key);
        else
            return InsertBST(T->rchild, key);
    }
    

2.编写CreateBST(T)的伪代码与实现

• 伪代码：

  CreateBST(T)
  {
      BSTNode* T = NULL;
      int i = 0;
      while (i < n)
      {
          InsertBST(T, A[i])插入;
          i++;
      }
      return T;
  }
  

• 实现：

  • 代码：

  #include<iostream>
  using namespace std;
  typedef int KeyType;
  typedef struct BSTNode
  {
      KeyType key;                     //关键字项
      int data;                       //其它数据域
      struct BSTNode* lchild, * rchild;   //左右孩子指针
  }BSTNode;
  BSTNode* CreateBST(KeyType A[], int n);
  int InsertBST(BSTNode*& T, KeyType key);
  void inOrder(BSTNode* T);
  int main()
  {
      BSTNode* T;
      int n, i, key = 0;
      int a[50];
      memset(a, '0', sizeof(a));
      cout << "请输入结点个数:" << endl;
      cin >> n;
      cout << "请输入二叉排序树结点:" << endl;
      for (i = 0;i < n;i++)
      {
          cin >> a[i];
      }
  
      cout << "中序遍历的结果:" << endl;
      T = CreateBST(a, n);
      inOrder(T);
  
      return 0;
  }
  int InsertBST(BSTNode*& T, KeyType key)
  {
      if (T == NULL)
      {
          T = new BSTNode;
          T->key = key;
          T->lchild = T->rchild = NULL;
          return 1;
      }
      else if (key == T->key)
          return 0;
      else if (key < T->key)
          return InsertBST(T->lchild, key);
      else
          return InsertBST(T->rchild, key);
  }
  BSTNode* CreateBST(KeyType A[], int n)
  {
      BSTNode* T = NULL;
      int i = 0;
      while (i < n)
      {
          InsertBST(T, A[i]);
          i++;
      }
      return T;
  }
  void inOrder(BSTNode* T)
  {
      if (T != NULL)
      {
          inOrder(T->lchild);
          cout << T->key << " ";
          inOrder(T->rchild);
      }
      else
          return;
  }
  
  

  • 运行结果：
    

3.编写DeleteBST(T,key)伪代码

伪代码：

int DeleteBST(BSTNode*& T, KeyType key)
{
    if (T 空)
        return 0;
    else//寻找关键字为key的结点
    {
        if (key < T->key)
            return T的左子树递归;
        else if (key > T->key)
            return T的右子树递归;
        else 找到key
        {
            BSTNode* q;
            if (T->rchild == NULL)   //右孩子为空，左孩子补上
            {
                q = T;
                T = T->lchild;
                delete q;
            }
            else if (T->lchild == NULL)  //左孩子为空，右孩子补上
            {
                q = T;
                T = T->rchild;
                delete q;
            }
            else  左右子树皆有的情况
                Deletel(T, T->lchild);  
            return true;
        }
    }
}
void Deletel(BSTNode* p, BSTNode* r)//r指向左子树
{
    BSTNode* q;
    if (r->rchild != NULL)
        Deletel(p, r->rchild); //递归找最右下结点
    else 最右下结点找到
    {
       
        p->key = r->key; //结点代替
        q = r;
        r = r->lchild;
        delete q;
    }
}

4.代码实现DeleteBST(T,key)

int DeleteBST(BSTNode*& T, KeyType key)
{
    if (T == NULL)
        return 0;
    else
    {
        if (key < T->key)
            return DeleteBST(T->lchild, key);
        else if (key > T->key)
            return DeleteBST(T->rchild, key);
        else
        {
            BSTNode* q;
            if (T->rchild == NULL)   
            {
                q = T;
                T = T->lchild;
                delete q;
            }
            else if (T->lchild == NULL)  
            {
                q = T;
                T = T->rchild;
                delete q;
            }
            else
                Deletel(T, T->lchild);   
            return true;
        }
    }
}
void Deletel(BSTNode* p, BSTNode* r)
{
    BSTNode* q;
    if (r->rchild != NULL)
        Deletel(p, r->rchild);  
    else
    {      
        p->key = r->key; 
        q = r;
        r = r->lchild;
        delete q;
    }
}

运行结果：

删除函数想法

• 删除结点对象有四种情况：
  1. 叶子结点；
  2. 被删结点右子树为空；
  3. 被删结点左子树为空；
  4. 左右子树皆不为空；
• 对应四种情况的解决方法：
  1. 归在2，3里；
  2. 用被删除结点的左子树q代替删除结点,释放q的空间；
  3. 用被删除结点的右子树q代替删除结点,释放q的空间；
  4. 寻找根结点的左子树的最右下结点r，将r值赋予被删除结点，设置q=r,r的左孩子代替r，释放q即原来的r的空间。