二叉排序树的C++实现

系统管理员 2022-06-09 11:18 176阅读 0赞

二叉排序树的主要操作有插入、创建、查找、删除。用C++实现了一下

#include <iostream>
    using namespace std;
    #include <stack>
    
    class Node 
    {
    	int data;
    	Node *lchild;
    	Node *rchild;
    public:
    	Node (int val, Node *left = NULL, Node *right = NULL)
    	{
    		data = val;
    		lchild = left;
    		rchild = right;
    	}
    	int Data()
    	{
    		return data;
    		
    	}
    	friend class Binary_sort_Tree;
    };
    
    class Binary_sort_Tree
    {
    private:
    	Node *root;
    public:
    	Binary_sort_Tree()
    	{
    		root = NULL;
    	}
    	~Binary_sort_Tree(){};
    	void Insert(Node *&temp, int a);
    	void Creat(int *a, int n);
    	Node* search(Node *cur, int val);
    	Node* Search(int val)
    	{
    		return search(root, val);
    	}
    	bool DeleteBST(Node *&cur, int val);
    	bool Delete(Node *&cur);
    	void InOrder();
    
    	Node* Root()
    	{
    		return root;
    	}
    };
    
    void Binary_sort_Tree::Insert(Node *&temp, int a)
    {
    	if (temp == NULL)
    		temp = new Node(a);
    	else if (temp->data >= a)
    		Insert(temp->lchild, a);
    	else
    		Insert(temp->rchild, a);
    }
    void Binary_sort_Tree::Creat(int *a, int n)
    {
    	for (int i = 0; i < n; i++)
    		Insert(root, a[i]);
    }
    void Binary_sort_Tree::InOrder()
    {
    	Node *cur = root;
    	if (cur == NULL)
    		return;
    	stack<Node *> s;
    	while (cur || !s.empty())
    	{
    		while (cur)
    		{
    			s.push(cur);
    			cur = cur->lchild;
    		}
    		Node *top = s.top();
    		s.pop();
    		cout<<top->data<<" ";
    		cur = top->rchild;
    	}
    	cout<<endl;
    }
    Node* Binary_sort_Tree::search(Node *cur, int val)
    {
    	Node *temp = cur;
    	Node *ret = NULL;
    	if (temp == NULL)
    		return ret;
    	if (temp->data == val)
    		ret = temp;
    	else if (temp->data < val)
    	{
    		ret = search(temp->lchild, val);
    	}
    	else
    	{
    		ret = search(temp->rchild, val);
    	}
    	return ret;
    }
    bool Binary_sort_Tree::DeleteBST(Node *&cur, int val)
    {
    	if (cur == NULL)
    	{
    		return false;
    	}
    	if (cur->data == val)
    	{
    		return Delete(cur);
    	}
    	else if (cur->data > val)
    	{
    		return DeleteBST(cur->lchild, val);
    	}
    	else
    	{
    		return DeleteBST(cur->rchild, val);
    	}
    }
    bool Binary_sort_Tree::Delete(Node *&cur)
    {
    	if (cur->rchild == NULL)
    	{
    		Node *temp = cur;
    		cur = cur->lchild;
    		delete temp;
    	}
    	else if (cur->lchild == NULL)
    	{
    		Node *temp = cur;
    		cur = cur->rchild;
    		delete temp;
    	}
    	else
    	{//左右子树均不为空
    		Node *temp = cur;
    		Node *p = cur->lchild;
    		while (p->rchild)
    		{
    			temp = p;
    			p = p->rchild;
    		}
    		cur->data = p->data;
    		if (cur != temp)
    			temp->rchild = p->lchild;
    		else
    			temp->lchild = p->rchild;
    		delete p;
    	}
    	return true;
    }
    
    
    
    
    void main()
    {
    	Binary_sort_Tree tree;
    	int a[] = {62,88,58,47,35,73,51,99,37,93};
    	tree.Creat(a, 10);
    	tree.InOrder();
    	Node *temp = tree.Root();
    	bool Delete = tree.DeleteBST(temp,58);
    	if (Delete == false)
    		cout<<"NULL"<<endl;
    	else
    		tree.InOrder();
    }

主要的操作难点在于删除操作，删除也是先查找才能删除，查找部分采用递归，删除的话分三种情况，即左子树为空，右子树为空，或者左右子树均不为空。需要注意的是，在前两种情况删除结点的时候，参数需要采用引用，不然删除结点的时候会出现问题。