C++进阶（3）二叉树进阶

1.内容安排说明二叉树在前面C数据结构阶段已经讲过。本节取名二叉树进阶是因为map和set特性需要先铺垫二叉搜索树而二叉搜索树也是一种树形结构。二叉搜索树的特性了解有助于更好的理解map和set的特性。二叉树中部分面试题稍微有点难度在前面讲解大家不容易接受且时间长容易忘。有些OJ题使用C语言方式实现比较麻烦比如有些地方要返回动态开辟的二维数组非常麻烦。因此本节借二叉树搜索树对二叉树部分进行收尾总结。2.二叉搜索树普通二叉树没什么特别大的意义二叉树结构比链表、顺序表复杂遍历起来也不方便单独只用来存储数据没什么意义不如直接使用链表、顺序表。所以二叉树的应用是需要在普通二叉树的基础上加一些“特殊的性质”形成特殊的数据结构才好用堆优先级队列的性质方便排序。搜索二叉树的性质主要是方便查找、附带有方便排序。……2.1二叉搜索树概念【二叉搜索树】定义又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树。性质若它的左子树不为空则左子树上所有节点的值都小于根节点的值。若它的右子树不为空则右子树上所有节点的值都大于根节点的值。它的左右子树也分别为二叉搜索树。2.2二叉搜索树操作搜索二叉树也称排序二叉树因为它的中序遍历就是有序升序。int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};1查找搜索1. 二叉搜索树的查找a、从根开始比较查找——比根大则往右边走查找比根小则往左边走查找。b、最多查找高度次走到到空还没找到这个值不存在。使用递归或者循环来实现。普通二叉树的查找只能暴力查找——O(N);搜索二叉树的查找相当于折半查找——O(logN);查找算法第2种方式的缺点排序的消耗。只需要排一次之后就可以一直二分查找排序消耗不算主要缺点仅对现有数据查找还好一旦涉及插入、删除数据效率就很低了。在内存中进行数据搜索AVL树和红黑树就足够了。在磁盘中进行海量数据的搜索使用AVL树和红黑树就会有很高的层高就需要压缩就出现了多叉平衡搜索树——M阶B树系列。再有一个就是hash——一种思想。哈希系列哈希表、跳表、布隆过滤器……2插入2. 二叉搜索树的插入插入的具体过程如下a.树为空则直接新增节点赋值给root指针b.树不空按二叉搜索树性质查找插入位置插入新节点一般情况下搜索二叉树不允许数据冗余——插入之前先查找搜索二叉树里面有没有这个值没有再插入。可以设置一个bool返回值当不存在数据冗余就直接插入返回1表示插入成功反之插入失败。3删除3. 二叉搜索树的删除首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情况a.要删除的结点无孩子结点b.要删除的结点只有左孩子结点c.要删除的结点只有右孩子结点d.要删除的结点有左、右孩子结点看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题--替换法删除2.3二叉搜索树的实现二叉树类结点类1查找漏了一个public:2插入测试3排序中序遍历需要给一个参数——根结点但是类外无法访问私有。可以写一个getroot()函数获取私有成员也可以把上述函数写成子函数。缺省值只能用常量和全局变量。【搜索二叉树的功能】查找数据去重冗余数据不插入排序 排序去重后的数据实际上是排序去重数据去重演示set的底层就是搜索二叉树所以set也具有这些功能。但不完全是搜索二叉树。搜索二叉树查找一个值的时间复杂度是高度次但并不是O(logN)。在极端情况下搜索二叉树查找效率会掉到O(N)平衡二叉搜索树的形状接近与完全二叉树或满二叉树高度接近logN。搜索二叉树默认情况下不支持修改——把某个节点从3改成13不支持或者以及之类的操作。但是搜索二叉树的变种支持修改不提供修改方面的接口。也能变种来支持数据冗余。4删除首先查找元素是否在二叉搜索树中如果不存在则返回0。否则要删除的结点可能分下面四种情况a.要删除的结点无孩子结点b.要删除的结点只有左孩子结点c.要删除的结点只有右孩子结点d.要删除的结点有左、右孩子结点看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下情况b删除该结点并使被删除节点的父结点指向被删除节点的左孩子结点--直接删除情况c删除该结点并使被删除节点的父结点指向被删除结点的右孩子结点--直接删除情况d在它的右子树中寻找中序下的第一个结点关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题--替换法删除6、14都只有一个孩子可以直接进行托孤。但是删除3——3有2个孩子得找一个合适的放过来——左子树最大 or 右子树最小。【合适】比左子树大比右子树小。一棵搜索二叉树的最小值最左边那个结点最大值最右边那个结点左子树的最大值——左子树中最右边那个结点。右子树的最小值——右子树中最左边那个结点。最左、最右看垂直竖线来划分。用4替代3之后需要删除原4结点——一定满足情况b或者情况c即一定能直接托孤直接删除注意根结点的删除要单独处理注意节点删除的时候托孤是给托给父结点的左还是右习惯上定义指针的时候都初始化成nullptr但是这里有可能右子树的最小结点就是右子树的根结点此时rightMinP初始化为nullptr而不是cur的话程序执行过程中访问rightMinP-_left就会崩溃。删节点之前先纠正链接关系让待删结点成为孤立结点之后再放心地delate它。代码测试二叉树的销毁需要把每个结点都销毁。templateclass T struct BSTNode { BSTNode(const T data T()) : _pLeft(nullptr) , _pRight(nullptr), _data(data) {} BSTNodeT* _pLeft; BSTNodeT* _pRight; T _data; }; templateclass T class BSTree { typedef BSTNodeT Node; typedef Node* PNode; public: BSTree(): _pRoot(nullptr) {} // 同学们自己实现与二叉树的销毁类似 ~BSTree(); // 根据二叉搜索树的性质查找找到值为data的节点在二叉搜索树中的位置 PNode Find(const T data); bool Insert(const T data) { // 如果树为空直接插入 if (nullptr _pRoot) { _pRoot new Node(data); return true; } // 按照二叉搜索树的性质查找data在树中的插入位置 PNode pCur _pRoot; // 记录pCur的双亲因为新元素最终插入在pCur双亲左右孩子的位置 PNode pParent nullptr; while (pCur) { pParent pCur; if (data pCur-_data) pCur pCur-_pLeft; else if (data pCur-_data) pCur pCur-_pRight; // 元素已经在树中存在 else return false; } // 插入元素 pCur new Node(data); if (data pParent-_data) pParent-_pLeft pCur; else pParent-_pRight pCur; return true; } bool Erase(const T data) { // 如果树为空删除失败 if (nullptr _pRoot) return false; // 查找在data在树中的位置 PNode pCur _pRoot; PNode pParent nullptr; while (pCur) { if (data pCur-_data) break; else if (data pCur-_data) { pParent pCur; pCur pCur-_pLeft; } else { pParent pCur; pCur pCur-_pRight; } } // data不在二叉搜索树中无法删除 if (nullptr pCur) return false; // 分以下情况进行删除同学们自己画图分析完成 if (nullptr pCur-_pRight) { // 当前节点只有左孩子或者左孩子为空---可直接删除 } else if (nullptr pCur-_pRight) { // 当前节点只有右孩子---可直接删除 } else { // 当前节点左右孩子都存在直接删除不好删除可以在其子树中找一个替代结点比如 // 找其左子树中的最大节点即左子树中最右侧的节点或者在其右子树中最小的节点即右子树中最小的节点 // 替代节点找到后将替代节点中的值交给待删除节点转换成删除替代节点 } return true; } // 同学们自己实现 void InOrder(); private: PNode _pRoot; };2.4二叉搜索树的应用1实践当中的两种搜索模型1. K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。比如给一个单词word判断该单词是否拼写正确具体方式如下以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。2. KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。这种方式在现实生活中非常常见比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。2搜索二叉树的key,value改造用命名空间封装之前写好的key模型。再在另一个命名空间中写key,value模型。查找函数之前只需要返回bool值——true、false现在需要返回结点指针删除函数和中序遍历都不需要改变。功能测试ret的类型是一个节点指针通过这个指针可以找到英文对应的中文。这样就实现了一个简单的字典——查找的逻辑还是按英文去查找只不过结果不再是只看在不在而是希望通过查找英文得到它对应的中文。因为英文和中文存在同一个节点内找到那个英文就找到它对应的中文了。while(cinstr)可以通过以下几种方式结束CtrlC杀进程返回码-1073741510程序不是正常结束的。CtrlZ结束输入。cinstr调用的是适配于string的流提取。这个运算符重载函数类型重载函数使得istream类型的对象可以隐式类型转换成bool类型。这个类型重载函数的返回值类型就是operator bool。强制类型转换运算符是()istream类型的对象转换的bool的写法(bool)cin所以理论上应该是operator()返回值是bool。但是operator()给了仿函数让对象能像函数调用一样去使用。类型转换和函数调用使用的是同一个符号——()。所以这里没办法只能写成operator bool。IO流主要有4个标志。operator bool是C11提出的。C98没有operator bool。英汉字典是一个最简单的key,value模型车库收费系统也是一个典型的key,value模型。收费车库在车辆进入时扫描车牌记录车牌及对应的入库时间。出库的时候扫描车牌根据出库时间计算停车时长进而计算出收取的费用扫码支付。这里的key,value模型就是车牌入库时间出库的时候通过车牌去找对应的入库时间。高铁票也是一个和身份证绑定的key,value模型刷身份证就能进站上车。以上都是常规场景以下是不常规的场景。某人写了一本英文小说写完之后希望检查有没有单词拼写错误——这是key模型找在不在只需要词库不需要字典。写完之后希望统计某个单词的出现次数——这是key,value模型。实际使用中不需要自己实现二叉搜索树C的数据结构有现成的二叉搜索树而且是平衡的二叉搜索树比上面实现的普通二叉搜索树效率更高。先学使用再学底层。2.5二叉搜索树的性能分析插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树最优情况下二叉搜索树为完全二叉树或者接近完全二叉树其平均比较次数为log_2_N最差情况下二叉搜索树退化为单支树或者类似单支其平均比较次数为N / 2问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优那么我们后续章节学习的AVL树和红黑树就可以上场了。3.二叉树进阶面试题这些题目更适合使用C完成难度也更大一些1. 二叉树创建字符串。OJ链接2. 二叉树的分层遍历1。OJ链接3. 二叉树的分层遍历2。OJ链接4. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。OJ链接5. 二叉树搜索树转换成排序双向链表。OJ链接6. 根据一棵树的前序遍历与中序遍历构造二叉树。OJ链接7. 根据一棵树的中序遍历与后序遍历构造二叉树。OJ链接8. 二叉树的前序遍历非递归迭代实现 。OJ链接9. 二叉树中序遍历 非递归迭代实现。OJ链接10. 二叉树的后序遍历 非递归迭代实现。OJ链接