下面的二叉树代码中,删除结点中,下面这段的p->data==key和p->data>key在编译过程会出现如下报错
要怎么样才能让左右两方的类型一致呢?求解
#include <iostream>
using namespace std; //cout头文件
#include <stdio.h>
#include "malloc.h" //头文件
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define ENDFLAG -1
#define MAXSIZE 100
#define OVERFLOW -2 //宏去替代,define不做任何语法检查
typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
typedef int KeyType ;//自定义类型语句
typedef string InfoType;//自定义类型的语句
typedef struct {
KeyType key; //关键字项
InfoType otherinfo;//其他数据项
}ElemType; //个节点数据类型
typedef struct BiTNode {
ElemType data; //ElemType 描述统一而自定的,结点的数据域这里表示
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;//结构类型,BiTree指向结构体BiTNode的指针类型
struct SqStack
{
BiTree *base; // 在栈构造之前和销毁之后,base的值为NULL
BiTree *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间,以元素为单位
}; // 顺序栈
Status InitStack(SqStack &S)//初始化栈
{//算法3.1
S.base=new BiTree[MAXSIZE]; //动态分配空间
if(!S.base) return(OVERFLOW); //分配空间失败
S.top=S.base; //空栈初态
S.stacksize=MAXSIZE; //设置栈最大容量
return OK;
}
Status Push(SqStack &S,BiTree &e) //入栈
{//算法3.2
if (S.top-S.base==S.stacksize) //栈满
return ERROR;
*S.top++ = e; //元素e入栈,栈顶指针加1
return OK;
}
Status Pop(SqStack &S,BiTree &e) //出栈
{//算法3.3
if (S.top==S.base) //栈空
return ERROR;
e=*--S.top; //top减1后取出元素给e
return OK;
}
Status StackEmpty(SqStack S) //空栈
{//判断栈空
if(S.top==S.base) return OK;
else return ERROR;
}
typedef struct
{
BiTree *base; // 初始化的动态分配存储空间
int front; // 头指针,若队列不空,指向队列头元素
int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;
Status InitQueue(SqQueue &Q)
{
// 构造一个空队列Q,该队列预定义大小为MAXQSIZE
// 请补全代码
Q.base = new BiTree[MAXSIZE]; //分配数组空间
if(!Q.base) return ERROR; //存储分配失败
Q.front=0;
Q.rear=0; //头尾指针置为零
return OK;
}
Status EnQueue(SqQueue &Q,BiTree &a)//入队
{
if((Q.rear+1)%MAXSIZE == Q.front) //队满
return ERROR;
Q.base[Q.rear] = a; //新元素插入队尾
Q.rear = (Q.rear+1) % MAXSIZE; //队尾指针加1
return OK;
}
Status DeQueue(SqQueue &Q,BiTree &a)
{// 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR
if(Q.front == Q.rear) return ERROR; //队空
a = Q.base[Q.front]; //保存队头元素
Q.front = (Q.front+1)%MAXSIZE; //队头指针加1
return OK;
}
Status isQEmpty(SqQueue &Q) //空队
{
if(Q.front==Q.rear) return OK;
else return ERROR;
}
void InsertBiT(BiTree &T, ElemType e ) //插入树
{
// 当二叉排序树中不存在关键字等于e.key 的数据元素时插入e
if(!T) { //找到插入位置,递归结束
BiTree S = new BiTNode; //生成新结点*s
S -> data = e; //新结点的数据域
S -> lchild = S -> rchild = NULL; //新结点的指针域
T = S; //把新结点插入到找到的位置
}
else if(e.key<T->data.key) InsertBiT(T->lchild, e); //插入左子树
else if(e.key>T->data.key) InsertBiT(T->rchild, e); //插入右子树
}
void CreatBiT(BiTree &T) //建树
{
T=NULL;//树初始值赋值为零
ElemType e;
int n;
scanf("%d",&n);//输入个数
for(int i=0;i<n;i++) //停止条件
{
scanf("%d",&e);//输入树的元素
InsertBiT(T,e);//将输入的插入树中
}
}
void PreOrderTraverse(BiTree T) {
// 前序遍历二叉树T的递归算法,
if(T){
cout<<T->data.key;//先访问根结点
printf(" ");
PreOrderTraverse( T->lchild );//先序遍历左子树
PreOrderTraverse( T->rchild );//先序遍历右子树
}
} // PreOrderTraverse
void InOrderTraverse( BiTree T ) {
// 中序遍历二叉树T的递归算法
if(T){
InOrderTraverse( T->lchild );//中序遍历左子树
cout<<T->data.key; //访问根结点
printf(" ");
InOrderTraverse( T->rchild );//中序遍右子树
}
} // InOrderTraverse
void PostOrderTraverse( BiTree T ) {
// 后序遍历二叉树T的递归算法
//补全代码,可用多个语句
if(T){
PostOrderTraverse( T->lchild );//后序遍历左子树
PostOrderTraverse( T->rchild );//后序遍历右子树
cout<<T->data.key;//访问根结点
printf(" ");
}
} // PostOrderTraverse
int SearchBiT(BiTree T,KeyType key)//查找树
{
if(T==NULL) return 0;//树空
else
{
if(key==T->data.key) return 1; //根结点是所查找元素返回其值
else if(key>T->data.key) return SearchBiT(T->rchild,key);//如果元素大于根结点的数值就查找右子树
else if(key<T->data.key) return SearchBiT(T->lchild,key);//如果元素大于根结点的数值就查找左子树
}
}
void OrderTraverse(BiTree T) {
// 中序遍历二叉树T的非递归算法
SqStack S;
BiTree p;
BiTree q = new BiTNode;
InitStack(S); p = T;
while (p || !StackEmpty(S)) {
if (p) {
Push(S, p); //非空指针进栈
p = p->lchild; } //遍历左子树
else {
Pop(S, q); //上层指针退栈
cout<<q->data.key;
printf(" "); //访问其所指结点
p = q->rchild; } //遍历右子树
}
}
void LevelTraverse(BiTree T) //层序遍历
{ SqQueue Q;
InitQueue(Q);//初始化队列
BiTree a;
a=T;
EnQueue(Q,a); //入队
while(!isQEmpty(Q))//队列不空
{
DeQueue(Q,a) ;//出队
printf("%d",a->data.key);//输出树的元素
printf(" ");//输出时的空格
if(a->lchild)EnQueue(Q,a->lchild);//左孩子存在,入队
if(a->rchild)EnQueue(Q,a->rchild);//右孩子存在,入队
}
}
void Exchange_Tree(BiTree T)
{
if(T)
{
BiTree term;//用相同的数据类型的中间变量来记录
term = T->lchild;
T->lchild = T->rchild;
T->rchild = term;//交换过程
Exchange_Tree(T->lchild);
Exchange_Tree(T->rchild);
}
}
int Depth(BiTree T){
int m,n;
if(T){
m = Depth(T->lchild);
n = Depth(T->rchild);
if(m>n) return(m+1);
else return(n+1);
}else return 0;
}
int leaf(BiTree T)
{
if(T){
if(!T->lchild && !T->rchild) return 1;
else return (leaf(T->lchild) + leaf(T->rchild));
}else return 0;//空树,无叶子
}
void DelectNode(BiTree T, BiTNode* key)
{
BiTNode* p = T, *root=NULL, *s;//初始化
while (p)//从根开始查找关键字等于key的结点
{
if (p->data == key)
break;
root = p;
if (p->data > key)
p = p->lchild;
else
p = p->rchild;
}
if (!p)
return ;
//考虑3种情况实现p所指子树内部的处理:*p左右子树均不为空、无右子树、无左子树
BiTNode* q = p;
if ((p->lchild) && (p->rchild))
{
s = p->lchild;
while (s->rchild)
{
q = s; s = s->rchild;
}
p->data = s->data;
if (q != p)
q->rchild = s->lchild;
else
q->lchild = s->lchild;
delete s;
return ;
}
else if (!p->rchild)
{
p = p->lchild;
}
else if (!p->lchild)
{
p = p->lchild;
}
//将p所指的子树挂接到其双亲结点*f相应的位置
if (!root){
T = p;
}else if (q == root->lchild){
root->lchild = p;
}else {
root->rchild = p;
delete q;
}
}
int main() //主函数
{
BiTree T;
KeyType a;
ElemType e;
SqQueue Q;
CreatBiT(T);//创建树
//前中后序遍历
PreOrderTraverse(T);
printf("\n");
InOrderTraverse(T);
printf("\n");
PostOrderTraverse(T);
printf("\n");
//查找
scanf("%d",&a);
printf("%d",SearchBiT(T,a));
printf("\n");
scanf("%d",&a);
printf("%d",SearchBiT(T,a));
printf("\n");
//插入
scanf("%d",&e);
InsertBiT(T,e);
//插入后前中后序遍历
PreOrderTraverse(T);
printf("\n");
InOrderTraverse(T);
printf("\n");
PostOrderTraverse(T);
printf("\n");
OrderTraverse(T);
printf("\n");
LevelTraverse(T);
printf("\n");
Exchange_Tree(T);//交换各结点的左右子树
printf("\n");
Depth(T);//求二叉树深度
printf("%d",Depth(T));
printf("\n");
leaf(T);
printf("%d",leaf(T));//计算叶子节点个数
}//main