● 二叉搜索樹滿足以下條件的二叉樹：
1、每個節(jié)點(diǎn)都有一個作為搜索依據(jù)的關(guān)鍵碼（key），所有節(jié)點(diǎn)的關(guān)鍵碼互不相同。
2、左子樹上所有節(jié)點(diǎn)的關(guān)鍵碼（key）都小于根節(jié)點(diǎn)的關(guān)鍵碼（key）。
3、右子樹上所有節(jié)點(diǎn)的關(guān)鍵碼（key）都大于根節(jié)點(diǎn)的關(guān)鍵碼（key）。
4、左右子樹都是二叉搜索樹。

創(chuàng)新互聯(lián)網(wǎng)站建設(shè)提供從項(xiàng)目策劃、軟件開發(fā)，軟件安全維護(hù)、網(wǎng)站優(yōu)化(SEO)、網(wǎng)站分析、效果評估等整套的建站服務(wù)，主營業(yè)務(wù)為成都網(wǎng)站制作、成都做網(wǎng)站，app軟件定制開發(fā)以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。創(chuàng)新互聯(lián)深信只要達(dá)到每一位用戶的要求，就會得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！

● 二叉搜索樹的插入過程如下：

1、若當(dāng)前的二叉搜索樹為空，則插入的元素為根節(jié)點(diǎn)。

2、若插入的元素值小于根節(jié)點(diǎn)值，則將元素插入到左子樹中。

3、若插入的元素值大于根節(jié)點(diǎn)值，則將元素插入到右子樹中。

4、找到插入的位置和插入的位置的父結(jié)點(diǎn)，進(jìn)行鏈接。

template<class T>
void BSTree<T>::Insert(const T& key, const T& value)//非遞歸算法進(jìn)行插入
{
 if (_root == NULL)
 {
  _root = new Node(key, value);
  return;
 }
 Node* prev = NULL;
 Node* cur = _root;
 while (cur)//在樹中找到插入的位置
 {
  if (key < cur->_key)
  {
   prev = cur;
   cur = cur->_left;
  }
  else if (key > cur->_key)
  {
   prev = cur;
   cur = cur->_right;
  }
 }
 cur = new Node(key, value);//建立新結(jié)點(diǎn)，并判斷具體位置進(jìn)行鏈接
 if (prev->_key > cur->_key)
 {
  prev->_left = cur;
 }
 if (prev->_key < cur->_key)
 {
  prev->_right = cur;
 }
}

template<class T>
void BSTree<T>::Insert_R(const T& key, const T& value)//遞歸算法進(jìn)行插入
{
 _insert_r(_root, key, value);
}
template<class T>
void BSTree<T>::_insert_r(Node*& root, const T& key, const T& value)//遞歸
{
 if (root == NULL)//root為空時，開辟新結(jié)點(diǎn)
 {
  root = new Node(key, value);
  return;
 }
 Node* cur = root;
 if (key < cur->_key)
  _insert_r(cur->_left, key, value);
 if (key > cur->_key)
  _insert_r(cur->_right, key, value);
}

● 二叉搜索樹的查找過程如下：

1、若當(dāng)前的二叉搜索樹為空，則結(jié)束函數(shù)。

2、若查找的元素值小于根節(jié)點(diǎn)值，則在當(dāng)前結(jié)點(diǎn)的左子樹中查找。

3、若查找的元素值大于根節(jié)點(diǎn)值，則在當(dāng)前結(jié)點(diǎn)的右子樹中查找。

template<class T>
BSTNode<T>* BSTree<T>::Find(const T& key)//非遞歸算法進(jìn)行查找
{
 Node* cur = _root;
 while (cur)
 {
  if (key < cur->_key)
  {
   cur = cur->_left;
  }
  else if (key > cur->_key)
  {
   cur = cur->_right;
  }
  else
  {
   return cur;
  }
 }
 return NULL;
}

template<class T>
BSTNode<T>* BSTree<T>::Find_R(const T& key)//遞歸
{
 return _find_r(_root, key);
}
template<class T>
BSTNode<T>* BSTree<T>::_find_r(Node*& root, const T& key)//遞歸算法進(jìn)行查找
{
 if (root == NULL)//root為空時為沒找到
 {
  return NULL;
 }
 if (key < root->_key)
  return _find_r(root->_left, key);
 else if (key > root->_key)
  return _find_r(root->_right, key);
 else
  return root;
}

● 二叉搜索樹的刪除，分兩種情況進(jìn)行處理：

1、找到要刪除的結(jié)點(diǎn)cur和cur的父親結(jié)點(diǎn)prev。

2、情況一：cur只有一個子樹或沒有子樹。首先考慮刪除的結(jié)點(diǎn)為根結(jié)點(diǎn)時，直接_root指向它的子樹；

再考慮cur的左為空、右為空還是左右都為空，進(jìn)行刪除，鏈接。

3、情況二：cur左右子樹都不為空。首先找到cur右子樹的最左下結(jié)點(diǎn)del，然后進(jìn)行交換，通過替換法刪除del，并使prev的指向置空。

template<class T>
void BSTree<T>::Remove(const T& key)//非遞歸算法進(jìn)行刪除
{
 if (_root == NULL)
 {
  return;
 }
 Node* prev = NULL;
 Node* cur = _root;
 while (cur)//找到要刪除的結(jié)點(diǎn)cur
 {
  if (key < cur->_key)
  {
   prev = cur;
   cur = cur->_left;
  }
  else if (key > cur->_key)
  {
   prev = cur;
   cur = cur->_right;
  }
  else
   break;
 }
 //情況一：cur只有一個孩子或沒有孩子，注意考慮cur為根結(jié)點(diǎn)時,prev=NULL
 if (cur->_left == NULL || cur->_right == NULL)
 {
  if (cur->_left == NULL)//cur只有右孩子
  {
   if (prev == NULL)//cur為根結(jié)點(diǎn)時
    _root = cur->_right;
   else if (prev->_left == cur)
    prev->_left = cur->_right;
   else
    prev->_right = cur->_right;
  }
  else if (cur->_right == NULL)//cur只有左孩子
  {
   if (prev == NULL)//cur為根結(jié)點(diǎn)時
    _root = cur->_left;
   else if (prev->_left == cur)
    prev->_left = cur->_left;
   else
    prev->_right = cur->_left;
  }
  //刪除cur并置空，包含了cur的左右為空的情況
  delete cur;
  cur = NULL;
 }
 //情況二：cur有左右子樹,替換法刪除
 else
 {
  //先找到cur結(jié)點(diǎn)右子樹的最左下結(jié)點(diǎn)del
  Node* del = cur;
  prev = del;
  del = del->_right;
  while (del->_left)
  {
   prev = del;
   del = del->_left;
  }
  //替換法，刪除結(jié)點(diǎn)del,注意使prev的指向置空
  swap(cur->_key, del->_key);
  swap(cur->_value, del->_value);
  if (prev->_left == del)
   prev->_left = NULL;
  else if (prev->_right == del)
   prev->_right = NULL;
  delete del;
  del = NULL;
 }
}

template<class T>
void BSTree<T>::Remove_R(const T& key)//遞歸算法進(jìn)行刪除
{
 _remove_r(_root, key);
}
template<class T>
void BSTree<T>::_remove_r(Node*& root, const T& key)//遞歸
{
 if (_root == NULL)
 {
  return;
 }
 if (key < root->_key)
  _remove_r(root->_left, key);
 else if (key > root->_key)
  _remove_r(root->_right, key);
 else
 {
  //情況一：只有一個子樹或沒有,直接使root重新賦值
  if (root->_left == NULL || root->_right == NULL)
  {
   Node* del = root;
   if (root->_left == NULL)
    root = root->_right;
   else if (root->_right == NULL)
    root = root->_left;
   else
    root = NULL;
   delete del;
   del = NULL;
  }
  else//情況二：左右子樹都不為空
  {
   Node* cur = root->_right;//root右子樹最左下結(jié)點(diǎn)，交換兩個結(jié)點(diǎn)的值
   while (cur->_left)
   {
    cur = cur->_left;
   }
   swap(root->_key, cur->_key);
   swap(root->_value, cur->_value);
   _remove_r(root->_right, key);//在root的右子樹上刪除key，轉(zhuǎn)換成情況一中左子樹一定為空
  }
 }
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

新聞標(biāo)題：【數(shù)據(jù)結(jié)構(gòu)】二叉搜索樹-創(chuàng)新互聯(lián)
網(wǎng)站URL：http://www.chinadenli.net/article48/gsgep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、網(wǎng)站設(shè)計、移動網(wǎng)站建設(shè)、App開發(fā)、外貿(mào)建站、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)