没有合适的资源?快使用搜索试试~ 我知道了~
二叉搜索树有关应用,数据结构课程设计 1.用二叉链表作存储结构 (1)以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T; (2)对二叉排序树T作中序遍历,输出结果; (3)计算二叉排序树T的平均查找长度,输出结果; (4)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无结点x”; (5)判断二叉排序树T是否为平衡二叉树,输出信息“OK!”/“NO!”; *(6)再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT; *(7)计算平衡的二叉排序树BT的平均查找长度,输出结果。 答案
资源推荐
资源详情
资源评论
二叉排序树与平衡二叉排序树基本操作的实现50标签:排序,平衡,操作
1.用二叉链表作存储结构
(1)以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T;
(2)对二叉排序树T作中序遍历,输出结果;
(3)计算二叉排序树T的平均查找长度,输出结果;
(4)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无结点x”;
(5)判断二叉排序树T是否为平衡二叉树,输出信息“OK!”/“NO!”;
*(6)再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT;
*(7)计算平衡的二叉排序树BT的平均查找长度,输出结果。
答案
#include <stdio.h>#include <malloc.h>typedef struct BiTnode{int data;struct BiTnode *lchild,*rchild;}BiTnode,*BiTree;BiTree search_tree(BiTree T,int keyword,BiTree *father){BiTree p;*father = NULL;p = T;while (p && p->data!=keyword){*father = p;if (keyword < p->data)p = p->lchild;elsep = p->rchild;}return p;}BiTree creat_tree(int count){BiTree T,p;int i = 1;while (i <= count){if (i == 1){p = (BiTnode *)malloc(sizeof(BiTree));if (!p)return NULL;T = p;scanf("%d",&p->data);p->lchild = p->rchild = NULL;i++;}else{int temp;scanf("%d",&temp);search_tree(T,temp,&p);if (temp < p->data){p->lchild = (BiTnode *)malloc(sizeof(BiTnode));if (!p->lchild)return NULL;p = p->lchild;}else{p->rchild = (BiTnode *)malloc(sizeof(BiTnode));if (!p->rchild)return NULL;p = p->rchild;}p -> data = temp;p -> lchild = p->rchild = NULL;i++;}}return T;}int insert_tree(BiTree *T,int elem){BiTree s,p,father;s = (BiTnode *)malloc(sizeof(BiTnode));if (!s)return -1;s->data = elem;s->lchild = s->rchild = NULL;p = search_tree(*T,elem,&father);if (!p)return -1;if (father == NULL)*T = s;else if (elem < father->data)father->lchild = s;elsefather->rchild = s;return 0;}int delete_tree(BiTree *T,int elem){BiTree s,p,q,father;p = search_tree(*T,elem,&father);if(!p)return -1;if(!p->lchild){if (father == NULL){*T = p->rchild;free(p);return 0;}if (p == father->lchild)father->lchild = p->rchild;elsefather->rchild = p->rchild;free(p);return 0;}elseif(!p->rchild){if (father == NULL){*T = p->lchild;free(p);return 0;}if (p == father->lchild)father->lchild = p->lchild;elsefather->rchild = p->lchild;free(p);return 0;}else{q = p;s = p->lchild;while (s->rchild){q = s;s = s->rchild;}p->data = s->data;if (q != p)q->rchild = s->lchild;elseq->lchild = s->lchild;free(s);return 0;}}main(){}这个2叉排序数存储的数据类型是int,要存储其他类型的数据,修改节点中的数据类型
1.用二叉链表作存储结构
(1)以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T;
(2)对二叉排序树T作中序遍历,输出结果;
(3)计算二叉排序树T的平均查找长度,输出结果;
(4)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无结点x”;
(5)判断二叉排序树T是否为平衡二叉树,输出信息“OK!”/“NO!”;
*(6)再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT;
*(7)计算平衡的二叉排序树BT的平均查找长度,输出结果。
答案
#include <stdio.h>#include <malloc.h>typedef struct BiTnode{int data;struct BiTnode *lchild,*rchild;}BiTnode,*BiTree;BiTree search_tree(BiTree T,int keyword,BiTree *father){BiTree p;*father = NULL;p = T;while (p && p->data!=keyword){*father = p;if (keyword < p->data)p = p->lchild;elsep = p->rchild;}return p;}BiTree creat_tree(int count){BiTree T,p;int i = 1;while (i <= count){if (i == 1){p = (BiTnode *)malloc(sizeof(BiTree));if (!p)return NULL;T = p;scanf("%d",&p->data);p->lchild = p->rchild = NULL;i++;}else{int temp;scanf("%d",&temp);search_tree(T,temp,&p);if (temp < p->data){p->lchild = (BiTnode *)malloc(sizeof(BiTnode));if (!p->lchild)return NULL;p = p->lchild;}else{p->rchild = (BiTnode *)malloc(sizeof(BiTnode));if (!p->rchild)return NULL;p = p->rchild;}p -> data = temp;p -> lchild = p->rchild = NULL;i++;}}return T;}int insert_tree(BiTree *T,int elem){BiTree s,p,father;s = (BiTnode *)malloc(sizeof(BiTnode));if (!s)return -1;s->data = elem;s->lchild = s->rchild = NULL;p = search_tree(*T,elem,&father);if (!p)return -1;if (father == NULL)*T = s;else if (elem < father->data)father->lchild = s;elsefather->rchild = s;return 0;}int delete_tree(BiTree *T,int elem){BiTree s,p,q,father;p = search_tree(*T,elem,&father);if(!p)return -1;if(!p->lchild){if (father == NULL){*T = p->rchild;free(p);return 0;}if (p == father->lchild)father->lchild = p->rchild;elsefather->rchild = p->rchild;free(p);return 0;}elseif(!p->rchild){if (father == NULL){*T = p->lchild;free(p);return 0;}if (p == father->lchild)father->lchild = p->lchild;elsefather->rchild = p->lchild;free(p);return 0;}else{q = p;s = p->lchild;while (s->rchild){q = s;s = s->rchild;}p->data = s->data;if (q != p)q->rchild = s->lchild;elseq->lchild = s->lchild;free(s);return 0;}}main(){}这个2叉排序数存储的数据类型是int,要存储其他类型的数据,修改节点中的数据类型
资源评论
huangkexing
- 粉丝: 0
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功