C++数据结构之搜索二叉树的实现

目录

• 零.前言
• 1.概念
• 2.作用
• 3.迭代实现
• (1)查找
• (2)插入
• (3)删除
• 4.递归实现
• (1)查找
• (2)插入
• (3)删除
• 5.key/value模型的应用
• (1)对应查找
• (2)判断出现次数
• 6.总结

零.前言

了解搜索二叉树是为了STL中的map和set做铺垫，我们所熟知的AVL树和平衡搜索二叉树也需要搜索二叉树的基础，本文就来建立一棵搜索二叉树。

1.概念

搜索二叉树又称为二叉排序树，它或者是一棵空树，或者具有如下性质：

1.若其左子树不为空，则左子树上所有节点的值都小于根节点的值。

2.若其右子树不为空，则右子树上所有节点的值都大于根节点的值。

3.它的左右子树也分别为二叉搜索树。

2.作用

1.搜索：通过搜索二叉树的性质来进行搜索。

2.排序：二叉搜索树的中序遍历就是将所有数据进行排序。

3.迭代实现

(1)查找

对二叉搜索树的节点进行查找：

1.定义查找节点指针cur

2.比较cur->_k与要查找的节点k的值的大小关系，当_k<k的时候，cur指向该节点的右子树，否则指向左子树。

3.查找成功返回true，失败返回false

bool Find(const K& k)
    {
        Node* cur = _root;//1.
        while (cur)//2.
        {
            if (cur->_k < k)
            {
                cur = cur->_right;
            }
            else if (cur->_k > k)
            {
                cur = cur->_left;
            }
            else
            {
                return true;//3
            }
        }
        return false;//3
    }

(2)插入

1.判断根节点指针是否为空。如果为空则直接将该节点插入根节点位置。

2.定义遍历节点cur与其父节点parent。

3.依次判断插入节点的k与当前节点cur的大小决定cur指向当前节点的左或者右节点。并在改变cur指向之前将parent赋值为cur。

如果二叉搜索树中已经有该值，则返回false。

4.当cur为空的时候，建立根据k在cur处建立节点。比较parent的_k与k的大小，判断cur建立在parent的左子树还是右子树。并返回true。

    bool InsertNode(const K& k)
    {
        if (_root == nullptr)
        {
            _root = new Node(k);
            return true;
        }//1
        Node* cur = _root;
        Node* parent = nullptr;//2
        while (cur)
        {
            if (cur->_k < k)
            {
                    parent = cur;
                    cur = cur->_right;
            }
            else if (cur->_k > k)
            {
                    parent = cur;
                    cur = cur->_left;
            }
            else
            {
                    return false;
            }
        }//3
            cur = new Node(k);
            if (parent->_k < k)
            {
                parent->_right = cur;
            }
            else
            {
                parent->_left = cur;
            }
            return true;//4
    }

(3)删除

1.首先通过cur和parent查找该节点。

2.如果cur左为空，判断cur相对于parent的位置，并将cur的右子树赋值到cur相对于parent的位置处。并删除cur。

3.如果cur右为空，判断cur相对于parent的位置，并将cur的左子树赋值到cur相对于parent的位置处。并删除cur。

4.如果cur的左右都不为空：

(1)建立一个新的节点指针min赋值为cur->right作为遍历指针，和其父节点指针minparent赋值为cur。

(2)一直向左遍历直到min->left为空。并交换min与cur的_key。

(3)判断min与minparent的位置关系，并将min的右子树放在该处。

(4)删除min，返回true。若没找到返回false。

    bool Erase(const K& k)
    {
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur)
        {
            if (cur->_k < k)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_k > k)
            {
                parent = cur;
                cur = cur->_left;
            }//1
            else
            {
                if (cur->_left == nullptr)
                {
                    if (parent == nullptr)
                    {
                        _root = cur->_right;
                    }
                    else if (parent->_right == cur)
                    {
                        parent->_right = cur->_right;
                    }
                    else
                    {
                        parent->_left = cur->_right;
                    }
                    delete cur;
                    return true;
                }
                else if (cur->_right == nullptr)
                {
                    if (parent == nullptr)
                    {
                        _root = cur->_left;
                    }
                    else if (parent->_left == cur)
                    {
                        parent->_left = cur->_left;
                    }
                    else
                    {
                        parent->_right = cur->_left;
                    }
                    delete cur;
                    return true;
                }//2
                else
                {
                    Node* min = cur->_right;
                    Node* minparent = cur;//4.(1)
                    while(min->_left)
                    {
                        minparent = min;
                        min = min->_left;
                    }//4.(2)
                    cur->_k = min->_k;
                    if (minparent->_left == min)
                    {
                        minparent->_left = min->_right;
                    }
                    else
                    {
                        minparent->_right = min->_right;
                    }//4.(3)
                    delete min;
                    return true;
                }
            }
        }
        return false;//4.(4)
    }

4.递归实现

(1)查找

1.判空

2.判断root->_k与k的大小，判断递归的方向。

3.如果找到了返回root节点。

    Node* _FindR(const K& k)
    {
        return FindR(_root, k);
    }//1
    Node* FindR(Node* root, const K& k)
    {
        if (root == nullptr)
        {
            return nullptr;
        }
        if (root->_k > k)
        {
            return FindR(root->_left, k);
        }
        else if (root->_k < k)
        {
            return FindR(root->_right, k);
        }//2
        else
        {
            return root;
        }//3
    }

(2)插入

1.判断节点是否为空，如果为空将该节点插入节点的位置。并返回true

2.判断_k和k的大小，判断递归的方向。

3.如果节点值等于k返回false。

    bool InsertR(const K& k)
    {
        return _InsertR(_root, k);
    }
    bool _InsertR(Node*& root, const K& k)
    {
        if (root == nullptr)
        {
            root = new Node(k);
            return true;
        }//1
        if (root->_k < k)
        {
            return _InsertR(root->_right, k);
        }
        else if (root->_k > k)
        {
            return _InsertR(root->_left, k);
        }//2
        else
        {
            return false;
        }//3
    }

(3)删除

1.如果节点为空则返回false

2.通过_k和k的大小来判断递归方向。

3.找到该节点：

(1)定义del指针赋值为root。

(2)如果root左子树为空，则将root指向该节点的右子树。

(3)如果root右子树为空，则将root指向该节点的左子树。

(4)如果root左右子树都不为空，将min赋值为root->right，并依次向左找，直到min->left为空。并交换min的k与root的k。 然后递归到右子树来进行删除。

(5)删除原root节点(del)，并返回true。

bool EraseR(const K& k)
{
	return _EraseR(_root, k);
}
bool _EraseR(Node*& root, const K& k)
{
	if (root == nullptr)
		return false;//1

	if (root->_k < k)
	{
		return _EraseR(root->_right, k);
	}
	else if (root->_k > k)
	{
		return _EraseR(root->_left, k);
	}//2
	else
	{
		Node* del = root;//3.(1)
		if (root->_left == nullptr)
		{
			root = root->_right;
		}//3.(2)
		else if (root->_right == nullptr)
		{
			root = root->_left;
		}//3.(3)
		else
		{
			Node* min = root->_right;
			while (min->_left)
			{
				min = min->_left;
			}

			swap(min->_k, root->_k);

			// 递归到右子树去删除
			return _EraseR(root->_right, k);//3.(4)
		}

		delete del;
		return true;//3.(5)
	}
}

5.key/value模型的应用

key/value模型，即在原来k的基础上，每个节点再带有一个value值。有两种主要的应用：

(1)对应查找

利用到了二叉搜索树搜素的性质。

    BSTree<string, string> word;
    word.InsertNode("man", "男人");
    word.InsertNode("woman", "女人");
    word.InsertNode("sort", "排序");
    word.InsertNode("Earth", "地球");
    word.InsertNode("birth", "出生");
    word.InsertNode("die", "死亡");
    string str;
    while (cin >> str)
    {
        BSTreeNode<string, string>* ret = word.Find(str);
        if (ret)
        {
            cout << "对应的中文解释：" << ret->_v << endl;
        }
        else
        {
            cout << "无此单词" << endl;
        }
    }

我们向二叉搜索树中存入英文单词和中文释义，将英文单词作为k来构建二叉搜索树，如果搜索到了则打印中文释义，这样就简单构成了一个字典。

(2)判断出现次数

当我们判断一个数组中各个元素出现的次数的时候，也可以使用到二叉搜索树。

    string arr[] = { "a","b","e","e","b","a","n","a","n","a","c","p","d","d","x","s","w","l" };
    BSTree<string, int> counttree;
    for (auto& str : arr)
    {
        auto ret = counttree.Find(str);
        if (ret != nullptr)
        {
            (ret->_v)++;
        }
        else
        {
            counttree.InsertNode(str, 1);
        }
    }
    counttree._InOrderv();

每一次出现一个元素我们就将它插入二叉搜索树中，并把它的value赋值为1，当第二次遇到这个元素的时候，在二叉搜索树中搜索该元素，人如果可以找到该元素则将该元素的value的值++。最终统计出各个元素出现的次数。

6.总结

对于二叉搜索树的理解对以后学习AVL树和红黑树具有很大的帮助

到此这篇关于C++数据结构之搜索二叉树的实现的文章就介绍到这了,更多相关C++搜索二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！