C++資料結構之搜尋二元樹的實現

2022-05-24 14:02:05

零.前言

瞭解搜尋二元樹是為了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的值++。最終統計出各個元素出現的次數。