main.cpp

5. 定义二叉树两个结点的最小距离为这两个结点的最近公共祖先分别到这两个结点的路径长度之和。请设计一种方法

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <queue>

using namespace std;

struct BTreeNode
{
	BTreeNode* left;
	BTreeNode* right;
	BTreeNode* parent;
	string data;
	int ld;
	int rd;
	BTreeNode(BTreeNode* pl=NULL, BTreeNode* pr=NULL, BTreeNode* pp=NULL, string d="", int l=-1, int r=-1)
		:left(pl),right(pr),parent(pp),data(d),ld(l),rd(r){}
};

class BTree
{
public:
	BTree(BTreeNode* r = NULL, map<string,BTreeNode*>* n = NULL):root(r),nodes(n)
	{
		nodes = new map<string,BTreeNode*>;
	}

	~BTree()
	{
		delete nodes;
	}

	void creatTree()
	{
		vector<string> v1,v2;
		string word;
		cout<<"请先任意创建一棵二叉树\n";
		cout<<"请输入先序列（以@符号结束）：";
		while(cin>>word,word!="@")
			v1.push_back(word);
		cout<<"请输入中序列（以@符号结束）：";
		while(cin>>word,word!="@")
			v2.push_back(word);
		root = create(NULL, v1,v2,v1.begin(),v1.end()-1,v2.begin(),v2.end()-1);
	}


	int getDist(string s1, string s2)
	{
		BTreeNode* ps1 = getPointer(s1);
		BTreeNode* ps2 = getPointer(s2);
		BTreeNode* temp = ps1;
		int dist = 0;
		while (temp!=NULL)
		{
			temp->ld = dist;
			temp = temp->parent;
			dist++;
		}
		temp = ps2;
		dist = 0;
		while (temp!=NULL)
		{
			if (temp->ld!=-1)
				return temp->ld + dist;
			temp->ld = dist;
			temp = temp->parent;
			dist++;
		}
	}

	void show()
	{
		showTree(root, 0);
	}

private:
	BTreeNode* root;
	map<string,BTreeNode*>* nodes;

	BTreeNode* getPointer(string s)
	{
		return (*nodes)[s];
	}

	void showTree(BTreeNode* r, int lev)
	{
		if (r!=NULL)
		{
			showTree(r->right, lev+1);
			for (int i = 0; i < lev; i++)
				cout<<"	";
			cout<<r->data<<endl;
			showTree(r->left, lev+1);
		}
	}

	BTreeNode* create(BTreeNode* p,vector<string>& v1, vector<string>& v2,
		vector<string>::const_iterator v11, vector<string>::const_iterator v12,
		vector<string>::const_iterator v21, vector<string>::const_iterator v22)
	{
		if (v11 > v12) return NULL;
		else if (v11==v12)
		{
			BTreeNode* parent = new BTreeNode(NULL,NULL,p,*v11);
			nodes->insert(make_pair(*v11,parent));
			return parent;
		}
		else
		{
			vector<string>::const_iterator i = v11;
			int index=0;
			for (vector<string>::const_iterator t = v21; t!= v22; t++,index++)
				if (*t == *i)
					break;
			BTreeNode* parent = new BTreeNode(NULL,NULL,p,*i);
			nodes->insert(make_pair(*i,parent));
			BTreeNode* left = create(parent,v1, v2, i+1, i+index, v21, v21+index-1);
			BTreeNode* right = create(parent,v1, v2, i+index+1, v12, v21+index+1, v22);
			parent->left=left;
			parent->right=right;
			return parent;
		}
	}
};

int main(int argc, char* args[])
{
	bool stop = false;
	while (!stop)
	{
		BTree bt;
		bt.creatTree();
		cout<<"树形显示：\n";
		bt.show();
		string s1,s2,t;
		cout<<"请分别输入两结点（分别代表左右两个结点）：";
		cin>>s1>>s2;
		cout<<"这两点的最小距离为："<<bt.getDist(s1,s2)<<endl;
		cout<<"再试一次？（Y）不试？（任意其它键）\n";
		if (cin>>t,t!="Y")
			break;
	}
	return 0;
}