00348307江云亮hw4_0401.cpp

二叉树的最短路径

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

// 在此，我感谢李逸男，陈昊罡等同学对我的启发和帮助。下面的报告中，我还会具体地提到
// 他们在各个方法对我的帮助。
 
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。

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

// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
// 江云亮

/*文件名称：00348307江云亮hw4_0401.cpp
项目名称：二叉树结点最小距离
创建者：江云亮
创建时间：2004/10/4
最后修改时间：2004/10/5
功能： 建立一棵二叉树，给定二叉树上任意两个结点，求出两个结点的最小距离
文件中的函数名称和简单功能描述：
    char value();  返回结点的数据
    BinaryTreeNode* leftchild();  返回当前结点的左子树
	BinaryTreeNode* rightchild(); 返回当前结点的右子树
	void setLeftchild(BinaryTreeNode* l); 设置当前结点的左子树
	void setRightchild(BinaryTreeNode* r); 设置当前结点的右子树
	void setValue(char& val);  设置当前结点的数据域
    void DeleteBinaryTree(BinaryTreeNode* root);  删除二叉树的root结点（包括其左右子树）
	BinaryTreeNode* Root(); 返回二叉树根结点
	bool isEmpty(); 判断二叉树是否为空树
	BinaryTreeNode* PreOrdersearch(BinaryTreeNode* root,char val); 
	//从root结点开始前序遍历寻找数据为val的结点，并将其返回，如找不到返回空
	void Insert(char father,char child,int check); 
	//将值child建立一个结点作为值为father的结点的子结点（check=1左子结点，check=2右子结点）
	int Distance(BinaryTreeNode* root,BinaryTreeNode* p,BinaryTreeNode* q,int& len);
	//返回p，q两个结点的最小距离
文件中定义的全局变量和简单功能描述：无
文件中用到的他处定义的全局变量及其出处：无
与其他文件的依赖关系：无
*/
#include <iostream.h>

/*类名称：BinaryTreeNode
定义该类的目的：二叉树由结点的有限集合构成，二叉树结点是大部分运算的基础，这里定义的是针对二叉树
                结点运算的抽象数据类型
类属性：简单类
类中函数及功能：
    char value();  返回结点的数据
    BinaryTreeNode* leftchild();  返回当前结点的左子树
	BinaryTreeNode* rightchild(); 返回当前结点的右子树
	void setLeftchild(BinaryTreeNode* l); 设置当前结点的左子树
	void setRightchild(BinaryTreeNode* r); 设置当前结点的右子树
	void setValue(char& val);  设置当前结点的数据域
与其他类的关系（调用/被调用哪类对象中的什么函数）：被BinaryTree类调用
*/
class BinaryTreeNode //二叉树结点类
{
	friend class BinaryTree; //二叉树类为二叉树结点类的友元类
private:
	BinaryTreeNode * left;   //结点的左子结点
	BinaryTreeNode * right;  //结点的右子结点
	char element;            //二叉树结点数据域
public:
	char value(); //返回结点的值
	BinaryTreeNode* leftchild();  
	/*函数名称：BinaryTreeNode* leftchild()
	函数功能描述：返回当前结点的左子树
	函数调用之前的预备条件：树的建立，结点存在
	返回值：一个二叉树结点的指针，指向当前结点的左子树
	函数的输入参数：无
	函数的输出参数：二叉树结点指针
	*/
	BinaryTreeNode* rightchild();
	/*函数名称：BinaryTreeNode* rightchild()
	函数功能描述：返回当前结点的右子树
	函数调用之前的预备条件：树的建立，结点存在
	返回值：一个二叉树结点的指针，指向当前结点的右子树
	函数的输入参数：无
	函数的输出参数：二叉树结点指针
	*/
	void setLeftchild(BinaryTreeNode* l);
	/*函数名称：void  setLeftchild(BinaryTreeNode* l)
	函数功能描述：设置当前结点的左子树
	函数调用之前的预备条件：树的建立，结点存在
	返回值：无
	函数的输入参数：一个二叉树结点指针，指向当前结点左子树预备设置的值
	函数的输出参数：无
	*/
	void setRightchild(BinaryTreeNode* r);
	/*函数名称：void  setRightchild(BinaryTreeNode* l)
	函数功能描述：设置当前结点的右子树
	函数调用之前的预备条件：树的建立，结点存在
	返回值：无
	函数的输入参数：一个二叉树结点指针，指向当前结点右子树预备设置的值
	函数的输出参数：无
	*/
	void setValue(char& val);
	/*函数名称：void  setValue(char& val)
	函数功能描述：设置当前结点的数据域
	函数调用之前的预备条件：树的建立，结点存在
	返回值：无
	函数的输入参数：一个字符型引用，传递当前结点预备设置的数值
	函数的输出参数：无
	*/
};
char BinaryTreeNode::value()
{
	return element;           //返回数据
}

BinaryTreeNode* BinaryTreeNode::leftchild()
{
	return left;              //返回左子树
}

BinaryTreeNode* BinaryTreeNode::rightchild()
{
	return right;             //返回右子树
}

void BinaryTreeNode::setLeftchild(BinaryTreeNode* l)
{
	left=l;                   //设置左子树
}

void BinaryTreeNode::setRightchild(BinaryTreeNode* r)
{
	right=r;                  //设置右子树
}

void BinaryTreeNode::setValue(char& val)
{
	element=val;              //设置数据域
}


/*类名称：BinaryTree
定义该类的目的：二叉树由结点的有限集合构成，而二叉树的某些运算是针对整棵树的，这里定义的是针对
整棵二叉树的抽象数据类型
类属性：简单类
类中函数及功能：
    BinaryTree(char val);  构造函数，建立一个根为val的二叉树
    ~BinaryTree();  析构函数
	void DeleteBinaryTree(BinaryTreeNode* root);  删除二叉树的root结点（包括其左右子树）
	BinaryTreeNode* Root(); 返回二叉树根结点
	bool isEmpty(); 判断二叉树是否为空树
	BinaryTreeNode* PreOrdersearch(BinaryTreeNode* root,char val); 
	//从root结点开始前序遍历寻找数据为val的结点，并将其返回，如找不到返回空
	void Insert(char father,char child,int check); 
	//将值child建立一个结点作为值为father的结点的子结点（check=1左子结点，check=2右子结点）
	friend int Distance(BinaryTreeNode* root,BinaryTreeNode* p,BinaryTreeNode* q,int& len);
	//友函数，返回p，q两个结点的最小距离
与其他类的关系（调用/被调用哪类对象中的什么函数）：调用BinaryTreeNode类
*/
class BinaryTree
{
private:
	BinaryTreeNode* root;  //二叉树根结点
public:
	BinaryTree(char val);  
	/*函数名称：BinaryTree(char val)
	函数功能描述：构造函数，建立一个根为val的二叉树
	函数调用之前的预备条件：无
	返回值：无
	函数的输入参数：一个字符型，传递当前树根结点的预设数值
	函数的输出参数：无
	*/
	~BinaryTree();
	/*函数名称：~BinaryTree()
	函数功能描述：析构函数
	函数调用之前的预备条件：树存在
	返回值：无
	函数的输入参数：无
	函数的输出参数：无
	*/         
	void DeleteBinaryTree(BinaryTreeNode* root); 
     /*函数名称：BinaryTreeNode* Root()
	函数功能描述：返回二叉树的根结点
	函数调用之前的预备条件：树存在
	返回值：无
	函数的输入参数：无
	函数的输出参数：无
	*/
	BinaryTreeNode* Root();  
	/*函数名称：BinaryTreeNode* Root()
	函数功能描述：返回二叉树的根结点
	函数调用之前的预备条件：树存在
	返回值：无
	函数的输入参数：无
	函数的输出参数：无
	*/
	bool isEmpty();  
	/*函数名称：bool isEmpty()
	函数功能描述：判断二叉树是否为空树
	函数调用之前的预备条件：树存在
	返回值：空树为true，非空树为false 
	函数的输入参数：无
	函数的输出参数：布尔变量
	*/
	BinaryTreeNode* PreOrdersearch(BinaryTreeNode* root,char val);
	/*函数名称：BinaryTreeNode* PreOrdersearch(BinaryTreeNode* root,char val);
	函数功能描述：从root结点开始前序遍历寻找数据为val的结点，并将其返回，如找不到返回空
	函数调用之前的预备条件：树存在
	返回值：二叉树结点的指针，指向值为val的结点，找不到为空指针 
	函数的输入参数：根结点指针root，字符型val
	函数的输出参数：二叉树结点的指针