14_2_2.cpp

王红梅编《数据结构》大多数的实验源码。内附详细的实验报告。

#include <iostream.h>

struct BiNode
{
	// 结点中的数据
	char data;
	// 左孩子和右孩子
	BiNode *lchild, *rchild;
};

/*
@ CreateTree
前置条件：	二叉树不存在
输入：		根结点和扩展前序遍历序列
功能：		建立一棵新的二叉树
输出：		二叉树根节点的指针
后置条件：	二叉树被建立
*/
BiNode *CreateTree(BiNode *root)
{
	char ch;
	cin >> ch;
	if (ch == '#')
		return NULL;
	else
	{
		root		= new BiNode;
		root->data	= ch;
		root->lchild	= CreateTree(root->lchild);
		root->rchild	= CreateTree(root->rchild);
	}
	return root;
}

/*
@ Like
前置条件：	两棵要比较的二叉树存在
输入：		两棵二叉树的根结点
功能：		比较两棵二叉树是否相似
输出：		两棵二叉树是否相似的布尔值
后置条件：	二叉树不变
*/
bool Like(BiNode *s, BiNode *t)
{
	if (s == NULL && t == NULL)
		return true;
	else if ( (s == NULL && t) || (s && t == NULL) )
		return false;
	else
	{
		bool same = Like(s->lchild, t->lchild);
		if (same)
			same = Like(s->rchild, t->rchild);
		return same;
	}
}

/*
@ DestroyTree
前置条件：	二叉树存在
输入：		二叉树的根结点
功能：		销毁二叉树
输出：		无
后置条件：	二叉树被销毁
*/
void DestroyTree(BiNode *root)
{
	if (root == NULL)
		return;
	DestroyTree(root->lchild);
	DestroyTree(root->rchild);
	delete root;
}

void main()
{
	BiNode *s, *t;
	cout << "请输入树1的扩展前序遍历：" << endl;
	s = CreateTree(s);
	cout << "请输入树2的扩展前序遍历：" << endl;
	t = CreateTree(t);
	cout << "两棵树是否相似：" << endl;
	cout << Like(s, t) << endl;
	DestroyTree(s);
	DestroyTree(t);
}