C++实现二叉搜索树BST,并实现多种方式遍历

#pragma once

class CBST
{
private:
    // 定义一个节点类型
    typedef struct tagNode {
        tagNode():m_pLeft(nullptr),m_pRight(nullptr),m_pParent(nullptr){};
        tagNode(int nVal, tagNode* pParent=nullptr, tagNode* pLeft=nullptr, tagNode* pRight=nullptr) :m_nVal(nVal),m_pLeft(pLeft), m_pRight(pRight), m_pParent(pParent){};
        int m_nVal; // 数据
        tagNode *m_pParent; // 父节点
        tagNode *m_pLeft; // 左孩子
        tagNode *m_pRight; // 右孩子
    }NODE,*PNODE;
public:
    CBST();
    CBST(const CBST& obj);
    CBST& operator=(const CBST& obj);
    ~CBST();
    // 插入
    bool Insert(int nVal);
    // 删除
    bool Delete(int nVal);
    // 修改
    bool Update(int nSrcVal,int nDstVal);
    // 查询
    bool Find(int nVal);
    // 清空
    void Clear();

    // 层序遍历 一层一层输出
    void LevelTraversal();
    // 递归前序遍历 根左右
    void MLR();
    // 递归中序遍历 左根右
    void LMR();
    // 递归后序遍历 左右根
    void LRM();

    // 中序使用循环
    void LMP_LOOP();
    // 前序使用循环
    void MLR_LOOP();
    // 后序使用循环
    void LRM_LOOP();
private:
    // 递归中序遍历 左根右
    void LMR(PNODE pNode);
    // 递归前序遍历 根左右
    void MLR(PNODE pNode);
    // 递归后序遍历 左右根
    void LRM(PNODE pNode);

    // 中序使用循环
    void LMP_LOOP(PNODE pNode);
    // 前序使用循环
    void MLR_LOOP(PNODE pNode);
    // 后序使用循环
    void LRM_LOOP(PNODE pNode);
private:
    // 查询并返回指针
    PNODE FindNode(int nVal);
    // 删除叶子节点
    void DeleteLeaf(PNODE pLeaf);
    // 删除单分节点
    void DeleteSingle(PNODE pSingle);
private:
    PNODE m_pRoot; // 根节点
};

#include "CBST.h"
#include 
#include 
#include 

using namespace std;

CBST::CBST()
{
	// 初始化根节点
	this->m_pRoot = nullptr; 
}

CBST::CBST(const CBST& obj)
{
	this->m_pRoot = nullptr;
	*this = obj;
}

CBST& CBST::operator=(const CBST& obj)
{
	if (this == &obj) return *this;
	// 清除自己
	Clear();
	// 拷贝obj
	
	deque trees;
	
	trees.push_back(obj.m_pRoot);
	while (!trees.empty()) {
		// 获取队首
		auto temp = trees.front();
		Insert(temp->m_nVal); 
		// 弹出队首
		trees.pop_front();
		// 把左右两边入队
		if (temp->m_pLeft != nullptr) {
			trees.push_back(temp->m_pLeft);
		}
		if (temp->m_pRight != nullptr) {
			trees.push_back(temp->m_pRight);
		}
	}
	return *this;
}

CBST::~CBST()
{
	// 释放内存
	Clear();
}


bool CBST::Insert(int nVal)
{
	// 创建节点
	PNODE pNewNode = new NODE(nVal); // pNewNode 保存new出来的这个地址
	// 如果分配失败的话
	if(pNewNode == nullptr){
		return false;
	}
	// 如果分配成功的话
	if(this->m_pRoot == nullptr){
		// 如果现在是一颗空树
		this->m_pRoot = pNewNode; // 相当于和pNewNode一样保存第一个new出来的节点地址
		return true;
	}
	// 如果不是空树 开始遍历 直至某个节点的叶子节点为null就插入
	PNODE pNode = this->m_pRoot; // 用一个临时节点 表示根节点 不修改根节点的数据
	while(true){
		// 如果当前节点的值 大于我们要插入的值 左边
		if(nVal < pNode->m_nVal){
			if(pNode->m_pLeft != nullptr){
				// 如果还有左孩子继续判断
				pNode = pNode->m_pLeft;
			}else{
				// 当前节点插入到左边
				pNode->m_pLeft = pNewNode;
				// 保存父节点
				pNewNode->m_pParent = pNode;
				return true;
			}
		}else if(nVal > pNode->m_nVal){
			// 如果当前节点的值 小于我们要插入的值 右边
			if (pNode->m_pRight != nullptr) {
				// 如果还有右孩子 继续判断
				pNode = pNode->m_pRight;
			}else {
				// 当前节点插入到右边
				pNode->m_pRight = pNewNode;
				// 保存父节点
				pNewNode->m_pParent = pNode;
				return true;
			}
		}else{
			// 暂时不考虑相等
			return false;
		}
	}
	return true;
}

// 删除叶子节点
void CBST::DeleteLeaf(PNODE pLeaf)
{
	
	// 获取父节点
	auto pParendNode = pLeaf->m_pParent;
	if (pParendNode == nullptr) {
		delete pParendNode; // 直接删除根节点
		pParendNode = nullptr;
		this->m_pRoot = nullptr; // 把根节点指针置为null
		return;
	}

	
	if(pParendNode->m_nVal > pLeaf->m_nVal){
		// 如果是左孩子 左孩子置空
		pParendNode->m_pLeft = nullptr;
	}else if(pParendNode->m_nVal < pLeaf->m_nVal){
		// 如果是右孩子 右孩子置空
		pParendNode->m_pRight = nullptr;
	}
	// 最后释放内存
	delete pLeaf; 
	pLeaf = nullptr;
}


void CBST::DeleteSingle(PNODE pSingle)
{
	
	
	
	auto pParentNode = pSingle->m_pParent;
	
	auto pLeftOrRightNode = pSingle->m_pLeft == nullptr ? pSingle->m_pRight : pSingle->m_pLeft;
	
	// 如果父节点为空 代表删除的是根节点
	if (pParentNode == nullptr){
		// 根节点 切换 为它的左右节点
		this->m_pRoot = pLeftOrRightNode;
		pLeftOrRightNode->m_pParent = nullptr; // 他作为新的根节点 没有父亲
		delete pSingle; // 释放根节点内存
		pSingle = nullptr;
		return; 
	}

	// 修改拿到的这个节点的父节点 为要删除的节点的父节点
	pLeftOrRightNode->m_pParent = pParentNode; // 就等于跳过中间那一层
	
	
	if(pLeftOrRightNode->m_nVal < pParentNode->m_nVal){
		// 提上来的节点放左边
		pParentNode->m_pLeft = pLeftOrRightNode;
	}else if (pLeftOrRightNode->m_nVal > pParentNode->m_nVal){
		// 提上来的节点放右边
		pParentNode->m_pRight = pLeftOrRightNode;
	}
	// 释放内存
	delete pSingle;
	pSingle = nullptr;
}


bool CBST::Delete(int nVal)
{
	
	// 查询节点
	auto pNodeToDel = FindNode(nVal);
	if(pNodeToDel == nullptr){
		// 如果没找到这个节点 
		return false;
	}
	// 1.叶子
	// 如果找到的这个节点是一个叶子节点
	if(pNodeToDel->m_pLeft == nullptr && pNodeToDel->m_pRight == nullptr){
		DeleteLeaf(pNodeToDel);
		return true;
	}
	// 如果代码能走到这就代表它不是叶子 那么我们判断 如果有一边为空 就是单分支了
	// 2.单分支
	if(pNodeToDel->m_pLeft == nullptr || pNodeToDel->m_pRight == nullptr){
		DeleteSingle(pNodeToDel);
		return true;
	}
	// 这里就不用判断了 能走到这里一定就是双分支了 既不是叶子 也不是单分支
	// 3.双分支
	
	auto pMaxInLeft = pNodeToDel->m_pLeft; 
	// 当这个循环结束 我们就找到了 被删除节点中的左子树的最大值了
	while(pMaxInLeft->m_pRight != nullptr){
		pMaxInLeft = pMaxInLeft->m_pRight;
	}
	// 找到最大值了 和 原本的节点的值进行替换
	int tempVal = pNodeToDel->m_nVal;
	pNodeToDel->m_nVal = pMaxInLeft->m_nVal;
	pMaxInLeft->m_nVal = tempVal;
	// 交换值完毕 接着就是把 pMaxInLeft 给删掉
	// 它可能是叶子节点 也 可能是单分支
	// 如果他是叶子节点
	if (pMaxInLeft->m_pLeft == nullptr && pMaxInLeft->m_pRight == nullptr) {
		DeleteLeaf(pMaxInLeft);
		return true;
	}
	// 如果它是单分支
	else{
		DeleteSingle(pMaxInLeft);
		return true;
	}
}


bool CBST::Update(int nSrcVal, int nDstVal)
{
	
	if(Find(nSrcVal)){
		Delete(nSrcVal);
		Insert(nDstVal);
	}
	return false;
}


bool CBST::Find(int nVal)
{
	if (this->m_pRoot == nullptr) {
		// 如果是空树查找失败
		return false;
	}
	// 如果不是空树开始遍历
	PNODE pNode = this->m_pRoot;
	while(true){
		if(nVal < pNode->m_nVal){
			// 如果小于 向左边
			if(pNode->m_pLeft == nullptr){
				// 左边没有了
				return false; // 那就是没有找到
			}else{
				// 如果左边还有 向左边移动
				pNode = pNode->m_pLeft;
			}
		}else if(nVal > pNode->m_nVal){
			// 如果大于 向右边
			if(pNode->m_pRight == nullptr){
				// 右边没有了
				return false; // 那就是没有了
			}else{
				// 如果还有 向右边移动继续找
				pNode = pNode->m_pRight;
			}
		}else{
			// 相等
			return true;
		}
	}
	return false;
}


CBST::PNODE CBST::FindNode(int nVal)
{
	
	// 如果不是空树 从根节点开始
	PNODE pNode = this->m_pRoot;
	while (pNode != nullptr){ 
		// 小于找左边
		if(nVal < pNode->m_nVal){
			pNode = pNode->m_pLeft;
			// 大于找右边
		}else if(nVal > pNode->m_nVal){
			pNode = pNode->m_pRight;
		}else{
			// 相等直接返回
			return pNode;
		}
	}
	// 如果退出循环了那就是找不到
	return nullptr;
}

void CBST::Clear()
{
	while (this->m_pRoot != nullptr){
		Delete(this->m_pRoot->m_nVal);
	}
}

// 层序遍历
void CBST::LevelTraversal()
{
	
	deque trees;
	if (this->m_pRoot == nullptr){
		cout << "空树" << endl;
		return;
	}
	
	trees.push_back(this->m_pRoot);
	while(!trees.empty()){
		// 获取队首
		auto temp = trees.front();
		// 弹出队首
		trees.pop_front();
		cout << temp->m_nVal <<  " ";
		// 把左右两边入队
		if(temp->m_pLeft != nullptr){
			trees.push_back(temp->m_pLeft);
		}
		if (temp->m_pRight != nullptr) {
			trees.push_back(temp->m_pRight);
		}
	}
	cout << endl;
}

// 前序遍历 根左右
void CBST::MLR()
{
	if (this->m_pRoot == nullptr) {
		cout << "空树" << endl;
		return;
	}
	MLR(this->m_pRoot);
}

// 中序遍历 左根右
void CBST::LMR()
{
	if (this->m_pRoot == nullptr) {
		cout << "空树" << endl;
		return;
	}
	LMR(this->m_pRoot);
}

// 后序遍历 左右根
void CBST::LRM()
{
	if (this->m_pRoot == nullptr) {
		cout << "空树" << endl;
		return;
	}
	LRM(this->m_pRoot);
}

// 中序使用循环
void CBST::LMP_LOOP()
{
	if (this->m_pRoot == nullptr) {
		cout << "空树" << endl;
		return;
	}
	LMP_LOOP(this->m_pRoot);
}

// 前序使用循环
void CBST::MLR_LOOP()
{
	if (this->m_pRoot == nullptr) {
		cout << "空树" << endl;
		return;
	}
	MLR_LOOP(this->m_pRoot);
}

// 后序使用循环
void CBST::LRM_LOOP()
{
	if (this->m_pRoot == nullptr) {
		cout << "空树" << endl;
		return;
	}
	LRM_LOOP(this->m_pRoot);
}

// 中序遍历 左根右
void CBST::LMR(PNODE pNode)
{
	// 开始递归
	if(pNode != nullptr){
		LMR(pNode->m_pLeft);
		cout << pNode->m_nVal << " ";
		LMR(pNode->m_pRight);
	}
}

// 前序遍历 根左右
void CBST::MLR(PNODE pNode)
{
	// 开始递归
	if (pNode != nullptr) {
		cout << pNode->m_nVal << " ";
		MLR(pNode->m_pLeft);
		MLR(pNode->m_pRight);
	}
}

// 后序遍历 左右根
void CBST::LRM(PNODE pNode)
{
	// 开始递归
	if (pNode != nullptr) {
		LRM(pNode->m_pLeft);
		LRM(pNode->m_pRight);
		cout << pNode->m_nVal << " ";
	}
}

// 中序使用循环
void CBST::LMP_LOOP(PNODE pNode)
{
	// 换行
	cout << endl;
	// 定义一个栈
	stack treesStack;
	// 根节点入栈
	treesStack.push(pNode);
	// 当栈不为空的时候
	while (!treesStack.empty()){
		if(pNode->m_pLeft != nullptr){
			// 如果左边不为空入栈
			treesStack.push(pNode->m_pLeft);
			pNode = pNode->m_pLeft;
			continue; // 直接进入下一次循环
		}
		// 如果左边为空 从栈里面取出来
		auto curNode = treesStack.top(); // 获取栈顶元素
		cout << curNode->m_nVal << " "; // 输出栈顶元素
		treesStack.pop(); // 弹出栈顶元素
		// 如果有右孩子 右孩子入栈
		if(curNode->m_pRight != nullptr){
			treesStack.push(curNode->m_pRight);
			pNode = curNode->m_pRight;
			continue;
		}
	}
}

// 前序使用循环
void CBST::MLR_LOOP(PNODE pNode)
{
	// 换行
	cout << endl;
	// 定义一个栈
	stack treesStack;
	
	while(true){
		// 当前节点不为空的话
		while(pNode != nullptr){
			// 输出根的值
			cout << pNode->m_nVal << " ";
			// 判断有没有右孩子
			if(pNode->m_pRight != nullptr){
				// 入栈
				treesStack.push(pNode->m_pRight);
			}
			// 往左走
			pNode = pNode->m_pLeft;
		}

		// 如果栈为空了 遍历结束
		if (treesStack.empty()) {
			break;
		}

		// 退出这个循环就是左边为空了 需要从栈里面取出来一个
		// 如果左边为空 从栈里面取出来
		// 同时当前根节点修改为弹出来的这个元素
		pNode = treesStack.top(); // 获取栈顶元素
		treesStack.pop(); // 弹出栈顶元素
	}
}

// 后序使用循环
void CBST::LRM_LOOP(PNODE pNode)
{
	// 换行
	cout << endl;
	// 定义一个栈
	stack treesStack;
	// 记录最后一次输出的值
	PNODE pLastHandledNode = nullptr;

	while(true){

		// 一路向左入栈
		while(pNode != nullptr){
			treesStack.push(pNode);
			pNode = pNode->m_pLeft;
		}

		// 栈为空
		if(treesStack.empty()){
			break;
		}

		// 这样就左边全部入栈完毕了 访问栈顶
		auto curNode = treesStack.top();

		if(curNode->m_pRight == pLastHandledNode || curNode->m_pRight == nullptr){
			// 如果上一次输出的就是它的右节点 或者它没有右节点 那么它就可以处理了
			cout << curNode->m_nVal << " ";
			treesStack.pop(); // 出栈
			pLastHandledNode = curNode; // 更新上一次输出的节点
		}else{
			// 否则把处理右节点
			pNode = curNode->m_pRight;
		}
		
	}
}

#include 
#include 
#include "CBST.h"

using namespace std;

int main()
{
	int ary[] = {
		50,
		30,70,
		20,40,60,90,
		10,25,35,45,55,65,80,99,
		42,56,62,67,85,
		69
	};
	CBST BST;
	for(int i = 0; i < sizeof(ary)/sizeof(ary[0]); i++){
		BST.Insert(ary[i]);
	}
	// 接着测试删除 
	//BST.Delete(70);
	//BST.Delete(69);
	//BST.Delete(67);
	//BST.Delete(65);
	//BST.Delete(80);
	//BST.Delete(10);
	//BST.Delete(20);
	//BST.Delete(50);
	//BST.Delete(60);
	
	// 层序遍历
	// BST.LevelTraversal();

	// 中序遍历
	BST.LMR();
	BST.LMP_LOOP();
	// 先序遍历
	cout << endl;
	BST.MLR();
	BST.MLR_LOOP();
	// 后序遍历
	cout << endl;
	BST.LRM();
	BST.LRM_LOOP();

	CBST BST1;
	BST1 = BST;
	BST1.LRM_LOOP();
	system("pause");
	return 0;
}