数据结构课程设计，二叉排序树。

2025-03-01 04:04:33

推荐回答（2个）

回答1：

//调式完毕，你copy后把不必要的注释可以去掉，交作业吧，记得采纳，这程序大部分是你自己的功劳
#include
#include
using namespace std;
typedef int KeyType;
#define MaxElement 1024 //因二叉树结构，实际输入元素不能过多，否则递归调用时可能出异常
typedef struct tree//声明树的结构
{
struct tree *left; //存放左子树的指针
struct tree *right; //存放又子树的指针
KeyType key; //存放节点的内容
} BSTNode, * BSTree; //声明二叉树的链表

int insertBST(BSTree &pRoot,KeyType key) // 在二叉排序树中插入结点参数:改为根结点的引用 key值 Ok了
{//若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回
BSTree f,p=pRoot; //p的初值指向根结点
while(p) //查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲
{
if(p->key==key) //树中已有key，无须插入
return 0;
f=p; //f保存当前查找的结点，即f是p的双亲
p=(keykey)?p->left:p->right;
}
p=(BSTree)malloc(sizeof(BSTNode)); //生成新结点
p->key=key; p->left=p->right=NULL;
if(pRoot==NULL) //原树为空，新插入的结点为新的根
pRoot=p;
else
if(keykey)
f->left=p;
else
f->right=p;
return 1;
}

BSTree createBST(int *iArr)//建立二叉树
{//这个不方便重复使用,大改一下了, 参数中有则直接用参数中的，没有则键盘输入
BSTree t=NULL; //根结点
KeyType key;
int i=0;
if(!*iArr)
{
cin>>key;
while(key!=-1 && ++i {
(*iArr)++;iArr[*iArr] = key;//集合元素先在数组中存放
cin>>key;
}
}
for(i=1;i<=*iArr;i++) //由数组形式生成二叉树状集合形式
{
insertBST(t,iArr[i]);
}
return t;
}

void inorder_btree(BSTree root)// 中序遍历打印二叉排序树 OK
{
BSTree p=root;
if(p!=NULL){
inorder_btree(p->left );
cout<<" "<key<<" ";
inorder_btree(p->right );
}
}

BSTree searchBST(BSTree t,KeyType key)//元素判定注意 Ok
{ //这里稍改，返回结点指针或空比较合适
//if(key==t->key)return t->key; //如果不是它的元素，你这会先访问了一个空指针的结点
//if(t==NULL)return 0; 上下这两行顺序放错了先这行再上面一行还可以且0也可能是元素之一
//综合起来就是这个返回类型定得不合适，改为返回指针，未找到时返回空指针找到时返回所在位置
if(!t || key==t->key) return t; //<<< 先判是不是空指针，非空了再判是不是相等了
if(keykey)
return searchBST(t->left,key);
else
return searchBST(t->right,key);
}

int deleteBST(BSTree &pRoot,KeyType key)//删除本函数暂未测试
{
BSTree p,tmp,parent=NULL;
p=pRoot;
while(p)
{
if(p->key==key)
break;
parent=p;
p=(keykey)?p->left:p->right;
}
if(!p) return 0;
tmp=p;
if(!p->right&&!p->left) /*p的左右子树都为空*/
{
if(!parent) //要删根，须修改根指针
pRoot=NULL;
else if(p==parent->right)
parent->right=NULL;
else
parent->left=NULL;
free(p);
}
else if(!p->right) //p的右子树为空，则重接p的左子树
{
p=p->left;
if(!parent) //要删根，须修改根指针
pRoot=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(!p->left) //的左子树为空，则重接p的左子树
{
p=p->right;
if(!parent) //要删根，须修改根指针
pRoot=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(p->right&&p->left) //p有左子树和右子树，用p的后继覆盖p然后删去后继
{ //另有方法：用p的前驱覆盖p然后删去前驱||合并p的左右子树
parent=p; //由于用覆盖法删根，则不必特殊考虑删根
p=p->right;
while(p->left)
{
parent=p;
p=p->left;
}
tmp->key=p->key;
if(p==parent->left)
parent->left=NULL;
else
parent->right=NULL;
free(p);
}
return 1;
}

void inorder_btree2Arr(BSTree root,int *Arr)//中序遍历输出到数组中数组第0个元素放个数(初始必需为0)
{
BSTree p=root;
if(p!=NULL){
inorder_btree2Arr(p->left, Arr);
(*Arr)++; //<<<数组首个地址进来之前一定要置为0!!!! 我约定的，不许赖啊否则程序死掉不怨我
Arr[*Arr] = p->key; //Arr[*Arr]等价于Arr[Arr[0]]
inorder_btree2Arr(p->right, Arr);
}
}

void inorder_btreeCount(BSTree root,int &n)//统计个数 n 初始必需为0 否则数得不对
{
BSTree p=root;
if(p!=NULL){
inorder_btreeCount(p->left, n);
n++;
inorder_btreeCount(p->right, n);
}
}

int beyong(BSTree m,BSTree n) //子集判定
{
//if(m->key==n->left)//这是什么算法啊，我看不懂呀汗是语法错误!! 只得改写了
//return m->key;
//else
// return 0;
int i,Array[MaxElement]={0};//不懂怎么一个一个的来访问树结点，只好使个懒人的方法，转成数组，再遍历数组啦
inorder_btree2Arr(n,Array);//返回的数组第一元素为长度，之后是数据
for(i=1;i<=*Array;i++)
if(!searchBST(m,Array[i])) return 0;//有元素找不着就不是子集了
return 1;//都能找着，就是子集
}

void combineTree(BSTree A,BSTree B,BSTree &C) //A+B=C 并集
{
int i,Array[MaxElement]={0};
inorder_btree2Arr(A,Array);
C = createBST(Array); //A 先复制到 C
Array[0]=0;
inorder_btree2Arr(B,Array);
for(i=1; i<=*Array; i++) insertBST(C,Array[i]);//B的每个元素试着插入C,重复元素自动忽略
}

void joinTree(BSTree A,BSTree B,BSTree &C) //A*B=C 交集
{
int i,Array[MaxElement]={0},Array1[MaxElement]={0};
inorder_btree2Arr(B,Array);
for(i=1;i<=*Array;i++)
if(searchBST(A,Array[i])){Array1[0]++; Array1[Array1[0]] = Array[i];}//求相交的所有元素
if(Array1[0]) C = createBST(Array1); //结果不空时再组一个集合
else C=NULL;
}

void differencedTree(BSTree A,BSTree B,BSTree &C) //A-B=C 差集
{
int i,Array[MaxElement]={0},Array1[MaxElement]={0};
inorder_btree2Arr(A,Array);//列出A中所有元素
for(i=1;i<=*Array;i++)
if(!searchBST(B,Array[i])){Array1[0]++; Array1[Array1[0]] = Array[i];}//求出不属于B的所有元素
if(Array1[0]) C = createBST(Array1); //结果不空时再组一个集合
else C=NULL;
}

int main()
{
int i,e;
int iArray[MaxElement]={0};//数组形式的整数集合做输入输出缓冲,输入时先在这暂存
BSTree root1,root2,root3,root4,root5;
cout<<"请输入你所要创建的集合LA，以-1结束：\n"; //<<<怎么看着不伦不类呀，这换行，有C风格的\n
iArray[0]=0;
root1=createBST(iArray);
cout<<"\n\n中序遍历二叉树："< inorder_btree(root1);
cout<<"\n"< printf("请输入e的值:");
scanf("%d",&e);
if(searchBST(root1,e))//元素判定
printf("元素e(%d)属于集合\n",e);
else
printf("元素e(%d)不属于集合\n",e);

cout<<"请输入你所要创建的集合LB，以-1结束：\n";
iArray[0]=0;
root2=createBST(iArray);

cout<<"\n求子集:"< i=beyong(root1,root2);
if(i)//子集判定
printf("集合LB包含于LA\n");
else
printf("集合LB不包含于LA\n");
i=beyong(root2,root1);
if(i)//子集判定
printf("集合LA包含于LB\n");
else
printf("集合LA不包含于LB\n");

cout<<"\n求并集:";
combineTree(root1,root2,root3);
if(!root3)
cout<<"LA+LB 并集怎会是空的，怪鸟!"< else
{
cout<<"中序遍历 LA+LB 的交集二叉树："< inorder_btree(root3);
}

cout<<"\n求交集:";
joinTree(root1,root2,root4);
if(!root4)
cout<<"LA*LB 交集怎会是空的? 有可能!"< else
{
cout<<"中序遍历 LA*LB 的交集二叉树："< inorder_btree(root4);
}

cout<<"\n求差集:";
differencedTree(root1,root2,root5);
if(!root5)
cout<<"LA-LB 差集怎会是空的? 有可能!"< else
{
cout<<"中序遍历LA-LB的交集二叉树："< inorder_btree(root5);
}
//内存资源系统能很好的收回，据说咱分配的一堆内存垃圾就丢那不理了也没事哦, 若作服务程序可就不要这样
}

回答2：

好的，我来做吧，免费的。。。嘿嘿》》》》

最新问答

有ESP无ESP真的那么重要吗

缺水的男孩名字经典

2011年沈阳建筑大学建筑学专业（二本）在辽宁的录取线是多少

青春理想作文800字

重庆中考语文作文写记叙文还是议论文

大概时间年前看过的一部电影，外国的，只是大概记得最后男的念什么东西，然后一个神从空中出现带走他

北京兴天通防雷科技有限公司怎么样？

花时间和金钱读在职MPA到底值不值

紫薇树有是什么颜色的

怎么用c语言随机生成4个0~9的数？求编程！！拜托了，很急用！！