6-5 统计二叉树结点个数
分数 10
作者 韦璐
单位 广西科技大学
统计二叉树中所有结点的个数
函数接口定义:
在这里描述函数接口。例如:
int NodeCount( BinTree BT );
其中 BinTree
的结构定义为:
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};
裁判测试程序样例:
在这里给出函数被调用进行测试的例子。例如:
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100typedef struct TNode * BinTree; /* 二叉树类型 */
typedef char ElementType;
struct TNode{ /* 树结点定义 */ ElementType Data; /* 结点数据 */BinTree Left; /* 指向左子树 */ BinTree Right; /* 指向右子树 */
}; int PrintLeaves( BinTree BT );//按先序次序输入二叉树中结点的值(一个字符),@表示空树,构造二叉链表表示二叉树T
BinTree CreatBinTree()
{ElementType ch;BinTree T;scanf("%c",&ch); /*按先序次序输入树的结点,空树输入@*/if(ch == '@')T = NULL;else {T = (BinTree)malloc(sizeof(struct TNode));T->Data = ch;T->Left = CreatBinTree();T->Right = CreatBinTree();}
return T;
}
/* 请在这里填写答案 */int main()
{BinTree BT;int count;BT = CreatBinTree();if(BT == NULL){printf("\n空树!\n"); }else{count = NodeCount(BT);printf("该二叉树中所有结点个数为:%d",count); } return 0;
}
输入样例:
在这里给出一组输入。例如:
ABD@@EG@@@C@F@@
输出样例:
在这里给出相应的输出。例如:
该二叉树中所有结点个数为:7
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C程序如下:
// 计算二叉树节点总数的递归函数
int NodeCount(BinTree BT) {// 如果当前节点为空,则节点数为0if (BT == NULL) {return 0;}int left, right;left = right = 0;// 递归计算左子树的节点数left += NodeCount(BT->Left);// 递归计算右子树的节点数right += NodeCount(BT->Right);// 返回左子树节点数、右子树节点数之和再加1(当前节点)return left + right + 1;
}