最近评论
正在载入评论列表...
11.3 结构与函数
结构表示C语言的一个强大特性，因此它与函数并用非常重要。现在探讨如何把结构当成变元传递给函数，以及如何从函数中返回结构。
11.3.1 结构作为函数的变元
将结构作为变元传给函数和传递一般变量没有什么不同。创建类似于horse的结构，如下：
struct family
{
char name[20];
int age;
char father[20];
char mother[20];
};
然后，建立一个函数，检查两个family类型的成员是否为兄弟，如下：
bool siblings(struct family memberl, struct family member2)
{
if(strcmp(memberl.mother, member2.mother) == 0)
return true;
else
return false;
}
这个函数有两个结构变元，该函数比较这两个结构中的mother成员。如果它们相同，就表示是兄弟，返回true。否则就返回false。这里忽略了离婚、人工受精和克隆等其他可能性。
11.3.2 结构指针作为函数变元
在调用函数时，传送给函数的是变元值的副本。如果变元是一个非常大的结构，就需要相当多的时间，并占用结构副本所需的内存。在这种情况下，应该使用结构指针作为变元。这可以避免占用内存，节省复制的时间，因为只需复制指针。函数可以通过指针直接访问原来的结构。另外，使用指针给函数传送结构，也提高了效率。重写siblings()函数，如下：
bool siblings(struct family *member1, struct family *member2)
{
if(strcmp(member1->mother, member2->mother) == 0)
return true;
else
return false;
}
这有一个缺点。按值传递机制禁止在被调用的函数中意外地更改变元值。如果使用指针，就丧失了这个优点。而如果不需要更改指针变元的值(只是访问并使用它们)，把指针传送给函数还是可以获得某种程度的保护。
在上一个siblings()函数中，不需要修改传给它的结构，它只是比较两个成员而已。因此可以重写它，如下所示：
bool siblings(struct family const *pmember1, struct family const *pmember2)
{
if(strcmp(pmember1->mother, pmember2->mother) == 0)
return true;
else
return false;
}
本书在前面介绍了const修饰符，它用于将变量变成常量。这个函数声明将参数的类型指定为family结构的常量指针。这意味着，传递给函数的结构指针在函数中被视为常量。试图改变结构，会在编译期间产生错误信息。当然，这不会影响它们在调用程序中的状态，因为const关键字仅在执行siblings()函数时应用于指针值。
注意下面这个函数和前一个函数的差异：
bool siblings(struct family *const pmember1, struct family *const pmember2)
{
if(strcmp(pmember1->mother, pmember2->mother) == 0)
return true;
else
return false;
}
每个参数定义中的间接运算符在关键字const的前面，而不是在指针名称的前面。这有什么差别吗？这里的参数是“指向family结构类型的常量指针”，而不是“指向常量结构的指针”，因此可以在函数中随意改变结构，但是不能改变存储在指针内的地址。因为这里保护的是指针，而不是指针指向的结构。
11.3.3 作为函数返回值的结构
函数返回结构和返回一般数值一样，只是在函数原型中，要以正常的方式指出函数返回的是结构，例如：
struct horse my_fun(void);
这个函数原型说明，它是一个没有变元的函数，返回horse类型的结构。
可以像这样从函数返回一个结构，但比较方便的做法是返回结构指针。下面在实例中探讨其细节。
试试看：返回结构指针
为了返回结构指针，可以重写前面的horse结构例子，把马换成人，并将输入部分放在一个函数中。
/* Program 11.6 Basics of a family tree */
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
struct Family *get_person(void); /* Prototype for input function */
struct Date
{
int day;
int month;
int year;
};
struct Family /* Family structure declaration */
{
struct Date dob;
char name[20];
char father[20];
char mother[20];
struct Family *next; /* Pointer to next structure */
struct Family *previous; /* Pointer to previous structure */
};
int main(void)
{
struct Family *first = NULL; /* Pointer to first person */
struct Family *current = NULL; /* Pointer to current person */
struct Family *last = NULL; /* Pointer to previous person */
char more = '\0'; /* Test value for ending input */
for( ; ; )
{
printf("\nDo you want to enter details of a%s person (Y or N)? ",
first != NULL?"nother" : "");
scanf(" %c", &more);
if(tolower(more) == 'n')
break;
current = get_person();
if(first == NULL)
{
first = current; /* Set pointer to first Family */
last = current; /* Remember for next iteration */
}
else
{
last->next = current; /* Set next address for previous Family */
current->previous = last; /* Set previous address for current */
last = current; /* Remember for next iteration */
}
}
/* Now tell them what we know */
/* Output Family data in reverse order */
while (current != NULL)
{
printf("\n%s was born %d/%d/%d, and has %s and %s as parents.",
current->name, current->dob.day, current->dob.month,
current->dob. year, current->father, current->mother );
last = current; /* Save pointer to enable memory to be freed */
current = current->previous; /* current points to previous list */
free(last); /* Free memory for the Family we output */
}
return 0;
}
/* Function to input data on Family members */
struct Family *get_person(void)
{
struct Family *temp; /* Define temporary structure pointer */
/* Allocate memory for a structure */
temp = (struct Family*) malloc(sizeof(struct Family));
printf("\nEnter the name of the person: ");
scanf("%s", temp -> name ); /* Read the Family's name */
printf("\nEnter %s's date of birth (day month year); ", temp->name);
scanf("%d %d %d", &temp->dob.day, &temp->dob.month, &temp->dob.year);
printf("\nWho is %s's father? ", temp->name );
scanf("%s", temp->father ); /* Get the father's name */
printf("\nWho is %s's mother? ", temp->name );
scanf("%s", temp -> mother ); /* Get the mother's name */
temp->next = temp->previous = NULL; /* Set pointers to NULL */
return temp; /* Return address of Family structure */
}
代码的说明
代码很多，但很简单，执行的方式和前一个例子类似，只是用了两个函数，而不是一个函数。
第一个结构的声明如下：
struct Date
{
int day;
int month;
int year;
);
用三个整数成员day、month和year来定义Date结构。目前这个结构还没有实例。这个定义放在源文件的所有函数之前，因此可以在文件的所有函数中访问。
下一个结构的声明如下：
struct Family /* Family structure declaration */
{
struct Date dob;
char name[20];
char father[20];
char mother[20];
struct Family *next; /* Pointer to next structure */
struct Family *previous; /* Pointer to previous structure */
};
上述语句定义了结构类型Family，它的第一个成员是Date类型的结构。然后是三个char数组成员。最后两个成员是结构指针，分别指向表中的下一个结构和上一个结构，将该结构变成一个双向链表。
这和前一个例子的最大差别是，这两个结构都在所有函数的外部声明，因此是全局结构。这是必需的，因为main()函数和get_person()函数要定义Family结构的变量。
注意：
只有结构类型的声明可以全局访问，在每个函数内声明的Family类型变量的作用域是声明它们的函数。
函数get_person()的原型如下：
struct Family *get_person(void); /* Prototype for input function */
它指出这个函数没有变元，但返回一个Family结构的指针。
其过程与程序11.5的操作相同，区别是使用了全局的结构类型声明，并将结构放在一个独立的函数中。
检查用户在more中的响应，确认用户要输入数据后，main()函数调用get_person()函数。在函数get_person()内声明如下指针：
temp = (struct Family*) malloc(sizeof(struct Family));
这是“Family类型结构的指针”，并且是本地变量。结构类型的声明是全局性的，但它与结构实例的作用域无关。每个实例的作用域取决于其声明在程序中的位置。
函数get_person()内的第一个动作是：
temp = (struct Family*) malloc(sizeof(struct Family));
调用malloc()函数给Family类型的结构分配了足够的内存，并将返回的地址存储到指针变量temp中。temp是本地变量，在get_person()函数结束时，temp就不存在了，但是malloc()函数分配的内存是永久的，可以在程序的某个地方释放该内存，或在退出程序时释放它。
函数get_person()会读取每个人的所有基本数据，并将它存储到temp所指的结构中。这个函数会接受任何数值的日期，但在实际情况下应该检查数据的有效性，例如要确认月份应是1~12，日期值对于该月也应是有效的。由于输入的是出生日期，因此应验证该日期不是未来的某个日期。
get_person()函数的最后一行语句是：
return temp; /* Return address of Family structure */
这行语句会返回结构指针的副本。虽然返回后temp就不存在了，但是它所指的内存地址仍然有效。
回到main()函数中，返回的指针存储到current变量中。如果这是第一次迭代，该指针也会存储到first变量中。这么做的目的是不希望失去链表中第一个结构的记录。另外也将current指针存到last变量中，因此下一次迭代时，可以将它填入当前结构的指针成员previous中。
读完所有输入的数据后，程序以类似前一个例子的方式，以反向顺序将小结输出到屏幕上。
11.3.4 修改程序
下面创建一个例子，将结构指针作为变元和返回值。修改前一个例子(程序11.6)，在Family类型的结构中声明一些额外的指针p_to_pa和p_to_ma，如下所示：
struct Family /* Family structure declaration */
{
struct Date dob;
char name[20];
char father[20];
char mother[20];
struct Family *next; /* Pointer to next structure */
struct Family *previous; /* Pointer to previous structure */
struct Family *p_to_pa; /* Pointer to father structure */
struct Family *p_to_ma; /* Pointer to mother structure */
};
现在可以在指针成员p_to_pa和p_to_ma中记录相关结构的地址了。必须在get_person()函数的return语句之前添加如下语句，将它们设定成NULL。
temp->p_to_pa = temp->p_to_ma = NULL; /* Set pointers to NULL */
现在可以扩展程序，使用两个额外的函数，在输入完每个人的数据后，给指针p_to_pa和p_to_ma填入适当的数值。第一个函数是set_ancestry()，它把Family结构的指针作为变元，检查第二个变元是否为第一个变元的父亲或母亲。如果是，就更改相应的指针，以反映这个结果，然后返回true。否则返回false。代码如下：
bool set_ancestry(struct Family *pmember1, struct Family *pmember2)
{
if(strcmp(pmember1->father, pmember2->name) == 0)
{
pmember1->p_to_pa = pmember2;
return true;
}
if( strcmp(pmember1->mother, pmember2->name) == 0)
{
pmember1->p_to_ma = pmember2;
return true;
}
else
return false;
}
第二个函数检查两个Family结构间的关系，如下：
/* Fill in pointers for mother or father relationships */
bool related (struct Family *pmember1, struct Family *pmember2)
{
return set_ancestry(pmember1, pmember2) ||
set_ancestry(pmember2, pmember1);
}
函数related()在return语句中调用set_ancestry()函数两次，以测试所有可能的关系。如果两次调用set_ancestry()中有一次返回true，related()函数的返回值就是true。调用程序可以用这个返回值判断指针是否已经填入了数值。
注意：
这里使用了库函数strcmp()，所以必须在程序的开头用#include指令包含头文件<string.h>。还需要给<stdbool.h>添加#include指令，因为还使用了bool类型和true、false值。
现在要给程序11.6中的main()函数添加一些代码，以使用related()函数，在包含有效地址的所有结构内填入指针。在输入初始数据的循环后，可以将以下代码插入main()函数中：
current = first;
while(current->next != NULL) /* Check for relation for each person in */
{ /* the list up to second to last */
int parents = 0; /* Declare parent count local to this block */
last = current->next; /* Get the pointer to the next */
while(last != NULL) /* This loop tests current person */
{ /* against all the remainder in the list */
if(related(current, last)) /* Found a parent ? */
if(++parents == 2) /* Yes, update count and check it */
break; /* Exit inner loop if both parents found */
last = last->next; /* Get the address of the next */
}
current = current->next; /* Next in the list to check */
}
/* Now tell them what we know etc. */
/* rest of output code etc. …*/
这是一段相当独立的代码块，用来填入双亲的指针。它从第一个结构开始，检查后续的结构之间是否存在父母关系。如果找到两个双亲(说明两个指针中已填入数据)，或到达链表的尾部，就停止检查。
一些结构的指针值可能没有更改。因为这不是一个永无止尽的链表，可能有些人的双亲数据不齐全。所以需要遍历链表中的每个结构，将它与后续的所有结构比较，确定它们是否有关系，至少要到找到两个双亲的结构为止。
当然，还必须在程序的开头、函数get_person()的原型后面插入related()和set_ancestry()的函数原型。它们的原型如下：
bool related(struct Family *pmember1, struct Family *pmember2);
bool set_ancestry(struct Family *pmember1, struct Family *pmember2);
为了说明指针已成功插入，可以扩展最后的输出，在最后一个printf()函数的后面加入一些语句，显示每个人的双亲信息。也可以修改输出循环，从first开始，所以输出循环如下所示：
/* Output Family data in correct order */
current = first;
while (current != NULL) /* Output Family data in correct order */
{
printf("\n%s was born %d/%d/%d, and has %s and %s as parents.",
current->name, current->dob.day, current->dob.month,
current->dob. year, current->father, current->mother);
if(current->p_to_pa != NULL )
printf("\n\t%s's birth date is %d/%d/%d ",
current->father, current->p_to_pa->dob.day,
current->p_to_pa->dob.month,
current->p_to_pa->dob.year);
if(current->p_to_ma != NULL)
printf("and %s's birth date is %d/%d/%d.\n ",
current->mother, current->p_to_ma->dob.day,
current->p_to_ma->dob.month,
current->p_to_ma->dob.year);
current = current->next; /* current points to next in list */
}
只有将双亲的结构指针设定成有效的地址，才能为每个人生成双亲的出生日期。不过，不能在循环内释放内存，否则，当双亲结构出现在链表的前面时，输出父母出生日期的语句就会生成垃圾值。因此在输出完毕后，必须在main()函数的最后添加一个循环，以释放内存。
/* Now free the memory */
current = first;
while(current != NULL)
{
last = current; /* Save pointer to enable memory to be freed */
current = current->next; /* current points to next in list */
free(last); /* Free memory for last */
}
把所有的片段集合成一个相当大的新程序。它的输出如下：
Do you want to enter details of a person (Y or N)? y
Enter the name of the person: Jack
Enter Jack's date of birth (day month year); 1 1 65
Who is Jack's father? Bill
Who is Jack's mother? Nell
Do you want to enter details of another person (Y or N)? y
Enter the name of the person: Mary
Enter Mary's date of birth (day month year); 3 3 67
Who is Mary's father? Bert
Who is Mary's mother? Moll
Do you want to enter details of another person (Y or N)? y
Enter the name of the person: Ben
Enter Ben's date of birth (day month year); 2 2 89
Who is Ben's father? Jack
Who is Ben's mother? Mary
Do you want to enter details of another person (Y or N)? n
Jack was born 1/1/65, and has Bill and Nell as parents.
Mary was born 3/3/67, and has Bert and Moll as parents.
Ben was born 2/2/89, and has Jack and Mary as parents.
Jack's birth date is 1/1/65 and Mary's birth date is 3/3/67.
可以修改这个程序，以日期的顺序输出每个人，或计算出每个人有多少后代。
11.3.5 二叉树
二叉树是组织数据的一种非常有效的方式，因为二叉树中的数据可以以有序的方式安排。二叉树也是一种非常有趣的机制，它在本质上非常简单。实现二叉树涉及到递归和动态分配内存，还要使用指针传送结构。
二叉树包含一系列相互关联的元素，称为节点。起始节点是树的根，称为根节点，如图11-5所示。
图11-5 二叉树的结构
每个节点一般包含一个数据项，以及两个指向后续节点(左节点和右节点)的指针。如果有一个后续节点不存在，对应的指针就是NULL。节点还可以包含一个计数器，记录树中何时有重复的数据项。
结构很容易表示二叉树的节点。下面的结构示例就定义了存储long类型整数的节点：
struct Node
{
long item; /* The data item */
int count; /* Number of copies of item */
struct Node *pLeft; /* Pointer to left node */
struct Node *pRight; /* Pointer to right node */
};
将数据项添加到二叉树中，且该项已存在于二叉树中时，就不创建新节点，而是把已有节点的count成员递增1。本章的下一个程序示例11.7在创建二叉树时，就利用前面的结构定义表示一个包含整数的节点。
1. 对二叉树中的数据排序
构建二叉树的方式确定了树中数据项的顺序。将一个数据项添加到二叉树中，需要比较要添加的项和树中已有的项。一般在添加数据项时，要求使左子节点的数据项小于当前节点的数据项，右子节点的数据项大于当前节点的数据项。图11-6中的示例二叉树包含随机顺序的整数。
图11-6 存储整数的二叉树
树的结构取决于数据项添加到树中的顺序。添加一个新项时，需要从树中的根节点开始，比较树中节点的值和新项。如果新项比给定的节点小，就查看给定节点的左子节点；反之，如果新项比给定的节点大，就查看给定节点的右节点。这个过程一直继续下去，直到找到一个与新项的值相同的节点为止，此时就更新这个节点的count。如果到达一个左节点或右节点的指针为NULL，就把新节点放在这里。
2. 构建二叉树
首先是创建根节点。所有节点的创建方式都相同，所以第一步是定义一个函数，从数据项中创建节点。假定创建一个存储整数的二叉树，可以使用前面的结构定义。下面是创建节点的函数定义：
struct Node *createnode(long value)
{
/* Allocate memory for a new node */
struct Node *pNode = (struct Node *)malloc(sizeof(struct Node));
pNode->item = value; /* Set the value */
pNode->count = 1; /* Set the count */
pNode->pLeft = pNode->pRight = NULL; /* No left or right nodes */
return pNode;
}
这个函数给新的Node结构分配内存，将item成员设置为value。count成员是节点中值的重复次数，所以对于第一个节点，这个count成员是1。现在还有后续节点，所以pLeft和pRight成员设置为NULL。这个函数返回指向新建Node对象的指针。
要为新的二叉树创建根节点，可以使用这个函数，如下所示：
long newvalue;
printf("Enter the node value: ");
scanf(" %ld", newvalue);
struct Node *pRoot = createnode(newvalue);
从键盘上读取了要存储的值后，就调用createnode()函数，在堆上创建一个新节点。当然，不要忘了使用完毕后释放节点的内存。
二叉树是应用递归的一个领域。插入节点的过程涉及到以相同的方式查看一系列节点，这是使用递归的一个强烈的暗示。用下面的函数在树中添加一个已有的节点：
/* Add a new node to the tree */
struct Node *addnode(long value, struct Node* pNode)
{
if(pNode == NULL) /* If there's no node */
return createnode(value); /* …create one and return it */
if(value ==pNode->item)
{ /* Value equals current node */
++pNode->count; /* …so increment count and */
return pNode; /* …return the same node */
}
if(value < pNode->item) /* If less than current node value */
{
if(pNode->pLeft == NULL) /* and there's no left node */
{
pNode->pLeft = createnode(value); /* create a new left node and */
return pNode->pLeft; /* return it. */
}
else /* If there is a left node…*/
return addnode(value, pNode->pLeft); /* add value via the left node */
}
else /* value is greater than current */
{
if(pNode->pRight == NULL) /* so the same process with */
{ /* the right node. */
pNode-> pRight = createnode(value);
return pNode-> pRight;
}
else
return addnode(value, pNode-> pRight);
}
}
第一次调用addnode()函数时，它的变元是存储在树中的值和根节点的地址。如果将NULL作为第二个变元传送，该函数就创建并返回一个新节点，所以也可以使用这个函数创建根节点。把根节点作为第二个变元传送时，有如下三种情况。
(1) 如果value等于当前节点的值，就不需要创建新节点，只递增当前节点中的计数器，并返回该节点。
(2) 如果value小于当前节点的值，就需要查看左子节点。如果左节点的指针是NULL，就创建一个包含value的新节点，使之成为左子节点。如果左节点存在，就递归调用addnode()函数，把指向左子节点的指针作为第二个变元。
(3) 如果value大于当前节点的值，就以与左节点相同的方式查看右节点。
无论调用递归函数时执行了什么，该函数都返回一个插入值的节点的指针。这可能是一个新节点，也可以是一个其值已存在于树中的节点。
下面的代码构建了一个完整的二叉树，以存储任意多个整数。
long newvalue = 0;
struct Node *pRoot = NULL;
char answer = 'n';
do
{
printf("Enter the node value: ");
scanf(" %ld", &newvalue);
if(pRoot == NULL)
pRoot = createnode(newvalue);
else
addnode(newvalue, pRoot);
printf("\nDo you want to enter another (y or n)? ");
scanf(" %c", &answer);
} while(tolower(answer) == 'y');
do-while循环构建了一个包含根节点的完整的二叉树。在第一次迭代中，pRoot是NULL，所以创建根节点。所有后续的迭代给已有的树中添加节点。
3. 遍历二叉树
可以遍历二叉树，用升序或降序方式提取其内容。下面讨论如何以升序方式提取数据，读者可以以类似的方式获得降序排序的数据。从二叉树中提取数据初看上去是一个复杂的问题，因为二叉树的结构是随意的，但使用递归，这个问题就很简单了。
从很明显的地方开始：左子节点的值总是小于当前节点，当前节点的值总是小于右子节点，因此，提取值的顺序就应是左子节点、当前节点、右子节点。当然，如果子节点还有孙节点，也必须按“左子节点、当前节点、右子节点”的顺序处理。下面用一些代码来说明。
假定要以升序方式列出二叉树中的整数值。完成该操作的函数如下：
/* List the node values in ascending sequence */
void listnodes(struct Node *pNode)
{
if(pNode->pLeft != NULL)
listnodes(pNode->pLeft); /* List nodes in the left subtree */
for(int i = 0; i<pNode->count ; i++)
printf("\n%10ld", pNode->item); /* Output the current node value */
if(pNode->pRight != NULL)
listnodes(pNode->pRight); /* List nodes in the right subtree */
}
该函数包含如下三步：
(1) 如果存在左子节点，就为该节点递归调用listnodes()函数。
(2) 输出当前节点的值。
(3) 如果存在右子节点，就为该节点递归调用listnodes()函数。
如果根节点存在左子节点，就重复第1步，因此，输出左子树的所有信息后，再输出当前节点的值。当前节点的值在输出中重复count次，以表示该节点的重复次数。在输出当前节点的值后，输出根节点的整个右子树中的值。树中的每个节点都要进行这样的处理，所以值以升序方式输出。只需将根节点指针作为变元，调用listnodes()函数即可，如下所示：
listnodes(pRoot); /* Output the contents of the tree */
这个简单的函数可以输出任意二叉树的所有整数值，下面探讨其工作过程。
试试看：用二叉树排序
这个示例将前面的代码合并起来，如下：
/* Program 11.7 Sorting integers using a binary tree */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
/* Function prototypes */
struct Node *createnode(long value); /* Create a tree node */
struct Node *addnode(long value, struct Node* pNode);
/* Insert a new node */
void listnodes(struct Node *pNode); /* List all nodes */
void freenodes(struct Node *pNode); /* Release memory */
/* Defines a node in a binary tree sotring integers */
struct Node
{
long item; /* The data item */
int count; /* Number of copies of item */
struct Node *pLeft; /* Pointer to left node */
struct Node *pRight; /* Pointer to right node */
};
/* Function main - execution starts here */
int main(void)
{
long newvalue = 0;
struct Node *pRoot = NULL;
char answer = 'n';
do
{
printf("Enter the node value: ");
scanf(" %ld", &newvalue);
if(pRoot == NULL)
pRoot = createnode(newvalue);
else
addnode(newvalue, pRoot);
printf("\nDo you want to enter another (y or n)? ");
scanf(" %c", &answer);
} while(tolower(answer) == 'y');
printf("The values in ascending sequence are: ");
listnodes(pRoot); /* Output the contents of the tree */
freenodes(pRoot); /* Release the heap memory */
return 0;
}
struct Node *createnode(long value)
{
struct Node *pNode = (struct Node *)malloc(sizeof(struct Node));
pNode->item = value; /* Set the value */
pNode->count = 1; /* Set the count */
pNode->pLeft = pNode->pRight = NULL; /* No left or right nodes */
return pNode;
}
/* Add a new node to the tree */
struct Node *addnode(long value, struct Node* pNode)
{
if(pNode == NULL) /* If there's no node */
return createnode(value); /* ...create one and return it */
if(value ==pNode->item)
{ /* Value equals current node */
++pNode->count; /* …so increment count and */
return pNode; /* …return the same node */
}
if(value < pNode->item) /* If less than current node value */
{
if(pNode->pLeft == NULL) /* and there's no left node */
{
pNode->pLeft = createnode(value); /* create a new left node and */
return pNode->pLeft; /* return it. */
}
else /* If there is a left node... */
return addnode(value, pNode->pLeft); /* add value via the left node */
}
else /* value is greater than current */
{
if(pNode->pRight == NULL) /* so the same process with */
{ /* the right node. */
pNode-> pRight = createnode(value);
return pNode-> pRight;
}
else
return addnode(value, pNode-> pRight);
}
}
/* List the node values in ascending sequence */
void listnodes(struct Node *pNode)
{
if(pNode->pLeft != NULL)
listnodes(pNode->pLeft);
for(int i = 0; i<pNode->count ; i++)
printf("\n%10ld", pNode->item);
if(pNode->pRight != NULL)
listnodes(pNode->pRight);
}
/* Release memory allocated to nodes */
void freenodes(struct Node * pNode)
{
if(pNode == NULL) /* If there's no node... */
return; /* we are done. */
if(pNode->pLeft != NULL) /* If there's a left sub-tree */
freenodes(pNode->pLeft); /* free memory for those nodes. */
if(pNode->pRight != NULL) /* If there's a right sub-tree */
freenodes(pNode->pRight); /* free memory for those nodes. */
free(pNode); /* Free current node memory */
}
程序的输出如下：
Enter the node value: 56
Do you want to enter another (y or n)? y
Enter the node value: 33
Do you want to enter another (y or n)? y
Enter the node value: 77
Do you want to enter another (y or n)? y
Enter the node value: -10
Do you want to enter another (y or n)? y
Enter the node value: 100
Do you want to enter another (y or n)? y
Enter the node value: -5
Do you want to enter another (y or n)? y
Enter the node value: 200
Do you want to enter another (y or n)? n
The values in ascending sequence are:
-10
-5
33
56
77
100
200
代码的说明
main()函数中的do-while循环利用前面讨论的方式从输入的值中构建出了二叉树。只要在提示时输入y或Y，该循环就继续。调用listnodes()函数时，将根节点的地址作为变元，就会以升序方式输出树中的所有值。接着，调用freenodes()函数，释放为树中节点分配的内存。
freenodes()函数是本例中唯一的新东西。这是另一个递归函数，其工作方式类似于listnodes()函数。本例在释放节点的内存之前，先删除每个节点的子节点的内存。因为一旦释放了内存块，其他程序就可以使用它了。也就是说，一旦释放了内存，子节点的地址就无效了。因此，在释放当前节点的内存之前，listnodes()函数总是为非空的子节点指针调用freenodes()函数。
可以构建二叉树来存储任意类型的数据，包括结构对象和字符串。如果要在二叉树中组织字符串，就可以在每个节点中使用指针引用字符串，而无须复制树中的字符串。
