shortest_way_main.cpp

二叉树最短路径问题

// 我真诚地保证：
    
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。

// 在此，我感谢 黄贝宁对我的启发和帮助。他对我的帮助主要是在找祖先上。
 
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。

// 我从未抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。

// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
// <学生姓名>黄冀渝 00348290

//文件名称：shortest_way_main.cpp
//项目名称：shortest_way_main.dsw
//创建者：黄冀渝
//创建时间：Sept.30 2004
//最后修改时间：Oct.6 2004
//功能： 打印给定两个结点的最短路径
 
//与其他文件的依赖关系：程序入口
#include<iostream>
#include<stdlib.h>
#include"BinaryTree.h"
using namespace std;

void check(char* a);

void main()
{
	BinaryTree<char> tree;
	cout<< "\n\n\n\t"
		<<"\t\t*  最短路径4.1  *\n"
		<<"\t请按照前序周游顺序输入一棵树,用^代表空结点\n"
		<<"\t例如abd^^^ce^^f^^代表的就是如下的树\n"
		<<"\t            a\n"
		<<"\t         /     \\ \n"
		<<"\t       b        c\n"
		<<"\t     /         /  \\ \n"
		<<"\t    d         e    f\n\n";
	char a[1000];
	cout<<"\n\t请输入表达式(前序)";
	cin.getline(a,990,'\n');
	
	check(a); //测试输入是否正确

	BinaryTreeNode<char>* root_of_tree = tree.GenerateTree(a);
	tree.Initialize(root_of_tree);

	cout<<"\n您输入的树的缩进表达式如下\n";
	tree.PreOrderPrint(tree.getRoot());

	char c1,c2;
	cout<<"\n请输入需要操作的两个结点(例如a b):  ";
	cin>>c1>>c2;
	if (!cin)
		exit(1);
	BinaryTreeNode<char>* p = tree.FindAncestor(tree.getRoot(),c1,c2);
	if (p == NULL){
		cout<<"您所输入的结点至少一个不存在!  程序退出中……\n";
		exit(1);
	}	
	cout<<"----------------------------------------\n"
		<< c1 
		<< "和" 
		<< c2 
		<< "的公共祖先是: ";
	if (p != NULL)
		cout<<p->value()<< endl;
	cout<< "----------------------------------------\n"
		<< "他们的最短路径是: ";

	BinaryTreeNode<char>* p1 = PreOrderGetPointer(tree.getRoot(),c1);
	BinaryTreeNode<char>* p2 = PreOrderGetPointer(tree.getRoot(),c2);

	tree.PrintPath(p,p1,p2);
	cout<< endl;
	//注意！！！退出主函数时会调用析构函数，请参看我写的析构函数
	//在我写的 析沟函数内已经将所有new出来的空间delete了
}

void check(char* a){
	int nEmptyLeaf = 0; //两个计数器用于判断输入的是不是正确的二叉树
	int nNode = 0;
	for (char* i = a; i[0] != '\0'; i++){
		if (*i == '^')
			nEmptyLeaf++;
		else
			nNode++;
		for (char* j = i + 1; *j != '\0'; j ++)
			if (*i == *j && *i != '^'){
				cout<< "\n\t输入中出现了重复的名称!程序退出中……\n";
				exit(1);
			}
	}
	if (nEmptyLeaf != nNode + 1){
		cout<<"\t根据书上P88性质二,您输入的恐怕不是二叉树吧(^_^)?\n\t程序退出中……";
		exit(1);
	}
}