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;

/* 判断2棵树是否相似的递归函数
 * 接受树的结点类型为参数 
 */ 
template <typename T>
bool isSimilarAux(BTreeNode<T> *r1, BTreeNode<T> *r2) {
	if (r1 == 0 && r2 == 0) {
		return true;
	} else
	if (r1 == 0 || r2 == 0) {
		return false;
	}
	return isSimilarAux(r1->left, r2->left) &&
		   isSimilarAux(r1->right, r2->right);
} // isSimilarAux(BTreeNode<T>, BTreeNode<T>)

/* 判断2棵树是否相似，界面 
 */ 
template <typename T>
bool isSimilar(BTree<T> t1, BTree<T> t2) {
	return isSimilarAux(t1.root, t2.root);
} // isSimilar(BTree, BTree)


/* 从cin根据前序、中序遍历结果读入一棵树
 */
BTree<char> getTree();

int main() {
	
	cout << "演示2树是否相似的程序，\n"
		 << "树的输入采用上题中的给出前、中序遍历结果的方法\n"
		 << "上题说明中关于程序退出的警告仍然有效\n"
		 << endl;


	cout << "输入第一棵树: \n";
	BTree<char> tree1 = getTree();

	cout << "输入第二棵树: \n";
	BTree<char> tree2 = getTree();

	cout << "是否相似: " << (isSimilar(tree1, tree2) ? "Y" : "N") << endl;
	
	pause();
	return 0;

} // main()



/////////////////////////////////////////////////////////////////////
// 以下为getTree()的实现
/////////////////////////////////////////////////////////////////////

/* 遍历用的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>)


/* 根据前序遍历和中序遍历一颗二叉树的结果确定一颗二叉树,
 * 并返回之
 */
BTree<char> makeTree(const string& preorder, const string& inorder) {
	/* push all useful variables into the stack
	 */
	#define PUSH_ALL() {		\
		sleft.push(ileft);		\
		sright.push(iright);	\
		sinode.push(inode);		\
		snode.push(node);		\
	} while (false)

	typedef string::const_iterator SItor;
	Stack<SItor> sleft, sright, sinode;
	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 {		// 都没有，向上回溯
			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&)


/* 从cin根据前序、中序遍历结果读入一棵树
 */
BTree<char> getTree() {
	
	cout << "输入前序遍历的结果: ";
	string preorder = getString();

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

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

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

	return tree;
} // getTree()