文档介绍：
■、基本概念：
?数据（Data）:信息的载体，能够被计算机识别、存储和加工处理的物理符号。
包括文本类型的数据（如：字母、数字、汉字）和多媒体类型的数据（如：声音、动画、图像）。
?数据元素（DataEleme删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。当表中没有元素时称为空栈。是一种后进先出的线性表，又称为LIFO表。
?栈的基本运算有：
栈的初始化、判栈空、判栈满、进栈、出栈等
?栈的存储:
顺序存储、链式存储
例：若进栈的输入序列是A、B、C、D、E,并且在它们进栈的过程中可以
进行出栈操作，则不可能出现的出栈序列是（）
A、EDCBAB、DECBAC、DCEABD、ABCDE
四、队列：
?队列（Queue）:也是一种运算受限的线性表，它只允许在表的一端进行插入，
而在另一端进行删除。允许删除的一段称为队头（Front）,允许插入的一段称为队尾（Rear）。（类似于生活中的购物排队）。是一种先进先出的线性表，又称为FIFO表。
?队列的基本运算：
队列的初始化、判队空、判队满、入队、出队
?队列的存储实现：
顺序存储、链式存储
例：一个队列的入队序列是1,2,3,4,则队列的输出序列是（）
A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,
4,1
五、工
?用（String）:是零个或多个字符组成的有限序列。
用中所包含的字符个数称为该用的长度。
审中任意个连续字符组成的子序列称为该用的子用，包含子用的用相应地称为主用
注：空用是任意用的子用，任意用是其自身的子用
?用有用常量、用变量之分：
1、用常量在程序中只能被引用但不能改变其值，即只能读不能写。
2、用变量其值是可以改变的。
?用的基本运算：
求用长、申复制、串联接、用比较、字符定位、
六、树(非线性结构)：
?树(Tree):是n(n>=0)个结点的有限集「T(n=0)为空时称为空树，否则它满足如下两个条件：
1、有且仅有一个特定的称为根(Root)的结点
2、其余的结点可分为m(m>=0)个互不相交的子集T1,T2,……Tm,其中每个子集本身又是一棵树，并称其为根的子树(Subtree)。
?在树的树形图表示中，结点通常是用圆圈表示的，结点的名字一般是写在圆圈旁边，有时亦可写在圆圈内。
?度(Degree):一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的最大度数。
?叶子(Leaf):度为零的结点称为叶子或终端结点
?分支结点(Node):度不为零的结点称为分支结点。
?树中某个结点的子树之根称为该结点的孩子(Child)结点或子结点，相应的该结点称为孩子结点的双亲(Parents)结点或父结点。
?同一个双亲的孩子称为兄弟结点(Sibling)
?结点的层数(Level)是从根起算，设根的层数为1,其余结点的层数等于其双亲结点的层数加1.
?树中结点的最大层数称为树的高度(Height)或深度(Depth).
?森林(Forest):是m(m>=0)棵互不相交的树的集合。删去一棵树的根，就得到一个森林，反之，加上一个结点作树根，森林就变为一棵树。
?二叉树(BinaryTree):是n(n>=0)个结点的有限集，它或者是空集(n=0),或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的
XXXXXX
二叉树组成。
二叉树中，每个结点最多只能有两棵子树，并且有左右之分。
?二叉树的五种基本形态：
例：具有3个结点的二叉树有几种形态。
?满二叉树(FullBinaryTree)：一棵深度为k且有2k-1个结点的二叉树称为满二叉树
?完全二叉树(CompleteBinaryTree):若一棵二叉树至多只有最下面的两层上结点的度数可以小于2,并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
二叉树的性质：性质1:二叉树第i层上的结点数目最多为2i-1(i>=1)
性质2:深度为k的二叉树至多有2k-1个结点（k>=1）
性质3:在任意一棵二叉树中，若终端结点的个数为no,度为2的结点数为n2,
贝Uno=n2+1
性质4：具有n个结点的完全二叉树的深度为3g2[1]+1（取下整）或【1n2〔】1一！）]（取上整）。
例：一棵二叉树的结点数为18个，求它的最小高度
已知度为2的结点数为15个，求叶子结点数15
二叉树的遍历：
?遍历（Traversal）:是指沿着某条搜索路线，依次对树中每个结点均做一次且
仅做一次访问。
（又称为先序遍历'
先根遍历' ）
前序遍历
层序遍历：42 5136
前序遍历:42X