【图论】【二叉树】以括号形式输出二叉树

问题 G(1187): 【基础算法】以括号形式输出二叉树

时间限制: 1 Sec 内存限制: 64 MB

题目描述

输入一个二叉树的先序串，输出以括号形式表示的而叉树。如果结点的子树为空，先序串的对应位置为空格符。

输入

第1行：先序串（结点数≤26，以单个大写字母表示）

输出

第1行：二叉树的括号形式

样例输入

(如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)

AB C  D

样例输出

A(B( ,C( , )),D( , ))

提示

#------------------------------------------------------------------------------#

好吧，终于写到树了。

┏┛┻━━━┛┻┓
┃||||||||||||||┃
┃　　　━　　　┃
┃　┳┛　┗┳　┃
┃　　　　　　　┃
┃　　　┻　　　┃
┗━┓　　　┏━┛
　　┃　　　┃
　　┃　　　┃
　　┃　　　┃
　　┃　　　┗━━━┓
　　┃　　　　　　　┃
　　┃草泥马也沉默了┣┓
　　┃　　　　　　　┃
　　┗┓┓┏━┳┓┏┛
　　　┃┫┫　┃┫┫

有句话说得好：

什么栈，队列，图，根本不是来帮助我们的，而是来恶心我们的……

By ZJX

好了，让我们进入正题——

首先，先讲讲惨痛的错误

LOOK!

输入

第1行：先序串（结点数≤26，以单个大写字母表示）

这红得发亮的字，就像我现在的心……

节点数小于等于26，不代表总字符数小于等于26（还有空格）！！！！！

　　　　　　　　╭⌒╮¤
　　╱◥███◣╭╭ ⌒╮
　｜田｜　面　|╰ ----╯
　｜田｜　　|　　　　说好的不犯内存问题的呢！！！？
　｜田｜　楼　|　　　　好歹也写了一篇粗心错误杂烩（原谅我打广告），还是这样(￣ε(#￣)☆╰╮(￣▽￣///)
　｜田｜　　|　　　　
　｜田｜　思　|　　　　
　｜田｜　　|　　　　
　｜田｜　过　|　　　　
　｜田｜　　　|　　　　
╬╬╬╬╬╬╬╬╬╬╬╬

---------------------我是分割线，以上都是废话------------------------

其他的倒也没什么。

读入字符后，从第一个字符开始递归。

一进递归便先输出（因为它规定空格也要输出），再判断此字符为不为空格，如果为空格，便return。

然后输出“(”，字符下标指向下一个，递归

然后输出“,”，字符下标指向下一个，递归

最后输出“)”，~~字符下标指向下一个，递归~~

最后当然不用递归了

其实有点像栈

注意：除了数组开大一点（我开的300），另外递归是不需要参数的，一个全局变量指向当前的字符即可，因为当你return过后，参数又会指向前一个字符，就会重复（甚至无限递归）。

代码：

#include<cstdio>
#include<cstring>//这东西应该只是打酱油的
char s[300];
int x=1;//你当然从零开始也行
void dfs()
{
	printf("%c",s[x]);//先输出
	if(s[x]==' ') return;//为空格（即到了叶子节点）便return
	printf("(");//左括号（引出左右儿子）
	x++; dfs();//下标移向下一个，开始递归
	printf(",");//逗号（分隔左右儿子）
	x++; dfs();
	printf(")");//右括号(……不知道怎么说了)
}
int main()
{
	fgets(s+1,300,stdin);//如果x从零开始，这里就不用+1了
	dfs();
	return 0;
}

By WZY