SWUST:统计利用二叉树存储的森林中树的棵数

￡神魔★判官ぃ 2022-01-31 15:05 155阅读 0赞

统计利用二叉树存储的森林中树的棵数  
1000(ms)  
10000(kb)  
3434 / 6642  
普通树及其构成的森林均可转换成相应的二叉树，反之亦然。故而可以根据相应的转换方法去统计某一二叉树对应的森林中树的棵数。相应的二叉树可利用先序递归遍历算法创建。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"\#“时表示该结点不需要创建，否则创建该结点。最后再统计该二叉树对应的森林中树的棵数。需要注意输入数据序列中的”\#“字符和非”\#"字符的序列及个数关系，这会最终决定创建的二叉树的形态（序列里面允许无效字符但需要正确处理）。  
输入

> **输入为接受键盘输入的由大写英文字符和"\#"字符构成的一个字符串（用于创建对应的二叉树）。**

输出

> **输出该用例对应的二叉树表示的森林中树的棵数。**

样例输入

> A\#B\#CD\#\#\#  
> ABC\#\#\#\#  
> AB\#\#C\#\#  
> ABCD\#\#\#EF\#\#G\#\#H\#\#  
> A\#\#B\#\#

样例输出

> 3  
> 1  
> 2  
> 2  
> 1

#### 树如何转换成二叉树？（引用自： ####

[https://www.cnblogs.com/xiaogua918/p/4181561.html][https_www.cnblogs.com_xiaogua918_p_4181561.html]

步骤1：仅保留最左边孩子与根节点的连线，并连接兄弟结点。如下图,B是A最左边的孩子，所以保留A与B的连线，断开A与C，A与D的连线。B、C、D是兄弟，所以将BCD连接起来。对于以B、C、D为根的子树仍然按照这样的规则转换。  
步骤2：左子树顺时针旋转45度，便得到了转换后的二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDYxMTc1_size_16_color_FFFFFF_t_70]

### 森林如何转换成二叉树？ ###

步骤1：每棵树都先转换为二叉树

步骤2：以第一棵树的根结点为根结点，将根结点依次连接起来

步骤3：按照根结点顺时针旋转45度  
![在这里插入图片描述][20190516220304742.png]

##### 代码实现 #####

//编译环境VS2013
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    
    
    typedef struct Tree
    {
    	Tree *left, *right;
    	char data;
    }T;
    void creat(T *&t)
    {
    	char a;
    	cin >> a;
    	if (a != '#')
    	{
    		t = new T;
    		t->data = a;
    		creat(t->left);
    		creat(t->right);
    	}
    	else
    		t = NULL;
    }
    int cou = 1;
    void travel(T *&t) //遍历右子树
    {
    	if (t != NULL)
    	{
    		if (t->right != NULL)
    		{
    			cou++;
    			travel(t->right);
    		}
    	}
    	else return;
    }
    int main()
    {
    	T *t;
    	creat(t);
    	travel(t);
    	cout << cou;
    }

[https_www.cnblogs.com_xiaogua918_p_4181561.html]: https://www.cnblogs.com/xiaogua918/p/4181561.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDYxMTc1_size_16_color_FFFFFF_t_70]: /images/20220131/268102e565a947539714c359ad7acace.png
[20190516220304742.png]: /images/20220131/e3fa5ce6d954431ab4619cb00760610a.png