C++中如何实现搜索二叉树

本篇内容介绍了"C++中如何实现搜索二叉树"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

• 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

• 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

• 任意节点的左、右子树也分别为二叉查找树；

• 没有键值相等的节点。

#pragma oncetemplatestruct BSTreeNode{        K _key;        V _value;        BSTreeNode* _left;        BSTreeNode* _right;        BSTreeNode(const K& key, const V& value)                :_key(key)                ,_value(value)                ,_left(NULL)                ,_right(NULL)        {}};templateclass BSTree{        typedef BSTreeNode Node;public:        BSTree()                :_root(NULL)        {}        bool Insert(const K& key, const V& value)        {                if (NULL == _root)//若为空树                {                        _root = new Node(key, value);                        return true;                }                Node* parent = NULL;                Node* cur = _root;                //确定插入节点的位置                while (cur)                {                        if (key < cur->_key)                        {                                parent = cur;                                cur = cur->_left;                        }                        else if (key > cur->_key)                        {                                parent = cur;                                cur = cur->_right;                        }                        else//已经存在key                        {                                return false;                        }                }                //插入节点                if (key > parent->_key)                        parent->_right = new Node(key, value);                else                        parent->_left = new Node(key, value);        }        //Insert递归写法        bool InsertR(const K& key, const V& value)        {                return _InsertR(_root, key, value);        }        bool _InsertR(Node*& root, const K& key, const V& value)        {                if (NULL == root)                {                        root = new Node(key, value);                        return true;                }                if (key > root->_key)                        return _InsertR(root->_right, key, value);                else if (key < root->_key)                        return _InsertR(root->_left, key, value);                else                        return false;        }        Node* Find(const K& key)        {                Node* cur = _root;                while (cur)                {                        if (key > cur->_key)                                cur = cur->_right;                        else if (key < cur->_key)                                cur = cur->_left;                        else                                return cur;                }                return NULL;        }        //Find递归写法        Node* FindR(const K& key)        {                return _FindR(_root, key);        }        Node* _FindR(Node* root, const K& key)        {                if (NULL == root)                        return NULL;                if (key > root->_key)                        return _FindR(root->_right, key);                else if (key < root->_key)                        return _FindR(root->_left, key);                else                        return root;        }        bool Remove(const K& key)        {                Node* parent = NULL;                Node* cur = _root;                //确定删除节点的位置                while (cur)                {                        if (key > cur->_key)                        {                                parent = cur;                                cur = cur->_right;                        }                        else if (key < cur->_key)                        {                                parent = cur;                                cur = cur->_left;                        }                        else                        {                                break;                        }                }                if (NULL == cur)//没有该节点                {                        return false;                }                Node* del;                if (NULL == cur->_left)//删除节点的左孩子为空                {                        del = cur;                        //删除的节点为根节点                        if (NULL == parent)                        {                                _root = _root->_right;                        }                        else                        {                                if (cur == parent->_left)                                        parent->_left = cur->_right;                                else                                        parent->_right = cur->_right;                        }                }                else if (NULL == cur->_right)//删除节点的右孩子为空                {                        del = cur;                        if (NULL == parent)                        {                                _root = _root->_left;                        }                        else                        {                                if (cur == parent->_left)                                        parent->_left = cur->_right;                                else                                        parent->_right = cur->_left;                        }                }                else//删除节点的左右孩子都不为空，找右子树最左节点代替该节点删除                {                        parent = cur;                        Node* leftmost = cur->_right;                        while (leftmost->_left)                        {                                parent = leftmost;                                leftmost = leftmost->_left;                        }                        del = leftmost;                        cur->_key = leftmost->_key;                        cur->_value = leftmost->_value;                        if (leftmost == parent->_left)                                parent->_left = leftmost->_right;                        else                                parent->_right = leftmost->_right;                }                return true;        }        //Remove递归写法        bool RemoveR(const K& key)        {                return _RemoveR(_root, key);        }                bool _RemoveR(Node*& root, const K& key)        {                if (NULL == root)                        return false;                                if (key > root->_key)                {                        return _RemoveR(root->_right, key);                }                else if (key < root->_key)                {                        return _RemoveR(root->_left, key);                }                else                {                        Node* del = root;                        if (NULL == root->_left)                        {                                root = root->_right;                        }                        else if (NULL == root->_right)                        {                                root = root->_left;                        }                        else                        {                                Node* leftmost = root->_right;                                while (leftmost->_left)                                {                                        leftmost = leftmost->_left;                                }                                swap(root->_key, leftmost->_key);                                swap(root->_value, leftmost->_value);                                return _RemoveR(root->_right, key);                        }                        delete del;                }                return true;        }        //中序遍历递归写法        void InOrder()        {                _InOrder(_root);        }        void _InOrder(Node* root)        {                if (NULL == root)                        return;                _InOrder(root->_left);                cout<_key<<" ";                _InOrder(root->_right);        }protected:        Node* _root;};void Test(){        BSTree t;        int a[] = {5, 3, 4, 1, 7, 8, 2, 6, 0, 9};        for (size_t i = 0; i < sizeof(a)/sizeof(a[0]);++i)        {                t.InsertR(a[i], i);        }        cout<_key<_key<_key<
"C++中如何实现搜索二叉树"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！