3.用输入的n个整数建立n个结点的完全二叉树
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define MAX 1000
struct node
{
int data;
struct node *lc; /*left左指针*/
struct node *rc; /*right右指针*/
};
typedef struct node NODE;
int setuptree(NODE *adr[MAX])
{
NODE *p;
int i; /*i结点个数控制变量*/
int n; /*n为结点的个数*/
int k; /*k为结点的编号*/
int f; /*f左右结点控制变量*/
printf("Enter the number of nodes:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
p=(NODE *)malloc(sizeof(struct node));
if(p==NULL)
{
printf("Memory error");
return -1;
}
p->lc=p->rc=NULL;
adr[i]=p;
}
for(i=1;i<=n;i++)
{
printf("Enter code of the node:");
scanf("%d",&k);
p=adr[k];
printf("Enter data:");
scanf("%d",&(p->data));
if(k>1)
{
f=k/2;
if(k%2==0)
adr[f]->lc=p;
else
adr[f]->rc=p;
}
}
return 0;
}
void pre_order(struct node *p)
{
if(p!=NULL)
{
printf("%d ",p->data);
pre_order(p->lc);
pre_order(p->rc);
}
}
void main()
{
NODE *adr[MAX];
memset(adr, 0, MAX*sizeof(NODE*));
setuptree(adr);
pre_order(adr[1]);
}
修改建议：
（1）先序改中序或后序
（2）用图形表示树，比如凹入表示法，树形表示法
（3）不限定为完全二叉树
1．编写程序实现：计算二叉链表存储的二叉树中度数为1的结点数。
2．编写程序实现：已知有—棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，求从根结点到p所指结点之间的路径。
3．编写程序实现：教材中下面习题的Huffman编码和译码过程。
“假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10, 请为这8个字母设计哈夫曼编码“