82动态查找表 表结构本身是在查找过程中动态生成的。 基本操作: Initdstablet&DT),∥构造一个空的动态查找表DT DestroyDSTable(&DT);∥销毁表 Searchdstable( DT, key),∥查找关键字为key的数据元素 InsertDSTable(&Dt, e) DeleteDS Table(&dt, key) TraverseTABle( DT, VisitO),∥遍历查找表
8.2 动态查找表 表结构本身是在查找过程中动态生成的。 基本操作： InitDSTable(&DT); //构造一个空的动态查找表DT DestroyDSTable(&DT); //销毁表 SearchDSTable(DT,key); //查找关键字为key的数据元素 InsertDSTable(&DT,e); DeleteDSTable(&DT,key); TraverseDSTable(DT,visit()); //遍历查找表
821二又排序树( Binary Sort Tree 定义 二叉排序树(二叉查找树)或者是一棵空树 或者是昊有下列性质的二叉树 n每个结点都有一个作为查找依据的关键字 key),所有结点的关键字互不相同。 左子树若非空)上所有结点的关键字都小于根 结点的关键字。 右子树若非空)上所有结点的关键字都大于根 结点的关键字。 左子树和右子树也是二叉排序树
定义 二叉排序树（二叉查找树）或者是一棵空树， 或者是具有下列性质的二叉树： ▪ 每个结点都有一个作为查找依据的关键字 (key)，所有结点的关键字互不相同。 ▪ 左子树(若非空)上所有结点的关键字都小于根 结点的关键字。 ▪ 右子树(若非空)上所有结点的关键字都大于根 结点的关键字。 ▪ 左子树和右子树也是二叉排序树。 8.2.1二叉排序树 ( Binary Sort Tree )
(3 (a) (b) 几个二叉排序树的例子 如果对一棵二叉排序树进行中序遍历,可以按 从小到大的顺序,将各结点关键字排列起来
如果对一棵二叉排序树进行中序遍历，可以按 从小到大的顺序，将各结点关键字排列起来。 几个二叉排序树的例子
二叉排序树的构建 如何构造二叉排序树 1)构造过程: 从空树出发,依次插入R1~Rn各数据值: (1)如果二叉排序树是空树,则插入结点就是 叉排序树的根结点; (2)如果二叉排序树是非空的,则插入值与 根结点比较,若小于根结点的值,就插 入到左子树中去;否则插入到右子树中 示例 45,24,53,12,22,90}
二叉排序树的构建 ——如何构造二叉排序树 1) 构造过程： 从空树出发，依次插入R1 ～ Rn各数据值： （1）如果二叉排序树是空树，则插入结点就是 二叉排序树的根结点； （2）如果二叉排序树是非空的，则插入值与 根结点比较，若小于根结点的值，就插 入到左子树中去；否则插入到右子树中。 示例： { 45，24，53，12，22，90 }
2)二又排序树的数据类型描述 typedef struct int key;, Elem Type typedef struct BiTNode Elem Type data struct binode lchild. rchild 3 BiTNode, Bitree 3)二又排序树上插入结点的算法 (1)在二叉排序树上插入一个结点的算法; (2)依次输入一组数据元素,并插入到二叉排 序树中的算法
2) 二叉排序树的数据类型描述 typedef struct { int key; } ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; } BiTNode, * BiTree; 3) 二叉排序树上插入结点的算法 （1）在二叉排序树上插入一个结点的算法； （2）依次输入一组数据元素，并插入到二叉排 序树中的算法