树和二叉树树的概念

树和二叉树树的概念

存储结构和运算树和二叉树的性质二叉树的概念第五章二叉树的五种基本形态：空树N只含根结点NL右子树为空NR左子树为空NRL左右子树均不为空树E

ADBCF

rootleftdataright结点结构:二叉链表先（根）序的遍历算法

DLR中（根）序的遍历算法

LDR后（根）序的遍历算法

LRD先右后左的遍历算法

RLDRDLDRLABCGFHEID

A,B,C,D,E,F,G,H,I层次遍历序列:

前序遍历递归算法

voidPreorder(BTreeNode*BT){if(BT!=NULL){cout<<BT->data<<'';//D访问根结点

Preorder(BT->left);//L遍历左子树

Preorder(BT->right);//R遍历右子树

}}由二叉树的先序和中序序列建树先序序列中序序列左子树左子树右子树右子树根根建立二叉树

以字符串的形式定义一棵二叉树

采用广义表表示的输入法定义一棵二叉树ABCDEFGABCEDFGrootABCEDFG

二叉链表(孩子-兄弟）存储树的遍历树的遍历可有三条搜索路径:先根(次序)遍历:后根(次序)遍历:按层次遍历:

ABCDEFGHIJKqGTAGHFEDCBABCDEFGHIJK按层遍历树

二叉树的应用二叉搜索树堆

哈夫曼第六章二叉搜索树的定义1．定义2．查找算法3．插入算法4．删除算法5．查找性能的分析二叉链表作为二叉搜索树的存储结构structBTreeNode{ElemTypedata;

BTreeNode*left;

BTreeNode*right;};“插入”操作在查找不成功时才进行；二叉搜索树的插入算法若二叉搜索树为空树，则新插入的结点为根结点；否则，新插入的结点必为一个叶子结点，其插入位置由查找过程得到。（1）被删除的结点是叶子；（2）被删除的结点只有左子树

或者只有右子树；（3）被删除的结点既有左子树，也有右子树。二叉搜索树的删除算法可分三种情况讨论：（1）被删除的结点是叶子结点其双亲结点相应指针域改为“空”（2）被删除的结点只有单支子树

其双亲结点的相应指针域改为“指向被删除结点的左子树或右子树”。p

右子树为空只需重接它的左子树s=p->left;p->left=q;delete(s);pqs=p->right;p->right=q;delete(s);qp左子树为空只需重接它的右子树ps=p->left;p->left=q;delete(s);s=p->right;p->right=q;delete(s);qq（3）被删除的结点有左右子树被删结点前驱结点以其前驱替代之，然后再删除该前驱结点左子树中“最右下”的结点（左指针可能不为空）

（3）被删除的结点有左右子树以其后继替代之，然后再删除后继结点右子树中“最左下”的结点（左指针可能不为空）堆是满足下列性质的数列{r1,r2,…，rn}：或(小顶堆)(大顶堆)对于完全二叉树r2i

是ri

的左孩子r2i+1

是ri

的右孩子structHeap{ElemTypeheap[HeapMaxSize];intsize;};

//HeapMaxSize事先定义的全局常量堆的顺序存储类型如何“建堆”？两个问题:如何“筛选”？完全二叉树

调整为堆哈夫曼树

最优树的定义如何构造最优树

抽象数据类型图的定义图的存储结构图的遍历dfsbfs最小生成树普里姆克鲁斯卡尔拓扑排序第七章图的存储表示邻接矩阵存储表示图的邻接表存储表示有向图的十字链表存储表示边集数组存储表示Aij={0(i,j)VR1(i,j)VR图的邻接矩阵存储表示矩阵的元素为有向图的邻接矩阵为非对称矩阵有向网的邻接矩阵为非对称矩阵Aij={∞(i,j)VRw(i,j)VR网的邻接矩阵存储表示矩阵的元素为指向下一个有相同弧尾的结点指向下一个有相同弧头的结点有向图的十字链表存储表示

弧的结点结构弧尾位置弧头位置相关信息指向该顶点的第一条入弧指向该顶点的第一条出弧顶点的结点结构顶点信息数据图的遍历

从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索dfs广度优先搜索bfs(连通网的)最小生成树

构造网的一棵最小生成树，即:在

e条带权的边中选取n-1条边（不构回路），使“权值之和”为最小。算法二：（克鲁斯卡尔算法）算法一：（普里姆算法）abcdegf195141827168213ae12dcbgf71485316217121819克鲁斯卡尔算法：abcdegf195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=67普里姆算法G=(V,E)T=(U,TE)

拓扑排序

问题:假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。

检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。对有向图进行如下操作：

按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。第八章查找

对查找的操作：1）查询(检索)某个“特定的”数据元素是否在查找表中及各种属性；2）在查找表中插入一个数据元素；3）从查找表中删去某个数据元素。仅作查询和检索操作的查找表。静态查找表有时还需要将“查询”结果为“不在查找表中”的数据元素插入到表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。动态查找表查找表可分为两类:1.顺序查找2.二分查找3.索引顺序静态查找表

以顺序表或线性链表表示静态查找表顺序查找表

顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。有序查找表

若以有序表表示静态查找表，则查找过程可以基于“折半”进行。索引顺序表的查找过程：1）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。索引可以根据查找表的特点来构造。

索引顺序查找的过程也是一个“缩小区间”的查找过程。B-树查找1．定义2．查找过程3．插入操作4．查找性能的分析动态查找表

在

m

阶的B-树上，每个非终端结点可能含有：

n

个关键字

Ki（1≤i≤n）n<m

或n

个指向记录的指针

Di（1≤i≤n）

n+1

个指向子树的指针

Ai（0≤i≤n）多叉树的特性

非叶结点中的多个关键字均自小至大有序排列，即：K1<K2<…<Kn；

Ai-1所指子树上所有关键字均小于Ki；

Ai所指子树上所有关键字均大于Ki；查找树的特性平衡树的特性树中所有叶子结点均不带信息，且在树中的同一层次上；根结点或为叶子结点，或至少含有两棵子树；其余所有非叶结点均至少含有

m/2

棵子树，至多含有m

棵子树；B-树的定义B-树是一种

平衡

的多路

查找

树：root50157184382026435662788996散列查找

哈希表动态查找表

对数字的关键字可有下列构造方法：

若是非数字关键字，则需先对其进行数字化处理。1.直接定址法3.数字分析法5.折叠法4.平方取中法2.除留余数法处理冲突的方法

“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。1.开放定址法2.链接法基本概念选择排序:气泡排序快速排序直接选择排序堆排序各种排序方法的综合比较交换排序:归并排序第九章排序基本概念一、排序的定义二、内部排序三、内部排序方法的分类内部排序的方法

内部排序的过程是一个逐步扩大记录的有序序列长度的