Question

求教数据结构（c语言版）高手两道题，很急！！！！

（1）假设head是某个带表头结点单向链表的表头指针，每个结点数值字段的类型为整型。请写一个算法，从该链表中删除一个值最大的结点，并将该结点的值存入表头结点的数值字段中。
（2）编写一个递归算法，统计并返回以BT为树跟指针的二叉树中的叶子结点个数。

Answer 1

//第一个：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct myNode
{
int element;
struct myNode *next;
}NODE;

int main(void)
{
int delMax(NODE *h);//删除链表中最大值
void printList(NODE *h);//打印链表
NODE *head=NULL;//链表头
NODE *p=NULL;
NODE *q=NULL;
int i=0;

if( ( head=(NODE *)malloc(sizeof(NODE)) )==NULL )
{
printf("内存不足!");
exit(-1);//退出程序
}
head->element=-1;//初始化head里面数据值为-1
p=head;
//使随即函数rand()随机出来的值每次都不一样
srand( (unsigned int)time(NULL) );
//创建一个链表
for(i=0;i<10;i++)
{
if( ( q=(NODE *)malloc(sizeof(NODE)) )==NULL )
{
printf("内存不足!");
exit(-1);//退出程序
}
q->element=rand()%100+1;//1-100的随机数
q->next=NULL;

p->next=q;
p=p->next;//p始终指向链表末尾
}

printf("原始链表:\n");
printList(head);

delMax(head);

printf("删除最大值后链表:\n");
printList(head);

system("pause");
return 0;
}

void printList(NODE *h)
{
NODE *p=h->next;
printf("head(%3d)->",h->element);

while( p!=NULL )
{
printf("%3d->",p->element);
p=p->next;
}
printf("NULL\n");
}

int delMax(NODE *h)
{
NODE *p=h->next;
int MAX=-1;
//第一遍遍历，找到最大值
while( p!=NULL )
{
if( p->element>MAX )
{
MAX=p->element;
}
p=p->next;
}
//第二遍遍历，删除最大值
p=h->next;
NODE *pFront=h;//pFront指向p前面一个节点
while( p!=NULL )
{
if( p->element==MAX )
{
pFront->next=p->next;
h->element=MAX;
free(p);
return 0;
}
p=p->next;
pFront=pFront->next;
}

return -1;
}

//第二个
#include <stdio.h>
#include <stdlib.h>

typedef struct myBTREE
{
int element;
struct myBTREE *leftTree;
struct myBTREE *rightTree;
}BTREE;

int main(void)
{
int count(BTREE *b);//计算leaf个数，空的树根(只有树根的树)也会看成叶子
int countLeaf(BTREE *b);//纠正count的错误，不把树根看成叶子
void createBtree(BTREE *b);//建立树

BTREE *BT=(BTREE *)malloc(sizeof(BTREE));
BT->element=-1;
BT->leftTree=NULL;
BT->rightTree=NULL;
//这次我就不判断内存不足之类的错误了，麻烦

createBtree(BT);
printf("The count of leafs in BT:%d\n",countLeaf(BT));

system("pause");
return 0;
}

int count(BTREE *b)
{
if( b==NULL )
{
return 0;
}

if( b->leftTree==NULL && b->rightTree==NULL )
{
return 1;
}

return(count(b->leftTree)+count(b->rightTree));
}

int countLeaf(BTREE *b)
{
//判断是否只有树根
if( b->leftTree==NULL && b->rightTree==NULL )
{
return 0;
}

return(count(b->leftTree)+count(b->rightTree));
}

void createBtree(BTREE *b)
{//自己在这里建立树，树根为b，这里我只让树根的左树有值
BTREE *p;
p=(BTREE *)malloc(sizeof(BTREE));
p->element=-1;
p->leftTree=NULL;
p->rightTree=NULL;

b->leftTree=p;
}