【问题描述】

假设二叉树采用二叉链存储结构存储。设计一个算法，输出从每个叶子结点到根结点的逆路径

【输入形式】

广义表表示的二叉树，结点元素类型为字符，例如：a( b( c ( d, e ) ), f( g, h( i, j) ) )

【输出形式】

从左至右，从上至下，依次打印每一个叶子节点到根节点的逆路径，元素间以空格隔开。每一叶子结点单独输出一行。

【样例输入】

a(b(c(d,e)),f(g,h(i,j))), 字符中间不含有空格

【样例输出】

d c b a

e c b a

g f a

i h f a 

j h f a
【样例说明】

叶子节点的输出顺序按中序遍历顺序依次输出
【评分标准】

#include<iostream>
#include<stack>
using namespace std;

class BinTree {
private:
	struct BinNode{
		char data;						//节点数据
		BinNode* lchild, *rchild;		//左右孩子
	};
	BinNode* root;			//根节点	
	stack<char>st;			//保存路径信息

public:
	//初始化
	BinTree() {
		root = new BinNode;
		root->data = '0';
		root->lchild = NULL;
		root->rchild = NULL;
	}

	//输入并创建二叉树
	BinNode* init() {
		char ch; char ch2;
		cin >> ch;
		if (ch == '(' || ch == ')'||ch==',') {
				ch2 = ch;
			}
		else {
				cin >> ch2;
			}
		if (root->data == '0') {
			root->data = ch;
			root->lchild = init();

			//这一段代码十分冗余，但是它能跑起来。
			cin >> ch;
			if (ch != ',' && ch != '(' && ch != ')') {
				cin >> ch2;
				if (ch2 == ')') {
					BinNode* p = new BinNode;
					p->data = ch;
					p->lchild = NULL;
					p->rchild = NULL;
					root->rchild = p;
				}
				else {
					BinNode* p = new BinNode;
					p->data = ch;
					p->lchild = init();
					p->rchild = init();
					root->rchild = p;
				}
			}
			else {
				while (ch != ',')cin >> ch;
				root->rchild = init();
			}
			//那就不要再管啦。

		}
		else {
			if (ch2 == ',' || ch2 == ')'||ch2=='\n') {
				if (ch == ',' || ch == ')' || ch == '(') {
					return NULL;
				}
				else {
					BinNode* p = new BinNode;
					p->data = ch;
					p->lchild = NULL;
					p->rchild = NULL;
					return p;
				}
			}
			else {
				BinNode* p = new BinNode;
				p->data = ch;
				p->lchild = init();
				p->rchild = init();
				return p;
			}		
		}
		return NULL;
	}

	//按要求查找输出
	void search(BinNode *root) {
		if (root!=NULL) {
			st.push(root->data);
			if (root->lchild == NULL && root->rchild == NULL) {
				stack<char>bin = st;
				while (!bin.empty()) {
					cout << bin.top() << " ";
					bin.pop();
				}
				cout << endl;
			}
			else {
				search(root->lchild);
				search(root->rchild);
			}
			st.pop();

		}
	}

	void print() {
		search(this->root);
	}
};

int main() {
	BinTree T;
	T.init();
	T.print();
}