二叉树

一.二叉搜索树的特点

二叉搜索树是一种特殊的二叉树

它的特点是:

1.左子树的所有节点均比根节点的值小

2.右子树的所有节点均比根节点的值大

3.左右子树都是二叉搜索树

4.中序遍历序列是有序的

5.一般二叉搜索树不允许有重复值

当然,二叉搜索树默认是升序的,不过也可以实现成降序的样子

只需要更改一下第1条和第2条即可,

第一条改为左子树的节点都要大于根节点

第二条改为右子树的节点都要小于根节点

此时实现出来的二叉搜索树就是降序的

例如:这个树就是一个二叉搜索树

二.我们要实现的大致框架

#pragma once
#include <iostream>
using namespace std;
//BST排升序:左孩子小于我,  右孩子大于我
//排降序:   左孩子大于我,  右孩子小于我


//节点的结构体
template <class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left = nullptr;
	BSTreeNode<K>* _right = nullptr;
	K _key;
	BSTreeNode(const K& key)
		:_key(key)
	{}
};


template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	//非递归实现insert.find,erase
	bool Insert(const K& key);


	Node* Find(const K& key);


	bool Erase(const K& key);


	//析构函数  后续遍历析构
	~BSTree();
	
	//C++11新语法
	BSTree() = default;//强制生成默认构造
	
	//拷贝构造
	//先序遍历构造
	BSTree(const BSTree<K>& bst);


	//赋值运算符重载:现代版本
	BSTree<K>& operator=(BSTree<K> bst);


	void InOrder()
	{
		_InOrder(_root);
	}


	//递归实现insert.find,erase
	Node* FindR(const K& key)
	{
		return _FindR(_root,key);
	}


	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}


	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
	
private:
	//拷贝构造函数的子函数
	Node* _Copy(const Node* root);
	//析构函数的子函数
	void _Destroy(Node*& root);
	//中序遍历的子函数
	void _InOrder(Node* root);
	//find的子函数
	Node* _FindR(Node* root, const K& key);
	//insert的子函数
	bool _InsertR(Node*& root, const K& key);
	//erase的子函数
	bool _EraseR(Node*& root, const K& key);
	
	//给根节点_root缺省值nullptr
	Node* _root = nullptr;
};

这是Key模型的版本,最后我们要修改一份Key-Value版本

template <class K>

这里模板给K的原因是:贴合K模型而已,所以没有用T

这里的R : recursion(递归的英文)

//给根节点_root缺省值nullptr
Node* _root = nullptr;

这里直接给根节点_root缺省值nullptr了,编译器默认生成的构造函数就会使用这个缺省值

这里补充一点:

//C++11新语法:给default这个关键字增加了一个含义
BSTree() = default;//强制生成默认构造