当前位置：首页 > news >正文

二叉树进阶

news 2025/7/3 22:36:55

一、二叉搜索树

1.二叉搜索树的概念

二叉搜索树又称二叉排序树，它也可以是一棵空树，或是具备以下性质的树：

1.1 若它的左子树不为空，则它左子树上所有节点的值都小于根节点的值。

1.2 若它的右子树不为空，则它右子树上所有节点的值都大于根节点的值。

1.3 它的左右子树也都是二叉搜索树。

2.二叉搜索树的操作

int a[]={8,3,1,10,6,4,7,14,13};

2.1 二叉搜索树的节点的定义

二叉树的每个不为空的节点都存储着左孩子和右孩子节点的指针，以及当前节点的值。

template<class T>
//一个节点的构造
struct BSTNode
{BSTNode(const T& data = T()):_right(nullptr), _left(nullptr), _data(data){}BSTNode<T>* _right;		//左孩子节点的指针BSTNode<T>* _left;		//右孩子节点的指针T _data;			//当前节点的值
};

2.2 二叉搜索树的结构

二叉搜索树的具体操作是被设为公开的，根节点是被设为私有的，只能在类内才能访问。

template<class T>
//搜索二叉树
class BSTree
{typedef BSTNode<T> Node;	//将节点名字进行重命名
public://....private:Node* _root;			//先存一个根节点的指针，并且为私有
};

2.3 二叉搜索树的查找

方法：从根开始比较查找，比根大的前往右树继续查找，比根小的往左树继续查找。

返回结果：最多查找高度次，找到返回true，没找到返回false。

//查找，找到返回true，没找到返回false
bool Find(const T& value)
{//用一个临时节点储存根Node* cur = _root;//当cur不为空时就继续找while (cur){//当value大于根节点的值，去右树找if (cur->_data < value){cur = cur->_right;}else if (cur->_data > value){//当value小于根节点的值，去左树找cur = cur->_left;}else{//当value等于根节点的值return true;}}//没找到return false;
}

2.4 二叉搜索树的插入

树为空则直接new一个新节点并初始化给根节点

树不为空则寻找要插入的位置后再进行插入

bool Insert(const T& value)
{//当根节点为空时，直接new一个节点并初始化为value并赋给根if (_root == nullptr){_root = new Node(value);return true;}//当根节点不为空时//二叉搜索树有一个特点，右孩子比根节点的值大，左孩子比根节点的值小//创建一个临时变量cur存储当前节点，和一个储存cur上一个节点的临时变量Node* parent = nullptr;Node* cur = _root;//寻找value应该要插入的位置while (cur != nullptr){//当value大于根节点的值，value要插入到cur的右树里面去if (cur->_data < value){parent = cur;cur = cur->_right;}else if(cur->_data > value){parent = cur;cur = cur->_left;}else{//搜索二叉树不允许有相同的值的存在return false;}}//找到要插入的位置后//parent为要插入的节点的父亲，但不确定要插入到父亲的哪个孩子上，所以还要进行比较一下if (parent->_data < value){//插入到右孩子处parent->_right = new Node(value);return true;}else{//插入到左孩子处parent->_left = new Node(value);return true;}
}

2.5 二叉搜索树的删除

首先要查找要删除的值是否在树中，如果不在树中则直接返回false，如果在树中又要分以下四中情况进行讨论。

情况1：要删除的节点没有左右孩子

情况2：要删除的节点只有左孩子

情况3：要删除的节点只有右孩子

情况4：要删除的节点同时有左孩子和右孩子

实际情况下情况1可以和情况2或3进行合并，因此真正的删除操作如下：

处理情况2的方法：储存该节点的值，并将该节点的左孩子给与其父节点，然后删除该节点

处理情况3的方法：储存该节点的值，并将该节点的右孩子给与其父节点，然后删除该节点

处理情况4的方法：先找到该节点右子树中最小的值的节点(最左节点)，然后替换这两个节点的值，将最左节点的右孩子给最左节点的父节点，然后删除最左节点；当然也可以先找到该节点左子树中的最大值的节点(最右节点)，然后进行相似的操作。

//删除
bool Erase(const T& value)
{//先查找当前节点//用一个临时节点储存根，以及一个cur的上一个节点Node* parent = _root;Node* cur = _root;//当cur不为空时就继续找while (cur){//当value大于根节点的值，去右树找if (cur->_data < value){parent = cur;cur = cur->_right;}else if (cur->_data > value){//当value小于根节点的值，去左树找parent = cur;cur = cur->_left;}else{//当value等于根节点的值，找到了break;}}//若要删除的节点不在当前树中if (cur == nullptr){return false;}//找到了要删除的节点，又要分三种情况//情况1：当前节点既有左孩子也有右孩子，当然也有可能是根节点if (cur->_right != nullptr && cur->_left != nullptr){//处理方法：先找到右树的最左节点，然后用替换法进行删除parent = cur;Node* subLeft = cur->_right;while (subLeft->_left != nullptr){parent = subLeft;subLeft = subLeft->_left;}//交换cur和最左节点std::swap(subLeft->_data, cur->_data);if (subLeft == parent->_left){parent->_left = subLeft->_right;}else{parent->_right = subLeft->_right;}delete subLeft;return true;}else if(cur->_right==nullptr&&cur->_left!=nullptr){//情况2：当前节点只有左孩子，没有右孩子//处理办法：删除当前节点并把该节点的左孩子给父亲的左孩子if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else{//情况3：当前节点只有右孩子或一个孩子也没有//处理办法：删除当前节点并把该节点的右孩子给父亲的右孩子if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;return true;}return false;
}

2.6 二叉搜索树的遍历

二叉搜索树中序遍历的结果必定是有序的。

public:	void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node*& root){//结束条件：当当前节点为空时返回if (root == nullptr){return;}//中序遍历是左根右_InOrder(root->_left);cout << root->_data << " ";_InOrder(root->_right);}

3.二叉搜索树的应用

3.1 K模型：K模型只有key作为关键码，结构中只需要存key即可，关键码即为需要搜索到的值。

比如：给一个单词，判断该单词是否拼写正确，具体方法如下：

以词库中所有单词作为key构建一棵二叉搜索树，在二叉搜索树查找该单词是否存在，存在则拼写正确，不存在则拼写错误。

3.2 KV模型：每一个关键码key都有一个与之对应的值value，即<Key，Value>的键值对。

比如英汉词典就是中文和英文对应关系，通过英文就可以快速找到对应的中文，英文单词和其对应的中文<word，chinese>就构成一对键值对。

再比如统计单词次数，统计成功后，给定单词就可以快速找到其出现的次数，单词与其出现的次数就是<word，count>构成一对键值对。

4.二叉搜索树的性能分析

插入和删除前必须先查找，查找效率就代表了二叉树各个操作的具体性能。

对于一个有n个节点的二叉搜索树，关键码插入的顺序不同可能会导致不同结构的二叉搜索树：