【数据结构】二叉搜索树

● 二叉搜索树满足以下条件的二叉树：
1、每个节点都有一个作为搜索依据的关键码（key），所有节点的关键码互不相同。
2、左子树上所有节点的关键码（key）都小于根节点的关键码（key）。
3、右子树上所有节点的关键码（key）都大于根节点的关键码（key）。
4、左右子树都是二叉搜索树。

● 二叉搜索树的插入过程如下：

1、若当前的二叉搜索树为空，则插入的元素为根节点。

2、若插入的元素值小于根节点值，则将元素插入到左子树中。

3、若插入的元素值大于根节点值，则将元素插入到右子树中。

4、找到插入的位置和插入的位置的父结点，进行链接。

template<class?T>
void?BSTree<T>::Insert(const?T&?key,?const?T&?value)//非递归算法进行插入
{
?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);//建立新结点，并判断具体位置进行链接
?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)//递归算法进行插入
{
?_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为空时，开辟新结点
?{
??root?=?new?Node(key,?value);
??return;
?}
?Node*?cur?=?root;
?if?(key?<?cur->_key)
??_insert_r(cur->_left,?value);
?if?(key?>?cur->_key)
??_insert_r(cur->_right,?value);
}

● 二叉搜索树的查找过程如下：

1、若当前的二叉搜索树为空，则结束函数。

2、若查找的元素值小于根节点值，则在当前结点的左子树中查找。

3、若查找的元素值大于根节点值，则在当前结点的右子树中查找。

template<class?T>
BSTNode<T>*?BSTree<T>::Find(const?T&?key)//非递归算法进行查找
{
?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)//递归算法进行查找
{
?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;
}

● 二叉搜索树的删除，分两种情况进行处理：

1、找到要删除的结点cur和cur的父亲结点prev。

2、情况一：cur只有一个子树或没有子树。首先考虑删除的结点为根结点时，直接_root指向它的子树；

再考虑cur的左为空、右为空还是左右都为空，进行删除，链接。

3、情况二：cur左右子树都不为空。首先找到cur右子树的最左下结点del，然后进行交换，通过替换法删除del，并使prev的指向置空。

template<class?T>
void?BSTree<T>::Remove(const?T&?key)//非递归算法进行删除
{
?if?(_root?==?NULL)
?{
??return;
?}
?Node*?prev?=?NULL;
?Node*?cur?=?_root;
?while?(cur)//找到要删除的结点cur
?{
??if?(key?<?cur->_key)
??{
???prev?=?cur;
???cur?=?cur->_left;
??}
??else?if?(key?>?cur->_key)
??{
???prev?=?cur;
???cur?=?cur->_right;
??}
??else
???break;
?}
?//情况一：cur只有一个孩子或没有孩子，注意考虑cur为根结点时,prev=NULL
?if?(cur->_left?==?NULL?||?cur->_right?==?NULL)
?{
??if?(cur->_left?==?NULL)//cur只有右孩子
??{
???if?(prev?==?NULL)//cur为根结点时
????_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为根结点时
????_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结点右子树的最左下结点del
??Node*?del?=?cur;
??prev?=?del;
??del?=?del->_right;
??while?(del->_left)
??{
???prev?=?del;
???del?=?del->_left;
??}
??//替换法，删除结点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)//递归算法进行删除
{
?_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右子树最左下结点，交换两个结点的值
???while?(cur->_left)
???{
????cur?=?cur->_left;
???}
???swap(root->_key,?cur->_key);
???swap(root->_value,?cur->_value);
???_remove_r(root->_right,?key);//在root的右子树上删除key，转换成情况一中左子树一定为空
??}
?}
}

（编辑：ASP站长网）