C++ 二叉搜索树

笔记

二叉搜索树1

二叉搜索树2

二叉搜索树3

代码模拟实现

BSTree.h

#pragma once

#include <iostream>
using namespace std;
//节点
template<class K>
struct BSTNode
{
	K _key;
	BSTNode<K>* _left;
	BSTNode<K>* _right;

	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

//二叉树
template<class K>
class BSTree
{
	typedef BSTNode<K> Node;

public:
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
				return false; //不允许重复
		}

		cur = new Node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}

	bool Find(const K& key)
	{
		Node* cur = _root;

		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
				return true; //相等的时候
		}

		return false;        //没有相等的时候
	}

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//相等删除
				if (cur->_left == nullptr) //左子树为空
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{

						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;

						}
					}

					delete cur;
				}
				else if (cur->_right == nullptr) //右子树为空
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{

						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;

						}
					}

					delete cur;
				}
				else //左右都不为空
				{
					//用右子树的最小节点替代（或左子树的最大节点）
					Node* replaceParent = cur;  //此时已经确定向右子树
					Node* replace = cur->_right;
					while (replace->_left)
					{
						replaceParent = replace;
						replace = replace->_left;
					}

					swap(cur->_key, replace->_key);

					//用来判断replace是replaceParent的左孩子还是右孩子
					if (replaceParent->_left == replace) //左孩子
					{
						replaceParent->_left = replace->_right; //replace可能还有右孩子，也可能是nullptr
					}
					else //右孩子
					{
						replaceParent->_right = replace->_right;
					}

					delete replace;
				}

				return true;
			}
		}

		return false;
	}

	void InOrder() //在外部调用的函数，调用的时候不能知道内部的_root
	{
		_InOrder(_root);//类内部可以知道内部成员变量
		cout << endl;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;
};

Test.cpp

#include"BSTree.h"

void TestBSTree1()
{
	int a[] = { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13 };
	BSTree<int> t;

	for (auto e : a)
	{
		t.Insert(e);
	}

	t.InOrder();

	t.Insert(16);
	t.InOrder();

	t.Insert(3);
	t.InOrder();

	// 左右都不为空
	t.Erase(8);
	t.InOrder();

	t.Erase(3);
	t.InOrder();

	// 右为空
	t.Erase(14);
	t.InOrder();

	// 左为空
	t.Erase(6);
	t.InOrder();

	for (auto e : a)
	{
		t.Erase(e);
		t.InOrder();
	}
}

//void TestBSTree2()
//{
//	BSTree<string, string> dict;
//	dict.Insert("insert", "插入");
//	dict.Insert("erase", "删除");
//	dict.Insert("left", "左边");
//	dict.Insert("string", "字符串");
//
//	string str;
//	while (cin >> str)
//	{
//		auto ret = dict.Find(str);
//		if (ret)
//		{
//			cout << str << ":" << ret->_value << endl;
//		}
//		else
//		{
//			cout << "单词拼写错误" << endl;
//		}
//	}
//
//	string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
//	// 统计水果出现的次
//	BSTree<string, int> countTree;
//	for (auto str : strs)
//	{
//		auto ret = countTree.Find(str);
//		if (ret == NULL)
//		{
//			countTree.Insert(str, 1);
//		}
//		else
//		{
//			ret->_value++;
//		}
//	}
//	countTree.InOrder();
//}

int main()
{
	TestBSTree1();

	return 0;
}

面试题

假设D类先继承B1，然后继承B2，B1和B2基类均包含虚函数，D类对B1和B2基类的虚函数重写了，并且D类增加了新的虚函数，则：（）

A.D类对象模型中包含了3个虚表指针

B.D类对象有两个虚表，D类新增加的虚函数放在第一张虚表最后

C.D类对象有两个虚表，D类新增加的虚函数放在第二张虚表最后

D.以上全部错误

A.D类有几个父类，如果父类有虚函数，则就会有几张虚表，自身子类不会产生多余的虚表，所以只有2张虚表

B.正确

C.子类自己的虚函数只会放到第一个父类的虚表后面，其他父类的虚表不需要存储，因为存储了也不能调用

B2 的虚表本身要保留，因为你可以通过 B2* 调用虚函数

D 的新虚函数不放进 B2 的虚表里，因为 B2* 无法调用 D 的新函数（编译器禁止）

D.错误

学习笔记&练习文章被收录于专栏

学习过程中的一些记录