文档介绍：数据结构基础讲义
第一页，共45页。
1 概要
2 线性表
3 栈和队列
4 树和二叉树
5 查找和排序
主要内容
第二页，共45页。
讨论的范畴
算法+数据结构 = 程序设计
处理问题的策略
给出第二十页，共45页。
编程实战
队列的链式存储
第二十一页，共45页。
Q1. 假设以带头结点的循环链表表示队列，并又只设一个指针指向队尾元音结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。
Q2. 假设称正读和反读都相同的字符序列为“回文”，例如，”aba”和”abcba”是回文，”abcde”和”ababab”则不是回文。试写一个算法判别读入的一个以“@”为结束符的字符序列是否是“回文”。
第2天 习题
第二十二页，共45页。
树的定义
定义：
- 由一个或多个结点组成的有限集合T，有且仅有一个结点称为根，其余的结点分为m个互不相交的有限集合T1, T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。
树的特点：
非线性结构，有一个直接前驱，但可能有多个直接后继（1:n）
树的定义具有递归性，树中还有树
树可以为空，即节点个数为0
第二十三页，共45页。
树的术语
专业术语
含义
根
也叫根结点(没有前驱)
叶子
也叫终端结点(没有后继)
森林
指m棵不相交的树的集合(例如删除A后的子树个数)
有序树
结点各子树从左至右有序，不能互换（左为第一）
无序树
结点各子树可互换位置
双亲
即上层的那个结点(直接前驱) parent
孩子
即下层结点的子树 (直接后继) child
兄弟
同一双亲下的同层结点（孩子之间互称兄弟）sibling
堂兄弟
即双亲位于同一层的结点（但并非同一双亲）cousin
祖先
即从根到该结点所经分支的所有结点
子孙
即该结点下层子树中的任一结点
结点
也叫节点，即树的数据元素
结点的度、树的度
结点挂接的子树数、所有结点度中的最大值
结点的层次
从根到该结点的层数（根结点算第一层）
终端结点
即度为0的结点，即叶子
分支结点
除树根以外的结点（也称为内部结点）
树的深度(或高度)
指所有结点中最大的层数(从根节点到最低层的结点层数)
第二十四页，共45页。
树的表示法
第二十五页，共45页。
树的表示法
第二十六页，共45页。
二叉树的概念
二叉树由一个根结点加上两棵分别称为左子树和右子树的互不相交的树组成：
每个结点最多只有两棵子树（不存在度大于2的结点）
左子树和右子树次序不能颠倒（有序树）
第二十七页，共45页。
树转化为二叉树
左孩子右兄弟表示法可以将一颗多叉树转化为一颗二叉树。
第二十八页，共45页。
满二叉树和完全二叉树
第二十九页，共45页。
树的顺序存储
多叉树顺序存储的缺陷
第三十页，共45页。
完全二叉树的顺序存储
非完全二叉树存储缺点：
①浪费空间；②插入、删除不便
完全二叉树存储
第三十一页，共45页。
二叉树的链式存储
二叉链存储
第三十二页，共45页。
二叉树的链式存储
三叉链存储
第三十三页，共45页。
二叉树的遍历
遍历是指按某条搜索路线遍访每个结点且不重复（又称周游），遍历是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。
牢记一种约定，对每个结点的查看都是“先左后右”。
遍历方式
特点
先序遍历(先根遍历，DLR)
根 -> 左子树 -> 右子树
中序遍历(中根遍历，LDR)
左子树 -> 根 -> 右子树
后序遍历(后根遍历，LRD)
左子树 -> 右子树 -> 根
第三十四页，共45页。
二叉树的遍历
第三十五页，共45页。
编程实战
二叉树的动态创建和释放
二叉树的递归遍历
计算二叉树叶子节点数目
计算二叉树高度
第三十六页，共45页。
第3天 习题
Q1 编写递归算法，在二叉树中求位于先序序列中第A个位置的结点的值。
Q2 编写递归算法，计算二又树中叶子结点的数目。
Q3 编写递归算法，将二叉树中所有结点的左、右子树相互交换。
第三十七页，共45页。
查找的概念
根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，若表中存在这样的一个记录，则称查找是成功的。
第三十八页，共45页。
编程实战
顺序查找
二分查找
第三十九页，共45页。