数据结构与算法 c语言，是用栈建立二叉树，其中flag 1和flag 0是什么意思？？？

来源：蜘蛛抓取(WebSpider) 时间：2016-05-16 00:37 标签： 数据结构与算法 c语言

上一篇详解了二叉树转双向链表，此篇作为【C语言强化】系列第二篇，来聊聊有关栈的一道题，

通过这道题，你可以掌握

  • 如何使用栈“先进后出"的特性
  • 如何在结构体中定义可共享的静态成员变量

看似很简单的求最小值函数，思路有很多很多。笔者首先想到每次push入栈都进行一次排序，使这个栈的栈顶永远是最小元素，然后就发现这是一个很蠢很蠢的想法，第一这样做会改变了栈的结构，第二不满足题目对时间复杂度的要求。

愚蠢归愚蠢，还是有点用的。既然不能改变原来栈的结构，那为何不弄俩栈呢？辅助栈的想法由此而出。

接下来是时间复杂度的问题，显然每次都进行排序是不可行的了，那么是否可以记录保存每个最小值的下一个最小值呢，也就是说，当我当前这个最小值被pop出去后，我要知道下一个最小值是哪个。这时栈的【先进后出】特性就派上用场了。

头脑风暴到此结束。下面是具体思路

牢牢把握住栈【先进后出】的特性，模拟各种实际情况，得出算法

栈结构体中添加一个辅助栈，这里称为【最小值栈】，存储最小值的历史记录，所以该最小值栈的栈顶即为当前栈的最小元素

当push进来的元素值大于、等于最小值栈的栈顶，最小值栈不变，因为根据栈的特性，只有当前最小值元素上面的所有元素都出去的时候，该最小值元素才能pop出去，否则该最小值元素用于是最小值。
反之，当push进来的元素值小于最小值栈的栈顶，则将该元素放进最小值栈。

当pop出去的元素不是最小值栈栈顶，则最小值栈不变
如果pop出去的值为当前最小值，则最小值栈也pop出一个元素，此时最小值栈的栈顶就是下一个最小值元素

定义栈的数据结构 要求添加一个min函数，找出栈的最小元素 牢牢把握住栈【先进后出】的特性，模拟各种实际情况，得出算法 栈结构体中添加一个辅助栈，这里称为【最小值栈】，存储最小值的历史记录 所以该最小值栈的栈顶即为当前栈的最小元素 当push进来的元素值大于、等于最小值栈的栈顶，最小值栈不变 因为根据栈的特性，只有当前最小值元素上面的所有元素都出去的时候，该最小值元素才能pop出去 反之，则将该元素放进最小值栈 当pop出去的元素不是最小值栈栈顶，则最小值栈不变 反之，最小值栈pop出栈顶 这样如果pop出去的值为当前最小值，则最小值栈也pop出一个元素 此时最小值栈的栈顶就是下一个最小值元素 pop2() 出栈并且求最小值 //push进来的值小于等于原来的最小值，则push进入最小值栈 //非空且pop的值等于最小值，则最小值栈pop //结构体静态变量初始化！

总结，所有与栈有关的题目，都记住这四个字——”先进后出“

 二叉树是数据结构中一种非常重要的结构，熟练的掌握二叉树的创建，遍历是打好编程基础的关键。对于遍历，不能仅仅只掌握递归遍历，还应掌握效率更高地非递归遍历。对于非递归的先序、中序、后序遍历要用到栈(在之前的博文中已经提到了具体的实现过程)，而在层次遍历中要使用到另一种数据结构——队列，这个在之前博文中没有提到，因此在本篇博文中将会给出简单实现。

         在本篇博文中给出的代码实现了：二叉树的创建、二叉树的递归、非递归的先、中、后序以及层次遍历七种遍历算法。话不多说，下面给出代码(仅供参考)：

//定义栈中数据的类型 //定义二叉树中存储的数据类型 //初始化一棵仅含根节点的二叉树,根节点的值为e //初始化一棵仅含根节点的二叉树,根节点的值为e //把根节点指针赋值给p //打印当前节点，其左节点依次进栈 //把根节点指针赋值给p //存储最近一次访问的节点 //如果不存在右子树，或右子树被访问 解析一下：根据上面的while循环，栈顶元素必然不存在左子树；如何存在右子树，又根据后序遍历的特点， 最近一次被访问的节点，必然是该节点的右子树

与大家分享，共同学习，相互提高，如有疑问或建议，请留言。

内容提示：严蔚敏《数据结构(c语言版)习题集》答案第六章 树和二叉树文库

文档格式：DOC| 浏览次数：72| 上传日期： 08:54:34| 文档星级：?????

我要回帖

更多关于 数据结构与算法 c语言 的文章

 

随机推荐