2023年6月22日发(作者：)

编写递归算法,求二叉链表表示的二叉树t的结点个数

二叉树是一种重要的数据结构，它主要用来存储和操作数据。二叉树可以用二叉链表表示，它包含结点、左右子树指针和数据。求二叉链表表示的二叉树t的结点个数，可以使用递归算法来实现。

首先，我们可以定义一个函数NodeCount(t)用于求二叉树t的结点个数，这个函数需要传入一个二叉树t作为参数，它的返回值是该二叉树t的结点个数。

实现NodeCount(t)函数的原理是，如果t是一棵空树，则t的结点个数为0；如果t不是一棵空树，则t的结点个数为t的左子树的结点数加上t的右子树的结点数再加

1，即：NodeCount(t)=NodeCount(t->lchild)+NodeCount(t->rchild)+1

这里NodeCount(t->lchild)和NodeCount(t->rchild)的值又是递归的调用NodeCount(t)函数的结果，因此上面的表达式可以简化为：NodeCount(t)=NodeCount(t->lchild)+NodeCount(t->rchild) 也就是说，我们可以用递归的方式来求二叉树t的结点个数，每次调用NodeCount(t)函数，它会递归地求出t的左右子树的结点个数，然后将它们相加，最后加上

1，即可得到t的结点个数。

下面，我们用C语言来实现NodeCount(t)函数：int

NodeCount(struct TreeNode *t) { if (t == NULL)

return 0; else return NodeCount(t->lchild) +

NodeCount(t->rchild) + 1;}递归算法是一种非常重要的算法，它能够很方便地解决一些复杂的问题。求二叉链表表示的二叉树t的结点个数，也可以使用递归算法来实现，它的基本原理是，每次调用NodeCount(t)函数，它会递归地求出t的左右子树的结点个数，然后将它们相加，最后加上

1，即可得到t的结点个数。

递归算法在解决一些复杂的问题时，效果非常明显。它不仅能够极大地简化程序的编写，而且运行效率也很高，非常适合用于实际的开发中。