|
|
本帖最后由 墨缘真人 于 2016-6-17 16:14 编辑 <br /><br />擂赛评判过程，其实就是一种排序过程。可以利用“数据结构”中的“二叉排序树”来解决。这种“树”建立好后，即可完成对全部参赛作品的排名。按照作品的编号，对相应作品评分每评完一个，即插入“排序二叉树”中。评分完毕后，名次就出来了。
下面具体介绍“二叉排序树”：
一、二叉排序树的定义
二叉排序树也是一种二叉树，它具有以下性质∶如果任一结点的左子树非空，则左子树中的所有结点的关键码都小于根结点的关键码；如果任一结点的右子树非空，则右子树中的所有结点的关键码都大于根结点的关键码。用二叉排序树表示字典，树中的一个结点对应于字典中的一个元素，如果按对称序周游二叉排序树得到的是字典中所有元素按关键码从小到大排成的序列。
二、二叉排序树的示例
例如关键码集合K={18,73,10,5,68,99,27,41,51,32,25}，对应的一棵二叉排序树可以如下图所示。对图中的二叉排序树进行对称序周游得到的对称序列为5, 10, 18, 25, 27, 32, 41, 51, 68, 73, 99。
三、二叉排序树的存储表示
二叉排序树通常采用一般二叉树的llink-rlink法表示，其存储结构定义如下∶
struct BinTreeNode;
typedef struct BinTreeNode * PBinTreeNode;
struct BinTreeNode
{ KeyType key; /* 结点的关键码字段 */
DataType value; /* 结点的属性字段 */
PBinTreeNode llink, rlink; /* 二叉树的左、右指针 */
};
typedef struct BinTreeNode * BinTree;
typedef BinTree * PBinTree;
四、二叉排序树的检索
int searchNode(PBinTree ptree, KeyType key, PBinTreeNode *position)
{ PBinTreeNode p, q; p=*ptree; q=p;
while(p!=NULL)
{ q=p;
if(p->key==key)/*检索成功时，由参数position指向查找到的结点 */
{ *position=p; return(TRUE);}
else if(p->key>key) /* 进入左子树继续检索 */
p=p->llink;
else p=p->rlink; /* 进入右子树继续检索 */
}
*position=q;
return(FALSE); /* 检索失败时，position指向该结点应插入的父结点 */
}
假设二叉排序树共有n个结点，高度是h（log2n≤h≤n），算法执行的时间代价
最坏为O(h)。
五、二叉排序树的插入和构造
5.1 二叉排序树的插入思想
在二叉排序树中插入新结点，要保证插入后仍满足二叉排序树的定义。插入新结点的方法是∶
1.如果二叉排序树为空，则新结点作为根结点。
2.如果二叉排序树非空，则将新结点的关键码与根结点的关键码比较，若相等表示该结点已在二叉排序树中；若小于根结点的关键码，则将新结点插入到根结点的左子树中；否则，插入到右子树中。
3.子树中的插入过程和树中的插入过程相同，如此进行下去，直到找到该结点，或者直到新结点成为叶子结点为止。
5.2 “二叉排序树”的插入示例
在如图所示的二叉排序树中插入关键码为70的结点。插入后的二叉排序树如下图所示。
5.3 "二叉排序树"的插入算法
void insertNode(PBinTree ptree, KeyType key)
{ PBinTreeNode p, position;
if(searchNode(ptree,key,&position)==TRUE)
return; /* 已存在关键码为key的结点 */
p=(PBinTreeNode)malloc(sizeof(struct BinTreeNode));
if(p==NULL) { printf(“Error\n”); exit(1); }
p->key=key; /* 忽略对p->value的赋值 */
p->llink=p->rlink=NULL;
if(position==NULL) /* 原树为空树 */
*ptree=p;
else if(key<position->key)
position->llink=p; /* 插入position的左子树 */
else position->rlink=p; /* 插入position的右子树 */
}
5.4 "二叉排序树"的构造算法
假设字典元素顺序存放在数组dic中，算法从一个空树开始，依次将字典元素插入到二叉排序树中。
void creatTree(PBinTree ptree, SeqDictionary dic)
{ int i;
*ptree=(BinTree)malloc(sizeof(struct BinTreeNode));
(*ptree)->llink=(*ptree)->rlink=NULL;
(*ptree)->key=dic.element[0].key;
for(i=1;i<dic.n;i++)
/* 将新结点插入树中 */
insertNode(ptree,dic.element.key);
}
六、二叉排序树的删除
6.1 第一种方法
1.如果被删除结点p没有左子树，则用p的右子女代替p即可。
2.否则，在p的左子树中，找出关键码最大的一个结点r (r处于p的左子树中最右下角的位置，r一定无右子女)，将r的右指针指向p的右子女，用p的左子女代替p结点。
二叉排序树的删除算法
void deleteNode(PBinTree ptree, KeyType key)
{ PBinTreeNode parentp, p, r; p=*ptree; parentp=NULL;
while(p!=NULL)
{ if(p->key==key) break;
parentp=p;
if(p->key>key) p=p->llink; /* 进入左子树 */
else p=p->rlink;
SO娱乐城：真_人.足球.彩票齐全| 开户送10元.首存送58元.手机可投ぶ注任何游戏顶级信用ぶ提现即时到账SO.CC |
|
IP卡
狗仔卡
发表于 2004-3-16 15:11
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡
发表于 2004-3-17 15:59
发表于 2004-3-19 08:33
发表于 2004-3-28 19:02
