第4章 栈与队列
第5章 串
第6章 树
第4章 栈与队列
栈是限定仅在表尾进行插入和删除操作的线性表。
队列是只允许在一段进行插入操作、而在另一端进行删除操作的线性表。
栈
把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表。
队列
队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。
第5章 串
串：串是由零个或多个字符组成的有限序列，又名叫字符串。
第6章 树
树是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（root）的结点；（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、Tn,其中每一个集合本身又是一棵树，并且称为根的子树（subtree）
二叉树的定义
二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两颗互不相交的、分别称为跟节点的左子树和右子树的二叉树组成。
二叉树特定
- 每个节点最多有两棵子树，所以二叉树中不存在度大于2的节点。
- 左子树和右子树是有顺序的，次序不能任意颠倒。
- 即使树种某节点只有一棵子树，也有区分它是左子树还是右子树。
特殊二叉树
斜树
所有的节点都只有左子树的二叉树叫左斜树。所有节点都是只有右子树的二叉树叫右斜树。
满二叉树
在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
完全二叉树
对一棵具有n个结点的二叉树俺层序编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这课二叉树称为完全二叉树。
二叉树的性质
- 性质1：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。
- 性质2：深度为K的二叉树至多有2^(k)-1个结点(K>=1)。
- 性质3: 对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1.
- 性质4：具有n个结点的完全二叉树的深度为[Log2n]+1([x]表示不大于x的最大整数)。
二叉树的存储结构
二叉树顺序存储结构
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。
二叉链表
二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法。称这样的链表叫做二叉链表。
遍历二叉树
二叉树遍历原理
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
两个关键词：访问和次序。
二叉树的遍历方法
前序遍历
规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
中序遍历
规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
后续遍历
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。
层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
