c++搜索二叉樹/排序二叉樹-創(chuàng)新互聯(lián)

#pragma once

#include <iostream>

using namespace std;

template<class K, class V>

struct BsTreeNode{//二叉樹 節(jié)點
	K _key;
	V _value;
	BsTreeNode* _left;
	BsTreeNode* _right;
	
	BsTreeNode(const K& key,const V& value)
		:_key(key)
		, _value(value)
		, _left(NULL)
		, _right(NULL)
	{}
};


template<class K, class V>
class BsTree{

public:
typedef BsTreeNode<K, V> Node;
	BsTree()
		: _root(NULL)
	{
	}

	~BsTree(){}

	bool Insert(const K& key, const V& value)//插入 非遞歸
	{
		if (_root == NULL){
			_root = new Node(key, value);
			return true;
		}
		Node* cur = _root;
		while (1){
			if (cur->_key > key)
			{
				if (cur->_left)
					cur = cur->_left;
				else{
					cur->_left = new Node(key, value);
					return true;
				}
			}
			else if (cur->_key < key)
			{
				if (cur->_right)
					cur = cur->_right;
				else{
					cur->_right = new Node(key, value);
					return true;
				}
			}//以上為找 插入位置 并插入
			else if (cur->_key == key)//存在  插入失敗
				return false;
		}


	}

	bool InsertR(const K& key,const V& value)//插入 遞歸
	{
		return _InsertR(_root,key,value);
	}

	Node* Find(const K& key){//查找
		Node * cur = _root;
		while (cur){
			if (cur->_key > key)
				cur = cur->_left;
			else if (cur->_key < key)
				cur = cur->_right;
			else
				return cur;
		
		}
		return NULL;
	}

	bool RemoveR(const K& key)//刪除 遞歸
	{
		if (_root == NULL)
			return false;
		return _RemoveR(_root,key);
	}

	bool Remove(K key){//刪除 非遞歸
		Node* cur=_root, *prev=NULL;
		while (cur){
			if (cur->_key > key)
			{
				prev = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				prev = cur;
				cur = cur->_right;
			}// 以上為 找到要刪除的 節(jié)點
			else
			{
				if (cur->_left == NULL)//如果節(jié)點左或右為空，直接刪除該節(jié)//點將之后的節(jié)點 連接在其父節(jié)點
				{
					if (prev == NULL)
					{
						_root = cur->_right;
					
					}
					else if (prev->_left == cur)
					{
						prev->_left = cur->_right;

					}
					else
						prev->_right = cur->_right;
				}

				else if (cur->_right == NULL)//同上 右為空
				{
					if (prev == NULL)
					{
						_root = cur->_left;
						delete cur;
					}
					else if (prev->_right == cur)
					{
						prev->_right = cur->_left;

					}
					else
						prev->_left = cur->_left;
				}
				else//如果左右都不為空 找右孩子最左 或 左孩子最右 節(jié)點替
				//代刪除
				{

					prev = cur;
					cur = cur->_right;
					while (cur->_left){
						cur = cur->_left;
						
					}
					prev->_key = cur->_key;
					prev->_value = cur->_value;
					prev->_right =cur->_right;
					
				}

				delete cur;
				return true;
			}
		}
		return false;
	}
	bool modification(K key,V value){//修改
		
		Node* ret = Find(key);
		if (ret == NULL)
			return false;
		ret->_value = value;
		return true;

	}

private:
	bool _InsertR(Node* & root,const K& key,const V& value)//插入 遞歸函數(shù)
	{
		if (root == NULL)
		{
			root = new Node(key,value);
			return true;
		}

		if (root->_key == key)
			return false;
		else if (root->_key > key)
			return _InsertR(root->_left,key,value);
		else 
			return _InsertR(root->_right,key,value);
			
	}

	bool _RemoveR(Node* & root,const K& key)//刪除 遞歸函數(shù)
	{
		if (root->_key < key)
			return _RemoveR(root->_right, key);
		if (root->_key>key)
			return _RemoveR(root->_left, key);
		if (root->_left == NULL)
		{
			Node* dev = root;
			root = root->_right;
			delete dev;
			return true;
		}
		else if (root->_right == NULL)
		{
			Node* dev = root;
			root = root->_left;
			delete dev;
			return true;
		}
		else
		{
			root->_key = root->_right->_key;
			root->_value = root->_right->_value;
			return _RemoveR(root->_right,root->_key);
		}
	}

	Node* _root;
};

堅守“ 做人真誠 · 做事靠譜 · 口碑至上 · 高效敬業(yè) ”的價值觀，專業(yè)網(wǎng)站建設(shè)服務(wù)10余年為成都成都混凝土泵車小微創(chuàng)業(yè)公司專業(yè)提供成都企業(yè)網(wǎng)站定制營銷網(wǎng)站建設(shè)商城網(wǎng)站建設(shè)手機網(wǎng)站建設(shè)小程序網(wǎng)站建設(shè)網(wǎng)站改版，從內(nèi)容策劃、視覺設(shè)計、底層架構(gòu)、網(wǎng)頁布局、功能開發(fā)迭代于一體的高端網(wǎng)站建設(shè)服務(wù)。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

本文名稱：c++搜索二叉樹/排序二叉樹-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://www.muchs.cn/article42/dgisec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、企業(yè)網(wǎng)站制作、網(wǎng)站排名、外貿(mào)網(wǎng)站建設(shè)、靜態(tài)網(wǎng)站、商城網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)