查找成功和失败搜索下的二叉排序树的平均搜索长度

/ **

*实验标题:

*查找成功和失败搜索下的二叉排序树的平均搜索长度

*实验目的:

*掌握二叉树的搜索过程和算法设计

*实验内容:

*设计一个程序，为给定的关键字序列构建一个二进制排序树bt，

*并找到成功和失败情况下bt的平均搜索长度.

* /

#include

#include

#include

#define MAX_SIZE 100

typedef int key_type; //定义关键字类型

typedef char info_type;

typedef结构节点{//记录类型

key_type键； //关键字项

info_type数据； //其他数据字段

结构节点* lchild; //左子指针

struct节点* rchild; //正确的子指针

} BSTNode；

/ * ----------------以括号表示法bt ------------------ *输出二进制排序树

void disp_bst（BSTNode * bt）; //函数声明

bool insert_bst（BSTNode *＆bt，key_type key）//在BST中插入一个以key为键的节点，以bt为根节点

{

if（bt == NULL）//原始树为空，新插入的记录为根节点

{

bt =（BSTNode *）malloc（sizeof（BSTNode））;

bt-> key = key;

bt-> lchild = bt-> rchild = NULL;

返回true;

}

否则if（key == bt-> key）

返回假；

否则if（key key）

返回insert_bst（bt-> lchild，键）; //插入bt节点的左侧子树

其他

返回insert_bst（bt-> rchild，键）; //插入bt节点的右子树

}

/ * ----------------从数组a中的关键字构建二进制排序树---------------- * /

BSTNode * create_bst（key_type a []，int n）

{

BSTNode * bt = NULL; //最初bt是一棵空树

int i = 0;

while（i

{

if（insert_bst（bt，a [i]）== 1）//将a [i]插入二进制排序树bst

{

printf（“步骤％d，插入％d: ”，i + 1，a [i]）；

disp_bst（bt）;

printf（“ \ n”）;

i ++;

}

}

退还债务；

}

/ * ----------------以括号表示法bt ------------------ *输出二进制排序树

void disp_bst（BSTNode * bt）

{

if（bt！= NULL）

{

printf（“％d”，bt-> key）;

if（bt-> lchild！= NULL || bt-> rchild！= NULL）

{

printf（“（”）; //仅在有子节点（

disp_bst（bt-> lchild）; //递归处理左子树

if（bt-> rchild！= NULL）

printf（“，”）; //仅在有正确的子节点时输出，

disp_bst（bt-> rchild）; //递归处理正确的子树

printf（“）”）; //仅在有子节点时输出）

}

}

}

key_type predt = -32767; // predt是一个全局变量，将前任的值保存在当前节点中，初始值为-∞

/ * ----------------确定bt是否为BST ------------------ * /

布尔法官_bst（BSTNode * bt）

{

bool b1，b2;

if（bt == NULL）

返回true;

其他

{

b1 =法官_bst（bt-> lchild）;

if（b1 == false || predt> = bt-> key）

返回假；

b2 = Justice_bst（bt-> rchild）;

返回b2;

}

}

/ * ----------------销毁BST ------------------ * /

void destroy_bst（BSTNode * bt）

{

if（bt！= NULL）

{

destroy_bst（bt-> lchild）;

destroy_bst（bt-> rchild）;

free（bt）;

}

}

/ * ----------------从根节点到找到的节点的路径以非递归方式输出----------- ------- * /

void search_bst1（BSTNode * bt，key_type key，key_type path []，int i）

{

int j;

if（bt == NULL）

返回；

else if（key == bt-> key）//查找其密钥为key的节点

{

path [i +1] = bt-> key; //输出其路径

for（j = 0; j <= i + 1; j ++）

{

printf（“％3d”，path [j]）;

}

printf（“ \ n”）;

}

其他

{

path [i +1] = bt-> key;

if（key key）

search_bst1（bt-> lchild，键，路径，i + 1）; //在左侧子树中进行递归搜索

其他

search_bst1（bt-> rchild，key，path，i + 1）; //在正确的子树中进行递归搜索

}

}

/ * ----------------递归输出从根节点到找到的节点的路径------------- ---- -* /

int search_bst2（BSTNode * bt二叉排序树的查找，key_type键）

{

if（bt == NULL）

返回0；

else if（key == bt-> key）//查找其密钥为key的节点

{

printf（“％3d”，bt-> key）; //输出关键字

返回1；

}

否则if（key key）

{

search_bst2（bt-> lchild，键）; //在左侧子树中进行递归搜索

}

其他

{

search_bst2（bt-> rchild，key）; //在右侧子树中进行递归搜索

}

printf（“％3d”，bt-> key）; //输出关键字

}

/ * ----------------删除的节点p具有左右子树，并且r指向其左子节点------------ ------ * /

void delete_node1（BSTNode * p，BSTNode *＆r）//指针引用

{

BSTNode * q;

if（r-> rchild！= NULL）//递归找到节点r的最右下层节点

{

delete_node1（p，r-> rchild）;

}

else //找到最右边的节点r（它没有右边的子树）

{

p->键= r->键; //将节点r的值存储在节点p中（替换节点值）

p->数据= r->数据;

q = r; //删除节点r

r = r-> lchild; //将其替换为节点r的左子节点

免费（q）; //释放节点r的空间

}

}

/ * ----------------从二进制排序树中删除p节点------------------ * /

void delete_node（BSTNode *＆p）

{

BSTNode * q;

if（p-> rchild == NULL）// p节点没有正确的子树的情况

{

q = p;

p = p-> lchild;

免费（q）;

}

否则if（p-> lchild == NULL）// p节点没有左子树

{

q = p;

p = p-> rchild;

免费（q）;

}

其他

delete_node1（p，p-> lchild）; // p节点同时具有左右子树

}

/ * ----------------删除键为bt中的键的节点------------------ * /

bool delete_bst（BSTNode *＆bt，key_type键）

{

if（bt == NULL）//删除空树失败

返回假；

其他

{

if（key key）

返回delete_bst（bt-> lchild，键）; //在左侧子树中递归删除以键为键的节点

否则if（key> bt-> key）

返回delete_bst（bt-> rchild，键）; //在右子树中递归删除以key为键的节点

else // key = bt->密钥情况

{

delete_node（bt）; //调用函数delete_node删除bt节点

返回true;

}

}

}

/ * --------------查找比较总数sum_len和案例数m ------------- * /

static void succ_length（BSTNode * bt，int＆sum_len，int＆m，int level）//引用类型

{

if（bt == NULL）

返回；

m ++;

sum_len + =等级;

succ_length（bt-> lchild，sum_len，m，level + 1）;

succ_length（bt-> rchild二叉排序树的查找，sum_len，m，level + 1）;

}

/ * --------------查找成功后的平均搜索长度------------- * /

静态双asl_succ（BSTNode * bt）

{

int sum_len = 0;

int m = 0;

succ_length（bt，sum_len，m，1）;

返回sum_len * 1.0 / m;

}

/ * --------------查找失败搜索的比较总数sum_len和案例数m ------------- * /

static void unsucc_length（BSTNode * bt，int＆sum_len，int＆m，int level）//引用类型

{

if（bt == NULL）//空指针对应于外部节点

{

m ++;

sum_len + = 1级；

返回；

}

unsucc_length（bt-> lchild，sum_len，m，level + 1）;

unsucc_length（bt-> rchild，sum_len，m，level + 1）;

}

/ * --------------查找搜索失败时的平均搜索长度------------- * /

静态双asl_unsucc（BSTNode * bt）

{

int sum_len = 0;

int m = 0;

unsucc_length（bt，sum_len，m，1）;

返回sum_len * 1.0 / m;

}

int main（int argc，char * argv []）

{

BSTNode * bt;

int n = 12; //关键字序列长度

key_type a [] = {25，18，46，2，53，39，32，4，74，67，60，11}; //关键字序列

printf（“（1）Create BST \ n”）;

bt = create_bst（a，n）;

printf（“（2）BST: ”）;

disp_bst（bt）;

printf（“ \ n”）;

printf（“（3）成功搜索的情况下的平均搜索长度=％g \ n”，asl_succ（bt））;

printf（“（4）搜索失败时的平均搜索长度=％g \ n”，asl_unsucc（bt））;

destroy_bst（bt）; //销毁二进制排序树

返回0；

}

测试结果:

（1）创建BST

步骤1，插入25:25

第2步，插入18:25（18）

第3步，插入46:25（18,46）

步骤4，插入2:25（18（2），46）

步骤5，插入53:25（18（2），46（，53））

步骤6，插入39:25（18（2），46（39,53））

步骤7，插入32:25（18（2），46（39（32），53））

步骤8，插入4:25（18（2（，4）），46（39（32），53））

步骤9，插入74:25（18（2（，4）），46（39（32），53（，74）））

第10步，插入67:25（18（2（，4）），46（39（32），53（，74（67））））

步骤11，插入60:25（18（2（，4）），46（39（32），53（，74（67（60）））））

步骤12，插入11:25（18（2（，4（，11））），46（39（32），53（，74（67（60）））））

（2）BST: 25（18（2（，4（，11））），46（39（32），53（，74（67（60）））））

（3）成功搜索时的平均搜索长度= 3.5

（4）搜索失败时的平均搜索长度= 4.15385

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-239150-1.html