已知含有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