数据结构,完全二叉树问题(用C语言)

发布网友 发布时间：2022-04-26 23:59

我来回答

共1个回答

热心网友 时间：2022-06-20 18:25

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

typedef struct node
{
int elem;
struct node *lch,*rch;
}Bnode;

Bnode *creat()
{
Bnode *root =NULL;
Bnode *s[20];
int i,x;
int j;
printf("input i and x:");
scanf("%d,%d",&i,&x);
while(i != 0)
{
Bnode *p = (Bnode *)malloc(sizeof(Bnode));
p->elem = x;
p->lch = NULL;
p->rch = NULL;
s[i] = p;
if(i == 1)root=p;
else
{
j = i/2;
if(i%2 == 0) //编号为偶数
s[j]->lch = p;
else
s[j]->rch = p;

}
printf("input i and x:");
scanf("%d,%d",&i,&x);
}
return root;
}
void anceng(Bnode *p) //按层遍历
{
Bnode *q = p;
Bnode *s[20];
int front = 0;
int rear = 0;
if(q != NULL)
{
rear++;
s[rear] = q;
}
while(rear != front)
{
front++;
p = s[front];
printf("%d\n",p->elem);
if(p->lch != NULL)
{
rear++;
s[rear] = p->lch;
}
if(p->rch != NULL)
{
rear++;
s[rear] = p->rch;
}
}
}

void zhonggen(Bnode *p) //非递归中根遍历
{
Bnode *q = p;
Bnode *s[20];
int top = 0;
int flag = 1;
do
{
while(q != NULL)
{
top++;
s[top] = q;
q = q->lch;
}
if(top == 0)flag = 0;
else
{
q = s[top];
top--;
printf("%d\n",q->elem);
q = q->rch;
}
}
while(flag);
}

void postorder(Bnode *p) //递归后根遍历
{
if(p!= NULL)
{
postorder(p->lch);
postorder(p->rch);
printf("%d\n",p->elem);
}
}
void inorder(Bnode *p) //递归中根遍历
{
if(p!= NULL)
{
inorder(p->lch);
printf("%d\n",p->elem);
inorder(p->rch);
}
}
void preorder(Bnode *p) //递归先根遍历
{
if(p!= NULL)
{
printf("%d\n",p->elem);
preorder(p->lch);
preorder(p->rch);
}
}
int main(void)
{
int tmp;
int i = 0;
int choice;
Bnode *root;
do
{
printf("\n");
printf("1.creat\n");
printf("2.先序遍历\n");
printf("3.中序遍历\n");
printf("4.后序遍历\n");
printf("5.中根遍历\n");
printf("6.按层遍历\n");
printf("0.exit\n");
printf("input your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
root = creat();
break;
case 2:
preorder(root);
break;
case 3:
inorder(root);
break;
case 4:
postorder(root);
break;
case 5:
zhonggen(root);
break;
case 6:
anceng(root);
break;
case 0:
break;
}

}while(choice);
return 0;
}

此代码有创建和遍历的各种算法，遍历有按层遍历，各种递归遍历和非递归遍历。希望对楼主有帮助。
望采纳！！追问

可是，为什么会这样呢