如何进行搜索二叉树分析

如何进行搜索二叉树分析，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

一、搜索二叉树

1、定义：它是一棵排序二叉树，可为空树。

2、性质：

• 每个节点都有一个作为搜索依据的关键码（key），所有节点的关键码互不相同；

• 左子树上所有节点的关键码（key）都小于根节点的关键码（key）；

• 右子树上所有节点的关键码（key）都大于根节点的关键码（key）；

• 左、右子树都是二叉搜索树。

二、源代码

1、定义节点

template<class K,class V> struct BSTreeNode {	BSTreeNode<K,V> *_left;//左节点	BSTreeNode<K,V> *_right;//右节点	K _key;//节点权值	V _value;	BSTreeNode(const K& key,const V& value)	:_key(key)	,_value(value)	,_left(NULL)	,_right(NULL)	{} };

2、搜索二叉树及其相关实现

template<class K,class V> class BSTree {	typedef BSTreeNode<K,V> Node; public:	BSTree()	:_root(NULL)	{}	//非递归	Node* Find(const K& key)	{	return _Find(_root,key);	}	bool Insert(const K& key,const V& value)	{	return _Insert(_root,key,value);	}	bool Remove(const K& key)	{	return _Remove(_root,key);	}	//递归	bool InOrder() //中序遍历 --> 有序序列	{	return _InOrder(_root);	cout<<endl;	}	Node* FindR(const K& key)	{	return _FindR(_root,key);	}	bool InsertR(const K& key,const V& value)	{	return _InsertR(_root,key,value);	}	bool RemoveR(const K& key)	{	return _RemoveR(_root,key);	} protected:	//非递归	Node* _Find(Node *root,const K& key)	{	if(root == NULL) return NULL;	Node *cur=root;	if(cur->_key > key)	{	cur=cur->_right;	}	else if(cur->_key < key)	{	cur=cur->_left;	}	else 	{	return cur;	}	return NULL;	}	bool _Insert(Node *&root,const K& key,const V& value)	{	if(root == NULL)	{	root=new Node(key,value);	return true;	}	Node *cur=root;	Node *parent=NULL;	while(cur)	{	if(cur->_key < key)	{	parent=cur;	cur=cur->_right;	}	else if(cur->_key > key)	{	parent=cur;	cur=cur->_left;	}	else	return false;	}	if(parent->_key < key)	{	parent->_right=new Node(key,value);	parent->_right=parent;	}	else	{	parent->_left=new Node(key,value);	parent->_left=parent;	}	return true;	}	bool _Remove(Node*& root,const K& key )	{	if(root == NULL) return false;	Node *cur=root;	Node *parent=NULL;	while(cur) //找节点	{	if(cur->_key > key)	{	parent=cur;	cur=cur->_left;	}	else if(cur->_key < key)	{	parent=cur;	cur=cur->_right;	}	else //找到节点	{	if(cur->_left == NULL)//左为空	{	if(parent == NULL)	root=cur->_right;	else if(parent->_left == cur)	parent->_left=cur->_right;	else	parent->_right=cur->_right;	}	else if(cur->_right == NULL)//右为空	{	if(parent == NULL)	root=cur->_left;	else if(parent->_left == cur)	parent->_left=cur->_left;	else	parent->_right=cur->_left;	}	else //左右都不为空	{	Node *parent=cur;	Node *left=cur->_right;//右子树的最左节点	while(left->_left)	{	left=left->_left;	}	cur->_key=left->_key;//替换结点	cur->_value=left->_value;	if(parent->_left == left)	parent->_left=left->_left;	else	parent->_right=left->_right;	delete left;	}	}	return true;	}	return false;	}	//递归	bool _InOrder(Node *root)	{	if(root == NULL) return false;	_InOrder(root->_left);	cout<<root->_left<<" ";	_InOrder(root->_right);	return true;	}	Node* _FindR(Node *root,const K& key)	{	if(root == NULL) return NULL;	if(root->_key == key)	return root;	else if(root->_key > key)	return _FindR(root->_left,key);	else	return _FindR(root->_right,key);	}	bool _InsertR(Node *root,const K& key,const V& value)	{	if(root == NULL) 	{	root=new Node(key,value);	return true;	}	if(root->_key > key)	return _InsertR(root->_left,key,value);	else if(root->_key < key)	return _InsertR(root->_right,key,value);	else	return false;	}	bool _RemoveR(Node *root,const K& key)	{	if(root == NULL) return false;	if(root->_key > key)	return _RemoveR(root->_left,key); 	else if(root->_key < key)	return _RemoveR(root->_right,key);	else  //找到节点	{	Node *del=NULL;	if(root->_left == NULL) 	root=root->_right;	else if(root->_right == NULL)	root=root->_left;	else 	{	Node *parent=NULL;	Node *left=root;	while(left->_left)	{	parent=left;	left=left->_left;	}	root->_key=left->_key;	root->_value=left->_value;	del=left;	if(parent->_left == left)	parent->_left=left->_left;	else	parent->_right=left->_right;	delete del;	return true;	}	}	return false;	} protected:	Node *_root; };

3、总结：

    搜索二叉树是一棵排序二叉树，可为空树。它的每一个节点都遵从搜索二叉树的性质。

    搜索二叉树的中序遍历后为升序序列；其查找根据key值以及性质进行；其插入需先根据其key值找到插入的节点，随后添加节点，另外其key值唯一；

    其删除节点时，需分3种情况：

   （1）仅左为空；

   （2）仅右为空；

   （3）该节点左右皆不为空。

        删除该节点，即需 找到 右子树的最左节点 或 左子树的最右节点，作为替换结点。

看完上述内容，你们掌握如何进行搜索二叉树分析的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注亿速云行业资讯频道，感谢各位的阅读！