计算二叉树结点度为0,1,2的结点个数

计算二叉树结点度为0,1,2的结点个数

【问题描述】首先利用二叉树的前序遍历建立一棵二叉树，分别用3个递归函数统计度为0，度为1和度为2的结点个数，并输出结果，这3个函数可以定义为二叉树的成员函数

【输入形式】假设二叉树的结点为字符型，输入“#”表示空结点，输入为一行字符串，具体见样例输入，二叉树见教材P202页，图5.15

【输出形式】输出只有1行，依次输出度为0的结点个数，度为1的结点个数，度为2的结点个数，3个数之间用空格分开，最后一个数据后面有一个空格，具体格式见样例输出

【样例输入】

ABC##DE#G##F###

【样例输出】

3 2 2

【样例说明】

其他测试数据：

输入：A## 输出：1 0 0

输入：AB#D##C#E## 输出：2 2 1

代码如下:

#include<iostream>using namespace std;template<class T>
struct BinTreeNode
{T data;BinTreeNode<T>* leftchild;BinTreeNode<T>* rightchild;BinTreeNode(){leftchild = NULL;rightchild = NULL;}BinTreeNode(T x){data = x;leftchild = NULL;rightchild = NULL;}
};template<class T>
class BinTree
{
public:BinTree();~BinTree();void CreateTree(BinTreeNode<T>*& t);void deleTree(BinTreeNode<T>* t);void count(BinTreeNode<T>* root, int& i, int& j, int& k);BinTreeNode<T>* Get_root(){return root;}
private:BinTreeNode<T>* root;
};template<class T>
BinTree<T>::BinTree()
{root = NULL;
}template<class T>
BinTree<T>::~BinTree()
{}template<class T>
void BinTree<T>::CreateTree(BinTreeNode<T>*& t)
{T x;cin >> noskipws >> x;if (x == '#'){t = NULL;return;}t = new BinTreeNode<T>(x);if (t == NULL)return;CreateTree(t->leftchild);CreateTree(t->rightchild);
}template<class T>
void BinTree<T>::deleTree(BinTreeNode<T>* t)
{if (t == NULL)return;deleTree(t->leftchild);deleTree(t->rightchild);delete t;
}template<class T>
void BinTree<T>::count(BinTreeNode<T>* root, int& i, int& j, int& k)
{if (root != NULL){if (root->leftchild == NULL && root->rightchild == NULL)k++;if (root->leftchild == NULL && root->rightchild != NULL || root->leftchild != NULL && root->rightchild == NULL)j++;if (root->leftchild != NULL && root->rightchild != NULL)i++;count(root->leftchild, i, j, k);count(root->rightchild, i, j, k);}
}int main()
{BinTree<char> temp;BinTreeNode<char>* head = temp.Get_root();int i = 0, j = 0, k = 0;temp.CreateTree(head);temp.count(head, i, j, k);temp.deleTree(head);cout << k << ' ' << j << ' ' << i <<' ';return 0;
}

计算二叉树结点度为0,1,2的结点个数

计算二叉树结点度为0,1,2的结点个数

【问题描述】首先利用二叉树的前序遍历建立一棵二叉树，分别用3个递归函数统计度为0，度为1和度为2的结点个数，并输出结果，这3个函数可以定义为二叉树的成员函数

【输入形式】假设二叉树的结点为字符型，输入“#”表示空结点，输入为一行字符串，具体见样例输入，二叉树见教材P202页，图5.15

【输出形式】输出只有1行，依次输出度为0的结点个数，度为1的结点个数，度为2的结点个数，3个数之间用空格分开，最后一个数据后面有一个空格，具体格式见样例输出

【样例输入】

ABC##DE#G##F###

【样例输出】

3 2 2

【样例说明】

其他测试数据：

输入：A## 输出：1 0 0

输入：AB#D##C#E## 输出：2 2 1

代码如下:

#include<iostream>using namespace std;template<class T>
struct BinTreeNode
{T data;BinTreeNode<T>* leftchild;BinTreeNode<T>* rightchild;BinTreeNode(){leftchild = NULL;rightchild = NULL;}BinTreeNode(T x){data = x;leftchild = NULL;rightchild = NULL;}
};template<class T>
class BinTree
{
public:BinTree();~BinTree();void CreateTree(BinTreeNode<T>*& t);void deleTree(BinTreeNode<T>* t);void count(BinTreeNode<T>* root, int& i, int& j, int& k);BinTreeNode<T>* Get_root(){return root;}
private:BinTreeNode<T>* root;
};template<class T>
BinTree<T>::BinTree()
{root = NULL;
}template<class T>
BinTree<T>::~BinTree()
{}template<class T>
void BinTree<T>::CreateTree(BinTreeNode<T>*& t)
{T x;cin >> noskipws >> x;if (x == '#'){t = NULL;return;}t = new BinTreeNode<T>(x);if (t == NULL)return;CreateTree(t->leftchild);CreateTree(t->rightchild);
}template<class T>
void BinTree<T>::deleTree(BinTreeNode<T>* t)
{if (t == NULL)return;deleTree(t->leftchild);deleTree(t->rightchild);delete t;
}template<class T>
void BinTree<T>::count(BinTreeNode<T>* root, int& i, int& j, int& k)
{if (root != NULL){if (root->leftchild == NULL && root->rightchild == NULL)k++;if (root->leftchild == NULL && root->rightchild != NULL || root->leftchild != NULL && root->rightchild == NULL)j++;if (root->leftchild != NULL && root->rightchild != NULL)i++;count(root->leftchild, i, j, k);count(root->rightchild, i, j, k);}
}int main()
{BinTree<char> temp;BinTreeNode<char>* head = temp.Get_root();int i = 0, j = 0, k = 0;temp.CreateTree(head);temp.count(head, i, j, k);temp.deleTree(head);cout << k << ' ' << j << ' ' << i <<' ';return 0;
}