C++实现二叉查找树

清疚 2022-02-23 04:50 166阅读 0赞

/*************************************************************
    **
    ** BinarySearchTree.h
    **
    ** BinarySearchTree template class.
    **
    ** By shaoguang @ 2019-04-06.
    **
    *************************************************************/
    
    #ifndef BINARY_SEARCH_TREE_H
    #define BINARY_SEARCH_TREE_H
    
    template <class T>
    class BinarySearchTree
    {
    public:
    	BinarySearchTree() : _root(nullptr) {}
    	BinarySearchTree(const BinarySearchTree& other)
    		: _root(nullptr)
    	{
    		_root = clone(other._root);
    	}
    	BinarySearchTree(BinarySearchTree&& other)
    		: _root(nullptr)
    	{
    		_root = other._root;
    		other._root = nullptr;
    	}
    	~BinarySearchTree()
    	{
    		makeEmpty();
    	}
    
    	// Find minimum value in the tree.
    	const T& findMin() const
    	{
    		return findMin(_root)->element;
    	}
    
    	// Find maximum value in the tree.
    	const T& findMax() const
    	{
    		return findMax(_root)->element;
    	}
    
    	// Is the tree contains x.
    	bool contains(const T& x) const
    	{
    		return contains(x, _root);
    	}
    
    	// Is the tree empty.
    	bool isEmpty() const
    	{
    		return nullptr == _root;
    	}
    
    	// Empty the tree.
    	void makeEmpty()
    	{
    		makeEmpty(_root);
    	}
    
    	// Insert a value to the tree.
    	void insert(const T& x)
    	{
    		insert(x, _root);
    	}
    	void insert(T&& x)
    	{
    		insert(x, _root);
    	}
    
    	// Remove a value in the tree.
    	void remove(const T& x)
    	{
    		remove(x, _root);
    	}
    
    	// Overload operator =.
    	BinarySearchTree& operator=(const BinarySearchTree& other)
    	{
    		if (this == &other)
    			return *this;
    		makeEmpty(_root);
    		_root = clone(other._root);
    		return *this;
    	}
    	BinarySearchTree* operator=(BinarySearchTree&& other)
    	{
    		if (this == &other)
    			return *this;
    		makeEmpty(_root);
    		_root = other._root;
    		other._root = nullptr;
    		return *this;
    	}
    
    private:
    	// The node of tree.
    	struct BinaryNode
    	{
    		T element;
    		BinaryNode* left;
    		BinaryNode* right;
    
    		BinaryNode(const T& e, BinaryNode* lt, BinaryNode* rt)
    			: element(e), left(lt), right(rt) {}
    		BinaryNode(T&& e, BinaryNode* lt, BinaryNode* rt)
    			: element(std::move(e)), left(lt), right(rt) {}
    	};
    
    	BinaryNode* _root;
    
    	void insert(const T& x, BinaryNode*& root)
    	{
    		if (nullptr == root)
    			root = new BinaryNode(x, nullptr, nullptr);
    		else if (x < root->element)
    			insert(x, root->left);
    		else if (root->element < x)
    			return insert(x, root->right);
    		else; // Repeating element, do noting.
    
    	}
    	void insert(T&& x, BinaryNode*& root)
    	{
    		if (nullptr == root)
    			root = new BinaryNode(std::move(x), nullptr, nullptr);
    		else if (x < root->element)
    			insert(std::move(x), root->left);
    		else if (root->element < x)
    			insert(std::move(x), root->right);
    		else; // Repeating element, do noting.
    	}
    
    	void remove(const T& x, BinaryNode*& t)
    	{
    		if (nullptr == t)
    			return;
    		if (x < t->element)
    			remove(x, t->left);
    		else if (t->element < x)
    			remove(x, t->right);
    		else if (nullptr != t->left && nullptr != t->right)
    		{
    			t->element = findMin(t->right)->elemrnt;
    			remove(t->element, t->right);
    		}
    		else
    		{
    			BinaryNode* oldNode = t;
    			t = (nullptr != t->left) ? t->left : t->right;
    		}
    	}
    
    	// Recursive implementation.
    	BinaryNode* findMin(BinaryNode* t) const
    	{
    		if (nullptr == t)
    			return nullptr;
    		if (nullptr == t->left)
    			return t;
    		return findMin(t->left);
    	}
    
    	// Non-recursive implementation.
    	BinaryNode* findMax(BinaryNode* t) const
    	{
    		if (nullptr != t)
    			while (nullptr != t->right)
    				t = t->right;
    		return t;
    	}
    
    	bool contains(const T& x, BinaryNode* t) const
    	{
    		if (nullptr == t)
    			return false;
    		else if (x < t->element)
    			return contains(x, t->left);
    		else if (t->element < x)
    			return contains(x, t->right);
    		else return true;
    	}
    
    	void makeEmpty(BinaryNode*& t)
    	{
    		if (nullptr != t)
    		{
    			makeEmpty(t->left);
    			makeEmpty(t->right);
    			delete t;
    		}
    		t = nullptr;
    	}
    
    	BinaryNode* clone(BinaryNode* t) const
    	{
    		if (nullptr == t)
    			return nullptr;
    		else
    			return new BinaryNode(t->element, clone(t->left), clone(t->right));
    	}
    };
    
    #endif // BINARY_SEARCH_TREE_H