资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

如何进行搜索二叉树分析

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

创新互联建站坚持“要么做到,要么别承诺”的工作理念,服务领域包括:网站设计制作、网站建设、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的来凤网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!

一、搜索二叉树

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

2、性质:

  • 每个节点都有一个作为搜索依据的关键码(key),所有节点的关键码互不相同;

  • 左子树上所有节点的关键码(key)都小于根节点的关键码(key);

  • 右子树上所有节点的关键码(key)都大于根节点的关键码(key);

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

二、源代码

1、定义节点

template
struct BSTreeNode
{
	BSTreeNode *_left;//左节点
	BSTreeNode *_right;//右节点
	K _key;//节点权值
	V _value;

	BSTreeNode(const K& key,const V& value)
		:_key(key)
		,_value(value)
		,_left(NULL)
		,_right(NULL)
	{}
};

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

template
class BSTree
{
	typedef BSTreeNode 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<_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<_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)该节点左右皆不为空。

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

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


新闻标题:如何进行搜索二叉树分析
链接URL:http://www.cdkjz.cn/article/gpsccj.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220