dede电影网站模版,视频转链接在线生成,个人网站怎么做的模板,网站建设专业导航网站快乐的流畅#xff1a;个人主页 个人专栏#xff1a;《C语言》《数据结构世界》《进击的C》 远方有一堆篝火#xff0c;在为久候之人燃烧#xff01; 文章目录 引言一、二叉搜索树介绍二、二叉搜索树的模拟实现2.1 结点2.2 成员变量2.3 默认成员函数2.3.1 constructor2.3.2… 快乐的流畅个人主页 个人专栏《C语言》《数据结构世界》《进击的C》 远方有一堆篝火在为久候之人燃烧 文章目录 引言一、二叉搜索树介绍二、二叉搜索树的模拟实现2.1 结点2.2 成员变量2.3 默认成员函数2.3.1 constructor2.3.2 copy constructor2.3.3 operator2.3.4 destructor 2.4 中序遍历2.5 查找2.5.1 迭代实现2.5.2 递归实现 2.6 插入2.6.1 迭代实现2.6.2 递归实现 2.7 删除2.7.1 迭代实现2.7.2 递归实现 三、二叉搜索树的应用四、二叉树进阶面试题 引言
二叉树在之前的数据结构章节讲解过当时使用C来实现。而如今学习的二叉搜索树便是二叉树的进阶也更适合使用C来实现。
一、二叉搜索树介绍
二叉搜索树BSTBinary Search Tree又称为二叉排序树。
它满足以下性质
非空左子树的所有键值小于其根结点的键值非空右子树的所有键值大于其根结点的键值左右子树均为二叉搜索树 二、二叉搜索树的模拟实现
2.1 结点
templateclass K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key): _left(nullptr), _right(nullptr), _key(key){}
};细节在二叉搜索树中一般更喜欢用K作为模板参数用key作为数据称为键值。
2.2 成员变量
templateclass K
class BSTree
{typedef BSTreeNodeK Node;
protected:Node* _root nullptr;
};2.3 默认成员函数
2.3.1 constructor
//写法一
BSTree(): _root(nullptr)
{}
//写法二
BSTree() default;//强制生产默认构造2.3.2 copy constructor
BSTree(const BSTreeK t)
{_root Copy(t._root);
}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;
}细节写一个子函数Copy进行前序遍历递归拷贝
2.3.3 operator
BSTreeK operator(BSTreeK t)
{swap(_root, t._root);return *this;
}细节现代写法直接拷贝完交换
2.3.4 destructor
~BSTree()
{Destroy(_root);
}void Destroy(Node* root)
{if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;
}细节
写一个子函数Destroy进行后序遍历递归释放参数为Node*这样就可以在函数内置空根节点
2.4 中序遍历
为什么只介绍中序遍历呢二叉搜索树之所以又称为二叉排序树是因为在中序遍历时便能将数据按升序遍历。
void InOrder()
{_InOrder(_root);cout endl;
}void _InOrder(Node* root)
{if (root nullptr){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);
}细节同样一般要递归写一个子函数再进行传参控制
2.5 查找
二叉搜索树其最大优势肯定是在于搜索
2.5.1 迭代实现
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;
}细节
查找的key比当前结点的_key大则往右查找查找的key比当前结点的_key小则往左查找找到返回true走到空找不到返回false
2.5.2 递归实现
bool FindR(const K key)
{return _FindR(_root, key);
}bool _FindR(Node* root, const K key)
{if (root nullptr){return false;}if (root-_key key){return _FindR(root-_right, key);}else if (root-_key key){return _FindR(root-_left, key);}else{return true;}
}2.6 插入
2.6.1 迭代实现
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;
}细节
若根为空直接创建结点返回true设置parent变量记录父节点以便在cur走到空时进行插入插入前要判断用左指针还是右指针链接
2.6.2 递归实现
bool InsertR(const K key)
{return _InsertR(_root, key);
}bool _InsertR(Node* root, const K key)
{if (root nullptr){root new Node(key);return true;}if (root-_key key){return _InsertR(root-_right, key);}else if (root-_key key){return _InsertR(root-_left, key);}else{return false;}
}细节参数为Node*使得当前root为空却可以直接创建节点链接因为此时root是其父节点左右指针的引用
2.7 删除
2.7.1 迭代实现
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-_right nullptr)//右子树为空{if (cur _root){_root _root-_left;}else{if (parent-_right cur){parent-_right cur-_left;}else{parent-_left cur-_left;}}delete cur;}else if (cur-_left nullptr)//左子树为空{if (cur _root){_root _root-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else//左右子树均不为空{//这里选择找右子树的最左节点Node* pminRight cur;Node* minRight cur-_right;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;if (pminRight-_right minRight){pminRight-_right minRight-_right;}else{pminRight-_left minRight-_right;}delete minRight;}return true;}}return false;
}细节
首先依然要parent记录父节点进行查找找到了分三种删除情况 右子树为空左子树为空左右子树均不为空 左右子树一边为空时先判断parent是否为空如果为空代表cur为_root需要移动_root如果不为空则再判断左右指针链接左右子树均不为空时寻找右子树的最左结点minRight也可以是左子树的最右结点来替代cur注意minRight可能有孩子还要设置pminRight记录其父节点位置判断左右指针链接
2.7.2 递归实现
bool EraseR(const K key)
{return _EraseR(_root, key);
}bool _EraseR(Node* root, const K key)
{if (root nullptr){return false;}if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Node* del root;if (root-_right nullptr)//右子树为空{root root-_left;}else if (root-_left nullptr)//左子树为空{root root-_right;}else{Node* minRight root-_right;while (minRight-_left){minRight minRight-_left;}swap(root-_key, minRight-_key);return _EraseR(root-_right, key);}delete del;return true;}
}细节
参数为Node*使得左右子树一边为空时不用判断直接链接将两种情况一并处理了左右子树均不为空时交换待删除root和minRight的键值key再递归其右子树删除
三、二叉搜索树的应用
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。
比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。
四、二叉树进阶面试题
二叉树进阶面试题
一、根据二叉树创建字符串 二、二叉树的层序遍历 三、二叉树的最近公共祖先 四、二叉搜索树转换双向链表 五、构造二叉树 5.1 前序与中序 5.2 中序与后序 六、二叉树的前中后序遍历非递归 6.1 前序 6.2 中序 6.3 后序 真诚点赞手有余香
