温故而知新 -＞数据结构 -＞二叉搜索树 -＞ KV模型 -> 程序实现_利用类

本篇博客是基于温故而知新 -＞数据结构 -＞树 -＞二叉搜索树中有关KV模型的理论知识进行程序实现，同时也结合了温故而知新 -＞数据结构 -＞二叉树 -＞链式存储 -＞程序实现2_利用类中的部分内容！

其中实现了二叉搜索树的增（插入）删（删除）查（查找）改（没写(～￣▽￣)～），前序遍历等操作！并附带了实例以及对应的运行结果！前序、中序、后序三种遍历，获得树的高度、节点个数等操作！并附带了相关实例以及对应的运行结果！

注意：其中代码有很大冗余，未考虑性能最优，读者有兴趣可进一步精简！而且因为模板类中函数若想类外定义比较麻烦，所以直接在头文件中对类函数做了定义！

具体内容如下
（1）TreeKV.h

#pragma once
#include<iostream>
using namespace std;

template<class K,class V>
struct BNode
{
	K _key;
	V _value;
	typedef BNode<K, V> Node;
	Node *_left;
	Node *_right;

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

template<class K,class V>
class BTree
{
public:
	typedef BNode<K, V> Node;

	BTree()
		:_root(nullptr)
	{}

	BTree(const BTree<K, V>& btree)
		:_root(KVCopy(btree._root))
	{}

	Node *KVFind(const K& key)
	{
		if (!_root)
			return NULL;

		Node *cur = _root;
		while (cur)
		{
			if (cur->_key == key)
				return cur;
			else if (cur->_key > key)
				cur = cur->_left;
			else
				cur = cur->_right;
		}
		return cur;
	}

	Node *KVCopy(Node *root)
	{
		if (!root)
			return NULL;
		Node *newNode = new Node(root->_key, root->_value);
		newNode->_left = KVCopy(root->_left);
		newNode->_right = KVCopy(root->_right);
		return newNode;
	}
	// 不进行重复插值
	bool KVInsert(const K& key, const V& value)
	{
		if (_root == nullptr)
		{
			_root = new Node(key, value);
			return true;
		}
		//先进行搜索，找到合适的位置
		Node *cur = _root;
		Node *parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (cur->_key == key)
				return false;
			else if (cur->_key > key)
				cur = cur->_left;
			else
				cur = cur->_right;
		}
		//插入
		cur = new Node(key, value);
		if (parent->_key > key)
			parent->_left = cur;
		else
			parent->_right = cur;
		return true;
	}

	void KVInorder()
	{
		_inorder(_root);
		cout << endl;
	}
	//中序遍历有序
	void _inorder(Node *root)
	{
		if (root)
		{
			_inorder(root->_left);
			cout << root->_key << "-->" << root->_value << " ";
			_inorder(root->_right);
		}
	}

	void KVDestory(Node *root)
	{
		if (root)
		{
			KVDestory(root->_left);
			KVDestory(root->_right);
			cout << "destroy:" << root->_key << "-->" << root->_value << endl;
			delete root;
		}
	}

	bool KVErase(const K& key)
	{
		Node *cur = _root;
		Node *parent = nullptr;
		while (cur)
		{
			if (cur->_key == key)
				break;
			parent = cur;
			if (cur->_key > key)
				cur = cur->_left;
			else
				cur = cur->_right;
		}
		if (cur == nullptr)
			return false;

		//删除
		//1、删除的为叶子节点
		if (cur->_left == nullptr && cur->_right == nullptr)
		{
			if (cur == _root)
				_root = nullptr;
			else
			{
				if (parent->_left == cur)
					parent->_left = nullptr;
				else
					parent->_right = nullptr;
			}
			delete cur;
		}
		//2、左边为空的非叶子节点，叶子节点在父节点的哪边，其后续节点连载叶子节点的对应边
		else if (cur->_left == nullptr)
		{
			if (cur == _root)
				_root = _root->_right;
			else
			{
				if (parent->_left == cur)
					parent->_left = cur->_right;
				else
					parent->_right = cur->_right;
			}
			delete cur;
		}
		//3、右边为空的非叶子节点
		else if (cur->_right == nullptr)
		{
			if (cur == _root)
				_root = cur->_left;
			else
			{
				if (parent->_left = cur)
					parent->_left = cur->_left;
				else
					parent->_right = cur->_left;
			}
			delete cur;
		}
		//4、左右子树皆在
		else
		{
			//找左子树的最右节点--其为左子树上最大值
			Node *leftRightMost = cur->_left;
			parent = cur;
			while (leftRightMost->_right)
			{
				parent = leftRightMost;
				leftRightMost = leftRightMost->_right;
			}
			//交换
			swap(cur->_key, leftRightMost->_key);
			swap(cur->_value, leftRightMost->_value);
			//删除最右节点
			if (parent->_left == leftRightMost)
				parent->_left = leftRightMost->_left;
			else
				parent->_right = leftRightMost->_left;
			delete leftRightMost;
		}
		return true;
	}

	Node *KVRoot()
	{
		return _root;
	}
	// 前序遍历 中左右
	void preOrder(Node *root)
	{
		if (root)
		{
			cout << "key:" << root->_key << " value:" << root->_value << endl;
			preOrder(root->_left);
			preOrder(root->_right);
		}
	}

	~BTree()
	{
		if (_root)
		{
			KVDestory(_root);
			_root = nullptr;
		}
	}

private:
	Node *_root;
};

（2）main.cpp

#include"TreeKV.h"

void test()
{
	BTree<int, int> b;
	b.KVInsert(5, 50);
	b.KVInsert(3, 30);
	b.KVInsert(7, 70);
	b.KVInsert(1, 10);
	b.KVInsert(4, 40);
	b.KVInsert(6, 60);
	b.KVInsert(8, 80);
	b.KVInsert(0, 00);
	b.KVInsert(2, 20);
	b.KVInsert(9, 90);
	b.preOrder(b.KVRoot());
	cout << endl;

	b.KVInorder();
	cout << endl;

	b.KVErase(5); b.KVInorder();
	b.KVErase(3); b.KVInorder();
	b.KVErase(8); b.KVInorder();
	cout << endl;
}

int main()
{
	test();
	system("pause");
	return 0;
}