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