已知含有n个结点的完全二叉树顺序存储,编算法传将爱完全二叉树对应的二叉树链表结构的树。
发布网友
发布时间:2022-05-04 12:06
我来回答
共2个回答
热心网友
时间:2023-10-22 14:06
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 1000
typedef struct
{
char data[MaxSize];
int n;
}SqBTree;
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}BTNode;
BTNode *trans(SqBTree a,int i)
{
BTNode *b;
if(i>a.n)
return NULL;
if(a.data[i-1]=='#')
return NULL;
b=(BTNode*)malloc(sizeof(BTNode));
b->data=a.data[i-1];
b->lchild=trans(a,2*i);
b->rchild=trans(a,2*i+1);
return b;
}
void dispBTNode(BTNode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
dispBTNode(b->lchild);
if(b->rchild!=NULL)
printf(",");
dispBTNode(b->rchild);
printf(")");
}
}
}
int main()
{
SqBTree a;
BTNode *b;
printf("请输入二叉树顺序存储结构的字符串(空节点用#表示):");
gets(a.data);
printf("\n\n请输入节点总个数n: ");
scanf("%d",&a.n);
b=trans(a,1);
printf("\n\n对应的二叉树链表结构字符串为:");
dispBTNode(b);
system("pause");
}
热心网友
时间:2023-10-22 14:06
前几天写的,输入二叉树的广义表形式,建立二叉树的链式存储。输出的是中序。有注释。例如输入:a(b,c(d,e(f)),g,h(i))
#include<stdio.h>
#include<stdlib.h>
int n=0; //全局变量
struct tree //二叉树结构体
{
char data;
struct tree *lc;
struct tree *rc;
};
tree *creat(char a[]) //创建树的二叉树
{
tree *h;
h=(tree *)malloc(sizeof(tree));
h->lc=NULL;
h->rc=NULL;
if(a[n]!=')'&&a[n]!='('&&a[n]!=',') //当a[n]为字母存入a[]
{
h->data=a[n];
n++;
}
if(a[n]=='(') //a[n]为左括弧对h->lc递归操作
{
n++;
h->lc=creat(a);
}
if(a[n]==',') //a[n]为逗号对h->rc递归操作
{
n++;
h->rc=creat(a);
return h;
}
if(a[n]==')') //a[n]为右括弧返回h
{
n++;
return h;
}
else
return h;
}
void print(tree *h) //二叉树中序输出
{
if(h!=NULL)
{
print(h->lc);
printf("%c",h->data);
print(h->rc);
}
}
int high(char a[]) //判断树的高度
{
int i=0,max=0,p=0;
while(a[i]!=0)
{
if(a[i]=='(')
{
p++;
if(max<i)
max=p;
}
if(a[i]==')')
p--;
i++;
}
if(p!=0)
{
printf("左右括弧数不等,输入错误\n"); //判断左右括弧数是否相等
exit(1);
}
return max+1;
}
void main() //主函数
{
int i=0;
tree *h;
char a[50]={0};
gets(a);
while(a[i]!=0) //判断各种可能出现的输入错误
{
if(i==0&&(a[i]=='('||a[i]==')'||a[i]==',')) //判断数组首元素是否为字母
{
printf("首节点错误\n");
exit(1);
}
if(a[i]=='(') //左括弧之前一定是字母
{
if(a[i-1]=='('||a[i-1]==')'||a[i-1]==',')
{
printf("输入错误\n");
exit(1);
}
}
if(a[i]!='('&&a[i]!=')'&&a[i]!=',') //两个字母不能在一起
{
if(a[i+1]!='('&&a[i+1]!=')'&&a[i+1]!=',')
{
printf("输入错误,两个字母不能在一起\n");
exit(1);
}
}
i++;
}
h=creat(a); //创建树
printf("该树的高度为:%d\n",high(a));
printf("该二叉树的中序输出为:");
print(h);
printf("\n");
}
热心网友
时间:2023-10-22 14:06
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 1000
typedef struct
{
char data[MaxSize];
int n;
}SqBTree;
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}BTNode;
BTNode *trans(SqBTree a,int i)
{
BTNode *b;
if(i>a.n)
return NULL;
if(a.data[i-1]=='#')
return NULL;
b=(BTNode*)malloc(sizeof(BTNode));
b->data=a.data[i-1];
b->lchild=trans(a,2*i);
b->rchild=trans(a,2*i+1);
return b;
}
void dispBTNode(BTNode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
dispBTNode(b->lchild);
if(b->rchild!=NULL)
printf(",");
dispBTNode(b->rchild);
printf(")");
}
}
}
int main()
{
SqBTree a;
BTNode *b;
printf("请输入二叉树顺序存储结构的字符串(空节点用#表示):");
gets(a.data);
printf("\n\n请输入节点总个数n: ");
scanf("%d",&a.n);
b=trans(a,1);
printf("\n\n对应的二叉树链表结构字符串为:");
dispBTNode(b);
system("pause");
}
热心网友
时间:2023-10-22 14:06
前几天写的,输入二叉树的广义表形式,建立二叉树的链式存储。输出的是中序。有注释。例如输入:a(b,c(d,e(f)),g,h(i))
#include<stdio.h>
#include<stdlib.h>
int n=0; //全局变量
struct tree //二叉树结构体
{
char data;
struct tree *lc;
struct tree *rc;
};
tree *creat(char a[]) //创建树的二叉树
{
tree *h;
h=(tree *)malloc(sizeof(tree));
h->lc=NULL;
h->rc=NULL;
if(a[n]!=')'&&a[n]!='('&&a[n]!=',') //当a[n]为字母存入a[]
{
h->data=a[n];
n++;
}
if(a[n]=='(') //a[n]为左括弧对h->lc递归操作
{
n++;
h->lc=creat(a);
}
if(a[n]==',') //a[n]为逗号对h->rc递归操作
{
n++;
h->rc=creat(a);
return h;
}
if(a[n]==')') //a[n]为右括弧返回h
{
n++;
return h;
}
else
return h;
}
void print(tree *h) //二叉树中序输出
{
if(h!=NULL)
{
print(h->lc);
printf("%c",h->data);
print(h->rc);
}
}
int high(char a[]) //判断树的高度
{
int i=0,max=0,p=0;
while(a[i]!=0)
{
if(a[i]=='(')
{
p++;
if(max<i)
max=p;
}
if(a[i]==')')
p--;
i++;
}
if(p!=0)
{
printf("左右括弧数不等,输入错误\n"); //判断左右括弧数是否相等
exit(1);
}
return max+1;
}
void main() //主函数
{
int i=0;
tree *h;
char a[50]={0};
gets(a);
while(a[i]!=0) //判断各种可能出现的输入错误
{
if(i==0&&(a[i]=='('||a[i]==')'||a[i]==',')) //判断数组首元素是否为字母
{
printf("首节点错误\n");
exit(1);
}
if(a[i]=='(') //左括弧之前一定是字母
{
if(a[i-1]=='('||a[i-1]==')'||a[i-1]==',')
{
printf("输入错误\n");
exit(1);
}
}
if(a[i]!='('&&a[i]!=')'&&a[i]!=',') //两个字母不能在一起
{
if(a[i+1]!='('&&a[i+1]!=')'&&a[i+1]!=',')
{
printf("输入错误,两个字母不能在一起\n");
exit(1);
}
}
i++;
}
h=creat(a); //创建树
printf("该树的高度为:%d\n",high(a));
printf("该二叉树的中序输出为:");
print(h);
printf("\n");
}
热心网友
时间:2023-10-22 14:06
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 1000
typedef struct
{
char data[MaxSize];
int n;
}SqBTree;
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}BTNode;
BTNode *trans(SqBTree a,int i)
{
BTNode *b;
if(i>a.n)
return NULL;
if(a.data[i-1]=='#')
return NULL;
b=(BTNode*)malloc(sizeof(BTNode));
b->data=a.data[i-1];
b->lchild=trans(a,2*i);
b->rchild=trans(a,2*i+1);
return b;
}
void dispBTNode(BTNode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
dispBTNode(b->lchild);
if(b->rchild!=NULL)
printf(",");
dispBTNode(b->rchild);
printf(")");
}
}
}
int main()
{
SqBTree a;
BTNode *b;
printf("请输入二叉树顺序存储结构的字符串(空节点用#表示):");
gets(a.data);
printf("\n\n请输入节点总个数n: ");
scanf("%d",&a.n);
b=trans(a,1);
printf("\n\n对应的二叉树链表结构字符串为:");
dispBTNode(b);
system("pause");
}
热心网友
时间:2023-10-22 14:06
前几天写的,输入二叉树的广义表形式,建立二叉树的链式存储。输出的是中序。有注释。例如输入:a(b,c(d,e(f)),g,h(i))
#include<stdio.h>
#include<stdlib.h>
int n=0; //全局变量
struct tree //二叉树结构体
{
char data;
struct tree *lc;
struct tree *rc;
};
tree *creat(char a[]) //创建树的二叉树
{
tree *h;
h=(tree *)malloc(sizeof(tree));
h->lc=NULL;
h->rc=NULL;
if(a[n]!=')'&&a[n]!='('&&a[n]!=',') //当a[n]为字母存入a[]
{
h->data=a[n];
n++;
}
if(a[n]=='(') //a[n]为左括弧对h->lc递归操作
{
n++;
h->lc=creat(a);
}
if(a[n]==',') //a[n]为逗号对h->rc递归操作
{
n++;
h->rc=creat(a);
return h;
}
if(a[n]==')') //a[n]为右括弧返回h
{
n++;
return h;
}
else
return h;
}
void print(tree *h) //二叉树中序输出
{
if(h!=NULL)
{
print(h->lc);
printf("%c",h->data);
print(h->rc);
}
}
int high(char a[]) //判断树的高度
{
int i=0,max=0,p=0;
while(a[i]!=0)
{
if(a[i]=='(')
{
p++;
if(max<i)
max=p;
}
if(a[i]==')')
p--;
i++;
}
if(p!=0)
{
printf("左右括弧数不等,输入错误\n"); //判断左右括弧数是否相等
exit(1);
}
return max+1;
}
void main() //主函数
{
int i=0;
tree *h;
char a[50]={0};
gets(a);
while(a[i]!=0) //判断各种可能出现的输入错误
{
if(i==0&&(a[i]=='('||a[i]==')'||a[i]==',')) //判断数组首元素是否为字母
{
printf("首节点错误\n");
exit(1);
}
if(a[i]=='(') //左括弧之前一定是字母
{
if(a[i-1]=='('||a[i-1]==')'||a[i-1]==',')
{
printf("输入错误\n");
exit(1);
}
}
if(a[i]!='('&&a[i]!=')'&&a[i]!=',') //两个字母不能在一起
{
if(a[i+1]!='('&&a[i+1]!=')'&&a[i+1]!=',')
{
printf("输入错误,两个字母不能在一起\n");
exit(1);
}
}
i++;
}
h=creat(a); //创建树
printf("该树的高度为:%d\n",high(a));
printf("该二叉树的中序输出为:");
print(h);
printf("\n");
}