main.cpp

一个我的数据结构解题集合

#include <iostream>
#include <string>
#include <algorithm>		// std::find
#include <assert.h>
#include "IoUtils.h"
#include "Stack.h"
#include "BinaryTree.h"
using namespace std;

/* 将二叉树转换为前续遍历结果字符串
 */
string toPreorder(BTree<char> tree);

/* 将二叉树转换为中续遍历结果字符串
 */
string toInorder(BTree<char> tree);

/* 将二叉树转换为后续遍历结果字符串
 */
string toPostorder(BTree<char> tree);

/* 根据前序遍历和中序遍历一颗二叉树的结果确定一颗二叉树,
 * 并返回之
 */
BTree<char> makeTree(const string& preorder, const string& inorder);


int main() {
	
	cout << "输入前序遍历和中序遍历一颗二叉树的结果,\n"
		 << "给出后续遍历的结果并且链接形式储存该树(处理过程中用到, 没有演示)\n"
		 << "输入格式: 每个结点的数据场为一个英文字母, 且互不相同, 中间没有分隔符\n"
		 << "注意: 程序中没有任何额外检查，若所给出的前序和中序遍历结果无法确定一颗二叉树\n"
		 << "      将导致程序退出!\n"
		 << endl;

	cout << "输入前序遍历的结果: ";
	string preorder = getString();

	cout << "输入中序遍历的结果: ";
	string inorder = getString();

	BTree<char> tree = makeTree(preorder, inorder);

	assert( preorder == toPreorder(tree) );
	assert( inorder == toInorder(tree) );

	string postorder = toPostorder(tree);

	cout << "后续遍历结果: " << postorder << endl;
	
	pause();
	return 0;

} // main()


/* 根据前序遍历和中序遍历一颗二叉树的结果确定一颗二叉树,
 * 并返回之
 */
BTree<char> makeTree(const string& preorder, const string& inorder) {
	/* push all useful variables into the stack
	 * WARNING: MACRO, be careful in use.
	 *          a better choice is to use a struct to put all the 
	 *          variables together and use only one stack
	 */
	#define PUSH_ALL() do {		\
		sleft.push(ileft);		\
		sright.push(iright);	\
		sinode.push(inode);		\
		snode.push(node);		\
	} while (false)

	typedef string::const_iterator SItor;
	Stack<SItor> sleft, sright, sinode;			// stacks to save variables
	Stack< BTreeNode<char>* > snode;

	BTree<char> tree;
	BTreeNode<char> *node = new BTreeNode<char>(preorder[0]);			// 确定树根
	tree.root = node;
	
	SItor inode  = find(inorder.begin(), inorder.end(), preorder[0]),
		  ileft  = inorder.begin(),
		  iright = inorder.end();
	SItor itor;

	PUSH_ALL();		// 变量压栈, 宏
	int i = 1;
	while ( i < preorder.size() ) {
		if ( ( itor = find(ileft, inode, preorder[i]) ) != inode) {		// 先在左边找
			// 找到了:
			node->insertLeft(*itor);			// node就是左子树的根
			PUSH_ALL();		// 变量压栈, 宏
			node   = node->left;				// 向左走
			iright = inode;
			inode  = itor;
			++i;								// 处理下一个前序遍历结点
		} else
		if ( ( itor = find(inode+1, iright, preorder[i]) ) != iright ) {	// 在右边找
			// 找到了:
			node->insertRight(*itor);			// node就是右子树的根
			PUSH_ALL();		// 变量压栈, 宏
			node  = node->right;				// 向右走
			ileft = inode;
			inode = itor;
			++i;								// 处理下一个前序遍历结点
		} else {		// 都没有，向上回溯 ( POP_ALL(); 如果同样写成宏的话 )
			node   = snode.top();  snode.pop();
			ileft  = sleft.top();  sleft.pop();
			iright = sright.top(); sright.pop();
			inode  = sinode.top(); sinode.pop();
		}
	}

	return tree;

	#undef PUSH_ALL
} // makeTree(const string&, const string&)


/* 遍历用的functor
 */
struct Guest {
	Guest(string& str)
		: result(str) {}
	string& result;
	void operator()(char c) {
		result += c;
	}
};

/* 将二叉树转换为前续遍历结果字符串
 */
string toPreorder(BTree<char> tree) {
	string retval;
	tree.preorderTraverse(Guest(retval));
	return retval;
} // toPreorder(BTree<char>)

/* 将二叉树转换为中续遍历结果字符串
 */
string toInorder(BTree<char> tree) {
	string retval;
	tree.inorderTraverse(Guest(retval));
	return retval;
} // toInorder(BTree<char>)

/* 将二叉树转换为后续遍历结果字符串
 */
string toPostorder(BTree<char> tree) {
	string retval;
	tree.postorderTraverse(Guest(retval));
	return retval;
} // toPostorder(BTree<char>)