第3章堆栈队列二叉树.ppt

队列 不存在物理的循环结构，用软件方法实现。 求模：（4＋1）mod 5＝0 队列的顺序存储结构及实现 如何实现循环队列？ 0 1 2 3 4 入队 出队 a3 a4 front rear a6 队列 如何判断循环队列队空？ 队空的临界状态 队列的顺序存储结构及实现 0 1 2 3 4 入队 出队 a3 rear front 队列 如何判断循环队列队空？ 执行出队操作 队空：front=rear 队列的顺序存储结构及实现 0 1 2 3 4 入队 出队 a3 front rear front 队列 如何判断循环队列队满？ 队满的临界状态 队列的顺序存储结构及实现 0 1 2 3 4 入队 出队 a3 a4 front a5 rear a6 队列 如何判断循环队列队满？ 执行入队操作 队满：front=rear 队列的顺序存储结构及实现 0 1 2 3 4 入队 出队 a3 a4 front a5 rear a6 rear a7 队列 方法一：附设一个存储队列中元素个数的变量num，当num=0时队空，当num=QueueSize时为队满； 方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元； 方法三： 如何确定不同的队空、队满的判定条件？ 为什么要将队空和队满的判定条件分开？ 队列的顺序存储结构及实现 队列 循 环 队 列 类 的 声 明 const int QueueSize=100; template class T class CirQueue { public: CirQueue( )； ~ CirQueue( )； void EnQueue(T x); T DeQueue( ); T GetQueue( ); bool Empty( )； private: T data[QueueSize]; int front, rear; }; 队列 template class T void CirQueue::EnQueue(T x) { if ((rear+1) % QueueSize ==front) throw 上溢; rear=(rear+1) % QueueSize; data[rear]=x; } 循环队列的实现——入队 0 1 2 3 4 入队 出队 a3 a4 rear front a5 rear 队列 0 1 2 3 4 入队 a4 a5 a6 出队 template class T T CirQueue::DeQueue( ) { if (rear==front) throw 下溢; front=(front+1) % QueueSize; return data[front]; } 循环队列的实现——出队 front rear front a3 队列 template class T T CirQueue::GetQueue( ) { if (rear==front) throw 下溢; i=(front+1) % QueueSize; return data[i]; } 循环队列的实现——读队头元素 0 1 2 3 4 入队 a4 a5 a6 出队 front rear a3 i 树 树的基本概念和术语 二叉树的基本概念和性质 二叉树的存储结构和各种遍历算法 树的基本概念 什么是树？什么是子树、树根？树的深度？ 什么是结点、双亲结点、孩子结点、 结点的度、兄弟、祖先和子孙？ 树的定义 树(Tree)是由一个或多个结点组成的有限集合T。其中： （1）有一个特定的结点，称为该树的根（root）结点； （2）根结点之外的其余结点可分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm，且其中每一个集合本身又是一棵树，称之为根的子树（Sub Tree）。 这是递归定义。仅有一个根结