D-OJ刷题日记：计算二叉树的结点个数 题目编号:27

建立一棵二叉树，用二叉链表存储二叉树，计算二叉树中包含的结点个数。

输入描述

输入的数据只有一组，是一棵二叉树的先序遍历序列，结点的值为一个小写字母，＃号表示空结点，如输入：a b d e # # f # # # c # #，数据之间空一个格，得到的二叉树如下。(   图暂时不能上传，请同学们自己画出图）

输出描述

输出二叉树的结点个数，空树输出NULL。

输入样例

输入样例1：
a b c # # # d e # # f # #
输入样例2：
#

输出样例

输出样例1：
6
输出样例2：
NULL

思路：递归

通关代码：

#includeusing namespace std;struct BiNode {char data;BiNode* left;BiNode* right;
};class BiTree {
public:BiTree() { root = Create(); };~BiTree() { Release(root); };
public:int GetNum() { return GetNum(root); };//获取结点个数
private:BiNode* Create();void Release(BiNode* bt);int GetNum(BiNode* bt);BiNode* root;int Bnum;//结点个数
};BiNode* BiTree::Create()
{BiNode* bt;char x;cin >> x;if (x == '#') bt = NULL;else {Bnum++;bt = new BiNode;bt->data = x;bt->left = Create();bt->right = Create();}return bt;
}int BiTree::GetNum(BiNode* bt)
{int lefNum, rigNum;if (bt == NULL) return 0;lefNum = GetNum(bt->left);rigNum = GetNum(bt->right);return 1 + lefNum + rigNum;
}void BiTree::Release(BiNode* bt)
{if (bt == NULL) return;else {Release(bt->left);Release(bt->right);delete bt;}
}
int main()
{BiTree T;if (T.GetNum())cout << T.GetNum();elsecout << "NULL";	return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！