树和二叉树：二叉树的基本运算算法的实现

一.前言

当前版本仅供笔者复盘

二.二叉树

2.1题目

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

1，先序遍历输出该树（带“^"标志)。

2，中序遍历输出该树（带“^"标志)。

3，后序遍历输出该树（带“^"标志)。

4，层次遍历输出该树（带“^"标志)。

5，输出该树的先序凹入表表示法(参考附件)。

6，输出该树的中序凹入表表示法。

7，输出该树的后序凹入表表示法。

8，设计一个算法把二叉树b所有的左、右子树进行交换，并用括号表示法输出该树。（要求不破坏原二叉树）

9，（选做题）输出该树相隔最远的一对结点。（例：对图1，N与I相隔最远。提示：相隔最远不一定分别在左右两棵子树上，相隔最远是两个叶子，还有一种就是叶子与根。）

2.2知识点总结

2.2.1排序

我的总结是

#include<bits/stdc++.h>
using namespace std;
#define MAX 10000
typedef char ch;
//首先每个节点的属性如下有数据域，左右孩子
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];
	}
}
//先序遍历输出该树（带“^"标志)。
void Predisplay(BT *B1)
{
	if(B1!=NULL)
	{
		cout<<B1->data;
		Predisplay(B1->lchild);
		Predisplay(B1->rchild);
	}
	else
		cout<<"^";
}
void Indisplay(BT *B1)
{
	if(B1!=NULL)
	{
		Indisplay(B1->lchild);
		cout<<B1->data;
		Indisplay(B1->rchild);
	}
	else
		cout<<"^";
}
void Postdisplay(BT *B1)
{
	if(B1!=NULL)
	{
		Postdisplay(B1->lchild);
		Postdisplay(B1->rchild);
		cout<<B1->data;
	}
	else 
		cout<<"^";
}
void Picdisplay(BT *B1)
{
	BT *p;
	queue<BT*>q;
	q.push(B1);
	while(!q.empty()){
		if(q.front()!=NULL)
		{
			p=q.front();
			q.pop();
			cout<<p->data;
		}
		else
		{
			cout<<'^';
			q.pop();
			continue;
		}
		q.push(p->lchild);
		q.push(p->rchild);
	}
	
}
//凹凸其本质就是打印的方式变了
//顺序代码还是一样的
void Pre(BT *B1,int h,int k){   //h为高度，k为左右               
	if(B1==NULL)    //常规判断                                
		return;
	for(int i=0;i<h*3;i++)   //越深空格越多，每次规定三个空格                
		cout<<" ";
	cout<<B1->data;
	for(int j=0;j<(30-3*h);j++)   //以30*30的正方形为空间，剩余填充为=         
		cout<<"=";
	if(!h)           //打印最后的字母                               
		cout<<"B";                               
	else{
		if(k)                                        
			cout<<"L";
		else
			cout<<"R"; 
	}
	cout<<endl;
	Pre(B1->lchild,h+1,1);
	Pre(B1->rchild,h+1,0);
} 
void In(BT *B1, int h, int k){
	if(B1==NULL)
		return;
	In(B1->lchild,h+1,1);
	for(int i=0; i<h*3;i++)
		cout<<" ";
	cout<<B1->data;
	for(int j=0; j<(30-3*h);j++)
		cout<<"=";
	if(!h)
		cout<<"B";
	else{
		if(k)
			cout<<"L";
		else
			cout<<"R"; 
	}
	cout<<endl;
	In(B1->rchild,h+1,0);
} 
void Post(BT *B1, int h, int k){//h为高度，k为左右
	if(B1==NULL)
		return;
	Post(B1->lchild,h+1,1);
	Post(B1->rchild,h+1,0);
	for(int i=0; i<h*3;i++)//越深空格越多，每次规定三个空格
		cout<<" ";
	cout<<B1->data;
	for(int j=0;j<(30-3*h);j++)//以30*30的正方形为空间，剩余填充为=
		cout<<"=";
	if(!h)//打印最后的字母
		cout<<"B";
	else{
		if(k)
			cout<<"L";
		else
			cout<<"R"; 
	}
	cout<<endl;
} 
//8.设计一个算法把二叉树b所有的左、右子树进行交换，并用括号表示法输出该树。（要求不破坏原二叉树）
void Exchange(BT *B1)
{
	BT *t;///temp
	if(B1==NULL)
		return;
	else if(B1->lchild!=NULL||B1->rchild!=NULL)
	{
		t=B1->lchild;
		B1->lchild=B1->rchild;
		B1->rchild=t;
	}
	Exchange(B1->lchild);
	Exchange(B1->rchild);	
}
void Displaybtree(BT *B1){
	if(B1!=NULL)
	{
		cout<<B1->data;
		if(B1->lchild!=NULL||B1->rchild!=NULL)
		{
			cout<<"(";
			Displaybtree(B1->lchild);
			if(B1->rchild!=NULL)
				cout<<",";
			Displaybtree(B1->rchild);
			cout<<")";
		}
	}
}
//我的理解
//有两种，叶子和叶子（根的左右最深的相加不就是了吗？）
//叶子和根（这个很简单，就是深度最深的那个叶子））//但其实是错的，因为左树可以很长，所以我们的算法是寻找 共同祖先，然后相减
//不过实现起来比较棘手，就会错很多，后面请教大佬才发现（/*我蒟蒻的*/）
//这个第一步是先找叶子节点
void Findleaves(BT *B1,char a[],int &i)//a用来存节点，为了找到叶子结点
{
	if(!B1)//为了高级
		return;
	else 
	{
		if(!B1->lchild&&!B1->rchild)
			a[++i]=B1->data;	
		Findleaves(B1->lchild,a,i);
		Findleaves(B1->rchild,a,i);
	}
}
//第二部
//上一题的寻找共同祖先
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;
}
map<char,int>trees;//储存每个结点的深度
void treedeep(BT* B1,int deep){
	if(B1){
		trees[B1->data]= deep;//求出每个结点的深du
		treedeep(B1->lchild,deep+1);
		treedeep(B1->rchild,deep+1);
	}
}
void Displaynode(BT *B1)
{
	ch str1,str2;//存储最终答案
	char a[MAX];
	int num=0;
	Findleaves(B1,a,num);//把所有叶子记录在a中
	treedeep(B1,1);//计算所有节点的深度
	a[++num]=B1->data;//加上根节点
	int max=0;
	for(int i=1;i<=num;i++)//遍历
	{
		for(int j=1;j<=num;j++){
			if(i==j)//不和自己比
				continue;
			char lcp=Findsameparent(B1,a[i],a[j]);//两个叶子的共同祖先
			int len=trees[a[i]]+trees[a[j]]-2*trees[lcp];//计算路径长度
			if(len>max)
			{
				max=len;
				str1=a[i];
				str2=a[j];
			}
		}
	}
	cout<<str1<<" "<<str2<<endl;
}

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<<"1:先序遍历输出该树（带\"^\"标志):";Predisplay(B1);cout<<endl<<endl;
	cout<<"2:中序遍历输出该树（带\"^\"标志):";Indisplay(B1);cout<<endl<<endl;
	cout<<"3:后序遍历输出该树（带\"^\"标志):";Postdisplay(B1);cout<<endl<<endl;
	cout<<"4:层次遍历输出该树（带\"^\"标志):";Picdisplay(B1);cout<<endl<<endl;
	cout<<"5:该树的先序凹入表表示法:"<<endl;Pre(B1,0,1);cout<<endl<<endl;
	cout<<"6:该树的中序凹入表表示法:"<<endl;In(B1,0,1);cout<<endl<<endl;
	cout<<"7:该树的后序凹入表表示法:"<<endl;Post(B1,0,1);cout<<endl<<endl;
	cout<<"8:现在交换二叉树所有的左、右子树，输出为括号表示法：  ";Exchange(B1);
	Displaybtree(B1);cout<<endl<<endl;
	cout<<"9:该树相隔最远的一对结点: ";Displaynode(B1);
	return 0;
}