首页 > 资讯 > 后端开发 > 其他教程 >C++数据结构之搜索二叉树的实现

865

分享到

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

2024-04-02 19:04:59 865人浏览泡泡鱼

摘要

目录零.前言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的值++。最终统计出各个元素出现的次数。