// 我真誠地保證：
    
// 我自己獨立地完成了整個程序從分析、設計到編碼的所有工作。
// 如果在上述過程中，我遇到了什么困難而求教于人，那么，我將在程序實習報告中
// 詳細地列舉我所遇到的問題，以及別人給我的提示。

// 在此，我感謝 黃貝寧對我的啟發和幫助。他對我的幫助主要是在找祖先上。
 
// 我的程序里中凡是引用到其他程序或文檔之處，
// 例如教材、課堂筆記、網上的源代碼以及其他參考書上的代碼段,
// 我都已經在程序的注釋里很清楚地注明了引用的出處。

// 我從未抄襲過別人的程序，也沒有盜用別人的程序，
// 不管是修改式的抄襲還是原封不動的抄襲。

// 我編寫這個程序，從來沒有想過要去破壞或妨礙其他計算機系統的正常運轉。
    
// <學生姓名>黃冀渝 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);
	}
}