栈、队列、树.pptVIP

栈 ( Stack ) 只允许在一端插入和删除的顺序表 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 (LIFO) 队列 ( Queue ) 定义 队列是只允许在一端删除，在另一端插入的顺序表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First Out) 结点(node) 结点的度(degree) 分支(branch)结点 叶(leaf)结点 子女(child)结点 双亲(parent)结点 兄弟(sibling)结点 祖先(ancestor)结点 子孙(descendant)结点 结点所处层次(level) 树的高度(depth) 树的度(degree) 二叉树遍历 (Binary Tree Traversal) 所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV 中序遍历 (Inorder Traversal) 中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (V)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f 前序遍历 (Preorder Traversal) 前序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 访问根结点 (V)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f 后序遍历 (Postorder Traversal) 后序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。 遍历结果 a b c d - * + e f / - * * 进栈示例 退栈示例 队列的进队和出队 进队时队尾指针先进一 rear = rear + 1，再将新 元素按 rear 指示位置加入。 出队时队头指针先进一 front = front + 1，再将 下标为 front 的元素取出。 队满时再进队将溢出出错；队空时再出队将队 空处理。 树的概念 树的定义 树是由n (n ? 0)个结点组成的有限集合。如果n = 0，称为空树；如果n 0，则 ? 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； ? 除根以外的其它结点划分为m (m ? 0)个互不相交的有限集合T0, T1, …, Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 表达式语法树