二叉树细分了两种类型的二叉树，一种叫做“满二叉树”，就是每一层都挂满了节点，没有空位。另一种叫做“完全二叉树”，完全二叉树假设有n层，那么n-1层和满二叉树是一样的，但是第n层最后一个节点前边都挂满了节点。这是它们两个概念的唯一具体区别。表示图如下： 【满二叉树】 【完全二叉树】 上面的树符合最后一个节点（F...

在搞清楚多叉树转换为二叉树之前，我们有必要想清楚，为什么要这样转换？多叉树哪里有缺点需要我们转换为二叉树使用？我们来考虑一个问题：“如果我们将一个多叉树存放在一个数组中，然后删除了整个多叉树。我们能否通过这个仅有的数组恢复原来的多叉树呢？” 答案是不能的，如下图： 我们可以将一个多叉树，按顺序写入到一个一维的...

树是一种较为复杂的数据结构，人们这样定义它：“由一个或多个(n>=0)节点组成的有限集合T，有且只有一个’根’节点（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。”我们首先来看一下我们对其逻辑结构的表示...

队列是一种先进先出的数据模型，它的应用场景比较常见，比如日常生活中我们打10086的电话需要排队时、吃饭排号时的小票、Windows GUI程序的消息队列等等都是基于队列实现的。先进入队列的也是先从队列出去的。他的模型如下： 【顺序线性表实现队列】 顺序线性表可以实现队列的模型，线性表中哪一端作为队头或者队尾...

以前我们使用自己封装的栈模型探讨并实现了后缀表达式的运算，“计算机是如何基于后缀表达式计算的”，在 C++ 的 STL 中，也有一个栈模型 stack，并且使用了模版类，这样可以让我们更方便的操作数据了，下面的代码就是使用 STL 的 stack 模型实现的后缀表达式运算，我们只是把自己实现的栈模型函数替换成了 ...

前一篇文章我们讨论了计算机是如何将中缀表达式转换为后缀表达式的，那么转换后到底计算机是如何计算的呢？本文就来讨论这个主要话题。我们首先来看一下其计算的规则： 【计算规则】 遍历后缀表达式中的数字和符号对于数字：进栈对于符号：从栈中弹出右操作数从栈中弹出左操作数根据符号进行运算将运算结果压入栈中遍历结束：栈中的唯...

后缀表达式，由波兰科学家在20世纪50年代提出，将运算符放在数字后面，更便于计算机去计算，而我们平常看到的 1 + 2、5 * 10 等，都是中缀表达式，这种方式，符合人类的思考方式。举几个例子： 5 + 4 => 5 4 + 1 + 2 * 3 => 1 2 3 * + 8 ...

你在使用编辑器写代码的时候是否思考过这个问题：如果少写了一个大括号或中括号，编辑器就会提示错误，这种做法是怎么做到的呢？ 其实这个检测就可以通过栈模型来实现，括号的数量总是匹配出现的，并且都是与最近的一个匹配。我们可以编写代码来实现这个检测的功能。具体实现思路如下： 从第一个字符开始扫描, 当遇见普通字符时忽略，...

栈模型使用顺序存储的方式就相当于在数组上进行操作，而本文介绍的则是通过链式存储来实现栈的模型，那么我们就要思考一个问题了。栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？ 由于单链表有头指针，而栈顶指针也是必须的，那干嘛不让他俩合二为一呢，所以比较好的办法就是把栈顶放在单链表的头部（如下图）。另外都...

栈（Stack）也是数据存储的一种方式，我们可以将其理解为一种线性的表，只不过他是前去后继的关系，他只能在线性表的尾部插入和取出数据，这个尾部所指的就是栈的栈顶，而最先被存入的数据则是栈底。它具有后进先出、先进后出的特性。表示图如下： 【代码实现】下面代码中，使用顺序线性表实现了一个栈模型，与上图非常类似。具...