C++——二叉树（进阶）
1.二叉搜索树
1.1概念
二叉搜索树又称
二叉排序树，它或是
一棵空树，又或是具有
以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值若它的右子树不为空，则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树
可以观察到，对这棵树进行
中序遍历的话，可以得到一串升序的数据
如果左子树放大的数据，右子树放小的数据，那么中序遍历就是降序了
1.2操作
1.2.1二叉搜索树的查找
一、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
二、最多查找高度次，如果走到空，还没找到，则这个值不存在。
1.2.2二叉搜索树的插入
一、树为空树，则直接新增节点，赋值给root指针
二、树不为空树，按二叉搜索树的性质查找插入位置，插入新节点
1.2.3二叉搜索树的删除
首先要查找所删除的元素
是否在二叉搜索树中，如果不存在，则返回
如果存在，则要删除的结点可以分为
下面四种情况：
一、要删除的结点无孩子结点
二、要删除的结点只有左孩子结点
三、要删除的结点只有右孩子结点
四、要删除的结点有左、右孩子结点这种情况是最难处理的，因为它不能直接托孤了，待删除的结点有两个孩子结点此时最好使用 替换法，找一个可以轻松脱身的结点，与待删除结点交换，然后再删除节点
综上，待删除结点有4种情况，但实际上，情况一可以与情况二或者三合并起来，因为叶子节点可以当作
左为空，也可以当作
右为空，所以真正的删除过程如下：
情况二：直接删除该结点，使被删除节点的 双亲结点指向被删除结点的左孩子结点情况三：直接删除该结点，使被删除节点的 双亲结点指向被删除结点的右孩子结点情况四：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除结点中，再来处理该结点的删除问题，使用替换法删除结点
1.3实现
1.3.1树的结点
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};这里一般不使用T，而使用K，因为这个数据结构的值要参与数据比较，一般把这个值叫做关键字 key
1.3.2插入
//BinarySearchTree.h
#pragma once
#include<iostream>
using namespace std;
//这里不写命名空间是因为，所写的东西与库中的命名不冲突
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool Insert(const K& key)//插入一个值
{
//初始时是空树
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//初始不为空树时，要去寻找插入的位置
Node* parent = nullptr;
Node* cur = _root; //cur是一个局部变量
//cur走到空的位置就可以完成插入了
while (cur)
{
parent = cur;
if (key > cur->_key)//插入的值比cur指向的_key大
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
//默认情况下，搜索二叉数是不允许有重复值的
else
{
return false;
//所以如果插入的值在树中已经存在了
//就return false
}
}
cur = new Node(key);
//判断cur是连接 在parent的左边还是右边
if (key > parent->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
private:
Node* _root = nullptr;
};1.3.2.1测试
//Test.cpp
#include"BinarySearchTree.h"
int main()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> bt;
for (auto e : a)
{
bt.Insert(e);
}
return 0;
}1.3.3中序遍历
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
void InOrder(Node* root)//中序遍历
{
if (root == nullptr)
return;
InOrder(root->_left);
cout << root->_key << " ";
InOrder(root->_right);
}
private:
Node* _root = nullptr;
};1.3.3.1测试时的问题
int main()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> bt;
for (auto e : a)
{
bt.Insert(e);
}
bt.InOrder();
//调用中序遍历要传递根结点，但这里不容易拿到
//二叉树的递归需要有参数
return 0;
}1.3.3.2解决方式一
写一个GetNode函数，把_root返回
1.3.3.3解决方式二
改写中序遍历的实现方式
C++中通常不使用方式一
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
void _InOrder(Node* root)//中序遍历
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
//类外面拿不到根结点，但是类里面可以使用
void InOrder()
{
_InOrder(_root);
}
private:
Node* _root = nullptr;
};
//测试成功
int main()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> bt;
for (auto e : a)
{
bt.Insert(e);
}
bt.InOrder();
return 0;
}C++中的递归通常都是这样去写的
1.3.4查找
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > _root->_key)
{
cur = cur->_right;
}
else if (key < _root->_key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
private:
Node* _root = nullptr;
};
1.3.5删除
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool Erase(const K& key)
{
//首先找到待删除的结点，同时要找到它的父亲
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{//查找的过程
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
//找到了待删除结点:cur
else
{
//开始删除
//1.情况三：左为空
if (cur->_left == nullptr)
{//先判断待删除节点是不是根节点
if (cur == _root)
{
_root = cur->_right;
}
else
{//判断父亲的哪个指针指向cur
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
}
//2.情况二：右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{//判断父亲的哪个指针指向cur
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
}
//3.情况四：左、右都不为空
else
{//默认找右树的最小节点来替换
//Node* parent = nullptr;
Node* parent = cur;
Node* subLeft = cur->_right;
while (subLeft->_left)
{
parent = subLeft;
subLeft = subLeft->_left;
}
swap(cur->_key, subLeft->_key);
//替换完之后，就要删除节点了
//注意：这里不能去复用函数来删除最左节点
//因为此时它已经不是二叉搜索树了，很可能根本就找不到最左节点
if (parent->_left == subLeft)
{
parent->_left = subLeft->_right;
}
else
{
parent->_right = subLeft->_right;
}
}
return true;
}//找到了待删除结点:cur
}//while结尾
//没有找到
return false;
}
private:
Node* _root = nullptr;
};
int main()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> bt;
for (auto e : a)
{
bt.Insert(e);
}
bt.InOrder();
bt.Erase(14);
bt.InOrder();
bt.Erase(3);
bt.InOrder();
bt.Erase(8);
bt.InOrder();
for (auto e : a)
{
bt.Erase(e);
bt.InOrder();
}
return 0;
}1.3.5.1注意事项
一、
二、
我们已经实现了二叉搜索树的增、删、查，那么二叉搜索树的修改，也需要实现吗？
二叉搜索树是不能随意修改的，因为修改之后，就很难保证这棵树依旧是二叉搜索树了。
1.4递归实现二叉搜索树
二叉搜索树本身是一个递归结构，但当前的实现，我们使用的是循环。
实际上还可以写一个递归版本的二叉搜索树
1.4.1查找
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool FindR(const K& key)
{
return _FindR(_root,key);
}
private:
//要实现递归，都要在里面多套一层
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
//比当前的值大，就转换成在当前节点的右子树去搜索
if (key > root->_key)
{
return _FindR(root->_right, key);
}
else if (key < root->_key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}
private:
Node* _root = nullptr;
};
1.4.2插入
1.4.2.1方式一
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool InsertR(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
return _InsertR(_root, key,nullptr);
}
private:
bool _InsertR(Node* root,const K& key,Node* parent)
{
if (root == nullptr)
{
root = new Node(key);
if (key > parent->_key)
{
parent->_right = root;
}
else
{
parent->_left = root;
}
return true;
}
if (key > root->_key)
{
return _InsertR(root->_right, key,root);
}
else if (key < root->_key)
{
return _InsertR(root->_left, key,root);
}
else
{
return false;
}
}
private:
Node* _root = nullptr;
};
1.4.2.1方式二：巧妙地使用引用
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
private:
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (key > root->_key)
{
return _InsertR(root->_right, key);
}
else if (key < root->_key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
private:
Node* _root = nullptr;
};
既然递归实现时，可以巧妙地使用引用来达成目的。
那么之前的循环实现的插入函数是不是也可以使用引用呢？
答案是不可以的。C++的引用不能改变指向，
比如起初是A的引用，那么之后就不能再变成B的引用、C的引用了，
int a = 0;
int& b = a;//给a取别名为b
int& c = a;
int& d = b;//给别名取别名
int x = 1;
b = x;//这里是赋值
//b已经是a的引用了，就不能再更改了递归时可以更改是因为，虽然都叫做root，但是每个栈帧中都是一个新的引用，不同作用域可以定义同名变量，每次都定义了一个新的引用，只是说前几次的引用没有起到作用，最后一次的引用才起到了作用。
1.4.3删除
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
//比它大，转换成在右树删除
if (key > root->_key)
{
return _EraseR(root->_right, key);
}
else if (key < root->_key)
{
return _EraseR(root->_left, key);
}
else
{//找到了节点，开始删除
if (root->_left == nullptr)
{
//使用引用传递参数，写起来就会很舒服
//不必再去判断是父亲的左还是右
Node* del = root;
root = root->_right;
delete del;
return true;
}
else if (root->_right == nullptr)
{
Node* del = root;
root = root->_left;
delete del;
return true;
}
else//左右都不为空
{
//这里还要去找替代节点
Node* subLeft = root->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
swap(root->_key, subLeft->_key);
//转换成在子树中，去递归删除
//在子树中，删除的节点一定 不是 左右都不为空的节点
return _EraseR(root->_right,key);
}
}
}
private:
Node* _root = nullptr;
};
画出递归展开图，有助于理解
1.5完善搜索树的实现
1.5.1析构函数
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
//不可能说对析构函数递归
//因为递归一定有一个特点：递归一定要控制参数
//由参数的变化来控制这棵树
~BSTree()
{
Destroy(_root);
}
//不写析构释放，是会产生内存泄露的，但是不会报错
private:
void Destroy(Node*& root)//注意auto是不能作为参数的
{
if (root == nullptr)
{
return;
}
//后序遍历
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
//直接置空是无用的，这里不影响实参
//之前的实现，通常使用二级指针
//但现在更好的办法是使用引用传参
}
private:
Node* _root = nullptr;
};Destroy函数的参数换成Node& root可以吗？
~BSTree()
{
Destroy(*_root);
}
//如果_root是空呢？所以这样实现纯纯是自找麻烦
void Destroy(Node& root)
{
}1.5.2拷贝构造
int main()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> bt;
for (auto e : a)
{
bt.InsertR(e);
}
bt.InOrder();
BSTree<int> copy(bt);
//没有写拷贝构造，这里就是浅拷贝，会崩溃
copy.InOrder();
return 0;
}如何书写呢？
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree(const BSTree<K>& t)
{
//t._root = Copy(_root);
_root = Copy(t._root);
}
private:
Node* Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
//前序遍历
Node* newRoot = new Node(root->_key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
private:
Node* _root = nullptr;
};