Question

数据结构课程设计，二叉树排序，高手来啊！

二叉排序树。用顺序表(一维数组)作存储结构 （8）
(1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
(2)对二叉排序树T作中序遍历,输出结果；
(3)计算二叉排序树T查找成功的平均查找长度,输出结果；
(4)输入元素x,查找二叉排序树T:若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；
人数：2人
要求：实用
要用C++做，不要C语言的额。。。。 还有一楼的貌似用的是二叉链表做存储结构的，题目要求用顺序表做存储结构的额。。。

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef int KeyType;
typedef struct
{
KeyType key;
}DataType;

typedef struct node
{
DataType data;
struct node *leftChild;
struct node *rightChild;
} BiTreeNode;

int Search(BiTreeNode *root, DataType item)
{
BiTreeNode *p;

if(root != NULL)
{
p = root;
while(p != NULL)
{
if(p->data.key == item.key) return 1;
if(item.key > p->data.key) p = p->rightChild;
else p = p->leftChild;
}
}
return 0;
}

int Insert(BiTreeNode **root, DataType item)
{
BiTreeNode *current, *parent = NULL, *p;

current = *root;
while(current != NULL)
{
if(current->data.key == item.key) return 0;
parent = current;
if(current->data.key < item.key) current = current->rightChild;
else current = current->leftChild;
}

p = (BiTreeNode *)malloc(sizeof(BiTreeNode));
if(p == NULL)
{
printf("空间不够!");
exit(1);
}

p->data = item;
p->leftChild = NULL;
p->rightChild = NULL;

if(parent == NULL) *root = p;
else if(item.key < parent->data.key)
parent->leftChild = p;
else
parent->rightChild = p;
return 1;
}

int Delete(BiTreeNode *root, DataType item)
{
BiTreeNode *p, *parent, *min;
int tag = 0;

p = root;
while(p != NULL)
{
if(p->data.key == item.key) break;

if(p->data.key < item.key)
{
tag = 1;
parent = p;
p = p->rightChild;
}
else
{
parent = p;
p = p->leftChild;
}
}

if(p == NULL) return 0;
else
{
//右子树空
if(p->rightChild == NULL)
{
printf("tag = %d\n", tag);
if(tag == 1)
parent->rightChild = p->leftChild;
else
parent->leftChild = p->leftChild;
free(p);
}
//左子树空
else if(p->leftChild == NULL)
{
printf("tag = %d\n", tag);
if(tag == 0)
parent->leftChild = p->rightChild;
else
parent->rightChild = p->rightChild;
free(p);
}
else
{
//寻找值大于当前结点的最小值，即寻找右子树的最左结点
min = p->rightChild;
while(min->leftChild != NULL)
{
parent = min;
min = min->leftChild;
}
//把右子树的最左结点的值拷贝到当前结点上
p->data = min->data;
//删除右子树的最左结点
Delete(p->rightChild, min->data);
}
return 1;
}
}

void InTraverse(BiTreeNode *root)
{
if(root == NULL) return;

if(root->leftChild != NULL)
InTraverse(root->leftChild);

printf("%d ", root->data.key);

if(root->rightChild != NULL)
InTraverse(root->rightChild);
}

int sum(BiTreeNode *root,int x)
{
if(root == NULL) return x;
else if(root->leftChild==NULL&&root->rightChild!=NULL)
return sum(root->rightChild,x++)+x;
else if(root->leftChild!=NULL&&root->rightChild==NULL)
return sum(root->leftChild,x++)+x;
else
return(sum(root->leftChild,x++)+sum(root->rightChild,x++))+x;
}

void main(void)
{
BiTreeNode *T=NULL;
int n = 8, i, s;

DataType L[8], x;
printf("输入八个不同的数：\n");
for(i=0;i<n;i++)
scanf("%d",&L[i].key);
for(i = 0; i < n; i++)
{
Insert(&T, L[i]);
}

InTraverse(T);

printf("\n平均查找深度为：");
printf("%f",(float )sum(T,1)/n);

printf("\n输入要查找的数：\n");
scanf("%d",&x.key);
s = Search(T, x);
if(s == 1)
{
printf("\n数据元素%d存在！", x.key);
Delete(T,x);
printf("\n删除%d后为：\n",x.key);
InTraverse(T);
printf("\n");
}
else
printf("\n无%d！",x.key);
printf("\n");
}
/*
查找成功的平均查找长度为所有节点深度之和除以节点总数
*/

Answer 2

#include<iostream>
using namespace std;

void Swap(int &a,int &b)
{
int temp=a;
a=b;b=temp;
}

template <class T>
void SelectSort(T A[], int n)
{
int i,j,k,small;
for (i=0; i<n-1; i++) {
small=i;
for (j=i+1;j<n;j++){if (A[j]<A[small]) small=j;}
Swap(A[i],A[small]);
cout<<"(";
for(k=0;k<i;k++) cout<<A[k]<<" ";
cout<<A[k]<<")";
k++;
for(;k<n;k++) cout<<" "<<A[k];
cout<<endl;
}
}

int main()
{
int i,n,a[400];
cin>>n;
for(i=0;i<n;i++) cin>>a[i];
cout<<"Source:"<<endl;
cout<<"(";
for(i=0;i<n-1;i++) cout<<a[i]<<" ";
cout<<a[i]<<")"<<endl;
cout<<"Select Sort:"<<endl;
SelectSort(a,n);
cout<<"Result:"<<endl;
cout<<"(";
for(i=0;i<n-1;i++) cout<<a[i]<<",";
cout<<a[i]<<")"<<endl;
return 0;
}