1. (简答题)

       编写一个程序，实现二叉树的基本运算，具体要求如下：（指定示范实例1：P243图7.34。指定示范实例2：P201图7.13 ）

1，括号表示法输出该树。

2，输入一个结点的值，输出该结点的左，右孩子的值。（要能测试错误数据）

3，输出该二叉树的高度。

4，输出该二叉树结点的个数。

5，输出该二叉树双分支结点的个数。

6，输出该二叉树单分支结点的个数。

7，输出该二叉树叶子结点的个数。

8，输出该二叉树的宽度。（宽度为每层结点数的最大值）

9，（选做题）任意给定该二叉树的两个结点，输出它们的最近的公共祖先。（例：对P243图7.34，输入J， N，它们的祖先是H，E，B，A，最近的祖先是H。  另外一组测试数据为：L,E的公共祖先是：E。 ）

10，销毁该二叉树。

//二叉树
#include<bits/stdc++.h>
using namespace std;
#define MAX 10000
#define MIN -1
typedef char ch;
int ans=MIN,w[100]={0};//假设这课树的高度不超100
//首先每个节点的属性如下有数据域，左右孩子
typedef struct BTnode
{
	ch data;
	struct BTnode *lchild;
	struct BTnode *rchild;
}BT;//注意这个是节点的定义
//解读树,用二叉链的形式
void CreatBtree(BT *&B1,ch *str)//输入我们创建的树和树的括号表示法
{//B1是我们的树，str是括号表示法的那串字符
	BT *st[MAX],*p;//B作为一个顺序栈。p就是我们扫描的元素
	int top=-1,k,j=0;ch l;//top是表示栈顶，k表示左右孩子，j是遍历a用的
	B1=NULL;
	l=str[j];
	while(l!='\0'){
		//总结一下：（入栈（表示这条分支的开始），）退栈（因为结束了），遇到元素就创建节点，
		//遇到逗号改k（左右孩子），见下面的注释一
		switch (l) {
		case '(':top++;st[top]=p;k=1;break;
		case ')':top--;break;
		case ',':k=2;break;
		default:
			p=new BT;
			p->data=l;
			p->lchild=p->rchild=NULL;
			if(B1==NULL)//头结点
				B1=p;
			else
			{
				switch (k) {
				case 1:st[top]->lchild=p;break;
				case 2:st[top]->rchild=p;break;
				}
			}
		}
		j++;
		l=str[j];
	}
}
//以值找p
BT *Findmyposition(BT *B1,ch str)
{
	BT *p;
	if(B1==NULL)//空树找不到
		return NULL;
	else if(B1->data==str)//根是的话就返回根
		return B1;
	else{//否则开始递归找（先搜索左）
		p=Findmyposition(B1->lchild,str);
		//p如果最后为空，说明没找到 ，那就找右节点
		//如果找到就不找了
		if(p!=NULL)
			return p;
		else
			return Findmyposition(B1->rchild,str);
	}
	
}
//寻找左右孩子
BT *Lchildnode(BT *p)//返回一个地址
{
	return p->lchild;//理解上面创建的过程就可以理解这个
}
BT *Rchildnode(BT *p)
{
	return p->rchild;
}
//高度
int BTheight(BT *B1)
{
	int l,r;
	if(B1==NULL)
		return 0;
	else
	{
		l=BTheight(B1->lchild);
		r=BTheight(B1->rchild);
		return ((l>r)?l+1:r+1);	
	}
}
//节点数
int BTcount(BT *B1)
{
	if(B1==NULL)
		return 0;
	else
		return BTcount(B1->lchild)+BTcount(B1->rchild)+1;
}
int BTdoublecount(BT *B1)
{
	if(B1==NULL)
		return 0;
	else if(B1->lchild!=NULL&&B1->rchild!=NULL)
		return BTdoublecount(B1->lchild)+BTdoublecount(B1->rchild)+1;
	else
		return BTdoublecount(B1->lchild)+BTdoublecount(B1->rchild);
}
int BTsinglecount(BT *B1)
{
	if(B1==NULL)
		return 0;
	else if((B1->lchild!=NULL&&B1->rchild!=NULL)||(B1->lchild==NULL&&B1->rchild==NULL))
		return BTsinglecount(B1->lchild)+BTsinglecount(B1->rchild);
	else
		return BTsinglecount(B1->lchild)+BTsinglecount(B1->rchild)+1;
}
int BTleavescount(BT *B1)
{
	if(B1==NULL)
		return 0;
	else if(B1->lchild==NULL&&B1->rchild==NULL)
		return BTleavescount(B1->lchild)+BTleavescount(B1->rchild)+1;
	else
		return BTleavescount(B1->lchild)+BTleavescount(B1->rchild);
}
//宽度计算
int BTwcount(BT *B1,int h)
{
	if(B1==NULL)
		return 0;
	w[h]++;
	ans=((w[h]>ans)?w[h]:ans);
	BTwcount(B1->lchild,h+1);
	BTwcount(B1->rchild,h+1);
	return ans;
}
bool Findallparent(BT *B1,ch str,stack<ch>&s1)
{
	if(B1==NULL)
		return false;
	s1.push(B1->data);
	if(B1->data==str)//为什么这样子，根据题目提示，本身也可以是祖先，所以我们把本身也压入.
		return true;//找到了就结束
	bool flag=Findallparent(B1->lchild,str,s1);//没搜索到本点就继续
	if(flag)
		return true;//如果在左支找到了，退出
	flag=Findallparent(B1->rchild,str,s1);//否则右支
	if(flag)
		return true;
	s1.pop();//没找到就回溯
	return false;
}
//寻找最近共同祖先
ch Findsameparent(BT *B1,ch str1,ch str2)
{
	stack<ch> s1,s2;
	Findallparent(B1,str1,s1);
	Findallparent(B1,str2,s2);
	int p1=s1.size(),p2=s2.size();
	if(p1>p2)//令两栈位于同一层
	{
		int n=p1-p2;
		while(n){
			s1.pop();
			n--;
		}
	}
	else
	{
		int n=p2-p1;
		while(n){
			s2.pop();
			n--;
		}
	}
	while(s1.top()!=s2.top())
	{
		s1.pop();s2.pop();
		if(s1.top()==s2.top())
			return s1.top();
	}
	if(s1.top()==s2.top())
		return s1.top();
	return 0;
}
//销毁
void DestroyBTree(BT *&B1)
{
	if(B1!=NULL)
	{//从根出发开始删除
		DestroyBTree(B1->lchild);
		DestroyBTree(B1->rchild);
		delete B1;
	}
}
int main()
{
	int n;BT *B1;
	B1=new BT;ch a[MAX];
	cout<<"请选择您要测试的样例（输入1或2）";
	cin>>n;cout<<endl;
	if(n==1){
		cout<<"1.括号表示法表示这个树(样例一)：A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))"<<endl<<endl;
		strcpy(a, "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))");
	}
	else if(n==2){
		cout<<"1.括号表示法表示这个树（样例二）：A(B(D(,G),),C(E,F))"<<endl<<endl;
		strcpy(a, "A(B(D(,G),),C(E,F))");
	}
	else
	{
		cout<<"WARNING:what are you doing?"<<endl<<endl<<"输入1或2，ok？"<<endl<<endl;//防伪标识
		return 1;
	}
	CreatBtree(B1,a);
	//输入一个节点值，输出左右孩子
	cout<<"2.请您输入您要查询的节点的值：";
	ch o;cin>>o;cout<<endl;
	BT *p=Findmyposition(B1,o);
	if(p==NULL)
		cout<<"您的输入错误，该树无此结点！"<<endl<<endl;
	else{ 
	BT *k=Lchildnode(p);
	if(!k)
		cout<<o<<"无左孩子!"<<endl<<endl;
	else
		cout<<o<<"的左孩子是:"<<k->data<<endl<<endl;
	k=Rchildnode(p);
	if(!k)
		cout<<o<<"无右孩子!"<<endl<<endl;
	else
		cout<<o<<"的右孩子是:"<<k->data<<endl<<endl;
	}
	//输出高度
	cout<<"3.该二叉树的高度为："<<BTheight(B1)<<endl<<endl;
	cout<<"4.该二叉树的节点个数为："<<BTcount(B1)<<endl<<endl;
	cout<<"5.该二叉树双分支结点的个数:"<<BTdoublecount(B1)<<endl<<endl;
	cout<<"6.该二叉树单分支结点的个数:"<<BTsinglecount(B1)<<endl<<endl;
	cout<<"7.该二叉树叶子结点的个数:"<<BTleavescount(B1)<<endl<<endl;
	cout<<"8.该二叉树的宽度:"<<BTwcount(B1,0)<<endl<<endl;
	cout<<"9.请输入二叉树的两个结点：";ch h,x;cin>>h>>x;cout<<endl;
	cout<<"它们的最近的公共祖先是:"<<Findsameparent(B1,h,x)<<endl<<endl;
	cout<<"是否继续？(0退出，1继续)";int y;cin>>y;cout<<endl;
	while(y){
		cout<<"9.请输入二叉树的两个结点：";cin>>h>>x;cout<<endl;
		cout<<"它们的最近的公共祖先是:"<<Findsameparent(B1,h,x)<<endl<<endl;
		cout<<"是否继续？(0退出，1继续)";cin>>y;cout<<endl;
		
	}
	//销毁二叉树
	DestroyBTree(B1);
	cout<<"10.销毁二叉树成功！！！"<<endl<<endl;
	return 0;
} 


//我的蒟蒻见解
//注释一：我对（的理解是递归中根的确立，先放到栈顶，在未遇到）之前他的左孩子就接到栈顶的
//左指针域，右孩子接到右指针域，如果是左孩子遇到了（那就左孩子入栈，继续这样子的步骤，直到遇到
//）表示结束最近的那个根的左右寻找，然后一步一步回去，类似dfs不完全像，我做了个图，可以参考一下！
//发现了一个技巧，字母后面的（直接看出这个字母进栈的标志)