题目要求：
二叉树算法设计
TXT文件内容（Btree.txt）：
1 2 4 8 0 0 9 0 0 5 0 0 3 6 0 0 7 0 0
一定注意，这里文件按照前序遍历的数字形式，空树按照0进行表示，每个数字间空格，这样能区分十位数还是个位数，并且只能是纯数字
代码展示：

#include<iostream>
#include<stdio.h>
#include<malloc.h>
#include<queue>
#include <string.h>
using namespace std;
typedef int ElemType;
#define MaxSize 100
char array[MaxSize];//用于存储文件当中的信息 
int str[MaxSize];
int flag=0;
int str1[MaxSize];
int cunchu[MaxSize];
int kkk=0;//数字数组分完单词后长度 
typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;int ltag,rtag;
}BiTNode,*BiTree;
BiTree CreateBiTree()//这里输入的空树是以0表示
{int e=str[flag++];//血的教训，递归的传值问题 
//   cout<<flag;BiTree T;if(e==0)T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));if(!T)return 0;T->data=e;T->lchild=CreateBiTree();T->rchild=CreateBiTree();}return T;
}
void openfile1(){//打开文件存储树的信息 FILE *fp;int i=0,len=0,temp1=0;char temp;if((fp=fopen("1.Btree.txt","r"))==NULL){cout<<"文件打开失败"<<endl; exit(0);}while(!feof(fp)){ 
//		if(fgetc(fp)=='/0')break;temp=fgetc(fp);array[i]=temp;//将字符一一存入所定义的字符串//cout<<array[i]<<" ";;i++;len++;}printf("\n");//cout<<len-1<<"hhhh"<<endl;for(int i=0;i<len-1;i++){//注意要少一位，最后的那个符号不需要 str1[i]=(int)(array[i]-'0');//cout<<str1[i]<<" ";}str1[i+1]=(int)(' '-'0');//cout<<str1[i+1]<<endl;int iii=0,jjj=0,cunchutemp=0;while(iii<len){//cout<<"OK"<<endl;if(str1[iii]==-16){cunchutemp=0;for(int i=0;i<=jjj-1;i++){cunchutemp=cunchu[i]+cunchutemp*10;//cout<<"计算的数值为"<<cunchutemp<<endl;}str[kkk]=cunchutemp;//cout<<str[kkk]<<endl;//cout<<"kkk的值为"<<kkk<<endl; kkk++;	memset(cunchu,0,sizeof(cunchu));iii++;jjj=0;}else{//cout<<"进入过一次"<<endl;cunchu[jjj]=str1[iii];jjj++;iii++;			}}printf("\n");//cout<<str1[0]<<str1[1]<<endl; for(int i=0;i<kkk+1;i++){cout<<str[i]<<" ";}return ;
}
int openfile(){//打开文件存储树的信息 FILE *fp;int i=0,len=0,temp1=0;char temp;if((fp=fopen("Btree.txt","r"))==NULL){cout<<"文件打开失败"<<endl; exit(0);}while(!feof(fp)){ 
//		if(fgetc(fp)=='/0')break;temp=fgetc(fp);array[i]=temp;//将字符一一存入所定义的字符串
//		cout<<array[i];i++;len++;}for(int i=0;i<len-1;i++){//注意要少一位，最后的那个符号不需要 str[i]=(int)(array[i]-'0');
//		cout<<str[i];}return len-1;
}
void search2(BiTree p,BiTree &q,char key)//找到值为key的结点并赋值 
{if(p!=NULL){if(p->data==key)q=p;else{search2(p->lchild,q,key);search2(p->rchild,q,key);}}
}BiTree lowestCommonAncestor(BiTree root, BiTree p, BiTree q) {//最主要的函数，找到最近的共同祖先       if(root==p||root==q||!root)return root; BiTree left=lowestCommonAncestor(root->lchild,  p, q);BiTree right=lowestCommonAncestor(root->rchild,  p, q);      if(!left&&!right)return NULL;else if(left&&!right)return left;else if(right&&!left)return right;return root;
}
void findlowestCommonAncestor(BiTree L,int ch1,int ch2){BiTree P,Q,S;P=(BiTNode*)malloc(sizeof(BiTNode));Q=(BiTNode*)malloc(sizeof(BiTNode));search2(L,P,ch1);//找到值为ch1的结点 cout<<"第一个结点的值为:"<<P->data<<endl;search2(L,Q,ch2);//找到值为ch2的结点 cout<<"第二个结点的值为:"<<Q->data<<endl;S=lowestCommonAncestor(L, P, Q);//找祖先 cout<<"最近共同祖先结点的值为:"<<S->data<<endl;
}
void preordertravels(BiTNode *b)//前序遍历 根左右 
{if(b==NULL)return;else{printf("%4d",b->data);preordertravels(b->lchild);preordertravels(b->rchild);}
}
int zisunnum[MaxSize];int ii=0;//存储子孙结点的值 
int zisunmax=0,zisunmin=10000;
void preordertravels1(BiTNode *b,BiTNode *b1)//该结点的子孙结点 
{if(b==NULL)return;else{//cout<<b->data<<b1->data<<endl;if(b->data!=b1->data){if(zisunmax<b->data) zisunmax=b->data;if(zisunmin>b->data) zisunmin=b->data;zisunnum[ii++]=b->data;		printf("%4d",b->data);	}		preordertravels1(b->lchild,b1);preordertravels1(b->rchild,b1);}
}
void inordertravels(BiTNode *b)//中序遍历 左根右 
{if(b==NULL)return;else{inordertravels(b->lchild);printf("%4d",b->data);inordertravels(b->rchild);}
}
void postordertravels(BiTNode *b)//后序遍历 左右根 
{if(b==NULL)return;else{postordertravels(b->lchild);postordertravels(b->rchild);printf("%4d",b->data);}
}
void print(BiTNode *b,int h)//打印二叉树 
{if(!b)return;print(b->rchild,h+1);//从上到下，右子树，根，左子树for(int i=0;i<h;i++)printf("        ");printf("%d\n",b->data);print(b->lchild,h+1);  
}
void menu(){printf("");printf("--------------请输入想要实现的功能--------------------\n");printf("*****************************************************\n");printf("********1、根据文本创建并显示纯数字二叉链表**********\n");printf("********2、前、中、后序遍历序列表示二叉树************\n");printf("********3、计算该二叉树不同结点个数******************\n");printf("********4、查找指点结点子孙和祖先并求最大数和最小数**\n");printf("********5、判断两个结点是否是直系亲属*****************\n");printf("********6、求出两个结点的共同祖先********************\n");printf("********7、判断其是否是完全二叉树********************\n");printf("********8、求出并显示第k层结点的个数****************\n");printf("***********退出程序请输入77**************************\n");printf("*****************************************************\n");printf("------------------------------------------------------\n");printf(" \n ");
}
void levelorder(BiTree T){
//	int ans=0;BiTree p;//建立一个暂存结点p=(BiTNode*)malloc(sizeof(BiTNode));queue<BiTree>q;//建立队列q.push(T);//头结点放入//printf("%4d",T->data);while(!q.empty()){//队列不为空一直执行//ans++;p=q.front();//取队列的第一个元素printf("%4d",p->data);q.pop();//删除第一个元素
//		cout<<p->lchild->data<<endl;
//		cout<<p->rchild->data<<endl;if(p->lchild!=NULL)//左孩子不为空入队列q.push(p->lchild);if(p->rchild!=NULL)//右孩子不为空入队列{q.push(p->rchild);//注意这里不兼容 !p->rchild//cout<<"YES"<<endl;}}
//	cout<<ans;
}
int bitrenodecount(BiTree T){//计算总结点个数 if(T==NULL)return 0;//如果是空树就返回0//这里并不是T->data==NULL 而是整个结点的值为NULL return bitrenodecount(T->lchild)+bitrenodecount(T->rchild)+1;//相加再加上根的个数
}
int bitree_key_x_number(BiTree T,int key){if(T==NULL)return 0;if(T->data==key)return 1+bitree_key_x_number(T->lchild,key)+bitree_key_x_number(T->rchild,key);return bitree_key_x_number(T->lchild,key)+bitree_key_x_number(T->rchild,key);
}
int bitreleadcount(BiTree T){ //计算叶子结点的个数 int m,n;if(T==NULL)//如果是空树就返回0return 0;if(T->lchild==NULL&&T->rchild==NULL)return 1;m=bitreleadcount(T->lchild);//计算左子树的结点个数n=bitreleadcount(T->rchild);//计算右子树的结点个数return m+n;//相加即为总叶子结点个数
} 
int zuzongmax=0,zuzongmin=1000;
int PrintAncestors(BiTree root, int x)//找打某个结点的祖宗结点 
{if (!root)  return 0;if (root->data == x)    return 1;//如果子树中可以找到匹配值 那么此节点肯定是祖先结点if (PrintAncestors(root->lchild, x) || PrintAncestors(root->rchild, x)){printf("%4d", root->data);if(root->data>zuzongmax)zuzongmax=root->data;if(root->data<zuzongmin)zuzongmin=root->data;return 1;}return 0;
}//打印祖先
int del_same(int date[],int n)//去除数组中相同的元素 
{int i,j,k=0;for(i=0;i<n;++i)//i用来遍历数组{for(j=i+1;j<n && date[i]-date[j];++j);if(!(j-n))//没有重复元素date[k++]=date[i];//可将date[]看作两个数组}return k;//返回删除后的有效长度
}void depth(BiTNode *b,int L,ElemType x,int *t)
{if(b!=NULL){L++;if(b->data==x){*t=L;}depth(b->lchild,L,x,t);depth(b->rchild,L,x,t);}
}
BiTNode *searchTree(BiTNode *b,ElemType x)
{if(b==NULL)return NULL;if(b->data==x)return b;else{if(!searchTree(b->lchild,x))return searchTree(b->rchild,x);}return b;
}
int SearchFather(BiTNode *b,ElemType x)
{if(b!=NULL){if(b->data==x)return 1;//找到父节点则返回1SearchFather(b->lchild,x);SearchFather(b->rchild,x);}else return -1;return 1;
}
//判断两个结点是否在同一条道路上面思想很简单
//首先看这两个结点是否在同一层，如果是在同一层则肯定不是一条路径
//不在同一层则看哪一个结点在的层数比较低、
//按照这个比较低的结点作为父结点，寻找另外挑一个结点
//如果找到了那么就在同一条路劲上面，没找到就不在同一条路劲上面 
int SearchIsWay(BiTNode *b,ElemType x,ElemType y)
{int d1=0,d2=0,flag;BiTNode *node=(BiTNode*)malloc(sizeof(BiTNode));//建立一个节点node用于存储x或者y的节点depth(b,0,x,&d1);depth(b,0,y,&d2);//返回得出两个节点深度大小if(d1==d2)return -1;//如果层数相等，说明是同辈，不在一条路径上，返回-1if(d1>d2){//d2小于d1,d2对应的节点则为父节点node=searchTree(b,y);//找到父节点flag=SearchFather(node,x);//从当前节点开始查找return flag;}if(d2>d1){//d1小于d2,d1对应的节点则为父节点node=searchTree(b,x);//找到父节点flag=SearchFather(node,y);//从当前节点开始查找return flag;}return flag;
}
int IsComBTree(BiTNode *b)
{if(b==NULL)return 1;BiTNode *q[MaxSize],*p;int front=-1,rear=-1;int flag1=1,flag2=1;//flag1为真说明二叉树为完全二叉树//flag2为真说明目前为止所有节点都有左右孩子if(b!=NULL){rear++;q[rear]=b;//根节点进入队列while(front!=rear)//队列不空{front++;p=q[front];if(p->lchild==NULL){flag2=0;if(p->rchild!=NULL)//没有左孩子有右孩子，说明不是完全二叉树flag1=0;}else{if(flag2){rear++;q[rear]=p->lchild;//左孩子进队if(p->rchild==NULL)flag2=0;else{rear++;q[rear]=p->rchild;}}elseflag1=0;}}return flag1;	}
}
int k_nodecount(BiTNode *b,ElemType k)
{int ans=0;//定义一个计数器int left,right;if(b==NULL || k<=0)return 0;if(b){if(k==1)return 1;left=k_nodecount(b->lchild,k-1);right=k_nodecount(b->rchild,k-1);//逐层查找return left+right;}return 0;	
}
//void _InOrderThread(BiTNode *root)//前序线索化 
//	{
//		if(root == NULL)
//			return ;
//		//左子树
//		_InOrderThread(root->lchild);
//		//根
//		if (root->lchild == NULL)
//		{
//			root->ltag=1;
//			root->lchild=_prev;
//		}
//		if (_prev  && _prev->rchild == NULL)
//		{
//			_prev->rtag=1;
//			_prev->rchild=root;
//		}
//		_prev=root;
//		//右子树
//		_InOrderThread(root->rchild);
//	}
int main()
{BiTree T;BiTree P;P=(BiTNode*)malloc(sizeof(BiTNode));openfile1();int aalength=0; int x1,x2,x3,x4,x5;T=CreateBiTree();int choosenum,searchkey,keynum;int allnode=bitrenodecount(T);int leafnode=bitreleadcount(T);int branchnode=allnode-leafnode;do{printf("\n");printf("\n");menu();cout<<"你的选择是:"; cin>>choosenum;switch(choosenum){case 1:printf("\n");cout<<"展示结果如下" <<endl;cout<<"横向展示二叉树" <<endl;print(T,0); break;case 2:printf("\n");cout<<"前序遍历结果为";preordertravels(T);printf("\n");cout<<"中序遍历结果为";inordertravels(T);printf("\n");cout<<"后序遍历结果为";postordertravels(T);printf("\n");cout<<"层次遍历结果为";levelorder(T); break;case 3:printf("\n"); cout<<"总结点数为:"<<allnode<<endl;cout<<"叶子结点数为:"<<leafnode<<endl;			cout<<"分支结点数为:"<<branchnode<<endl;cout<<"请输入要查找结点的值："<<endl;cin>>searchkey;cout<<"结点数为:"<<bitree_key_x_number(T,searchkey)<<endl;break; case 4:printf("\n"); zisunmax=0;zisunmin=1000;zuzongmax=0;zuzongmin=1000;cout<<"说明：这里是按照前序序列找到的第一个结点计算"<<endl;cout<<"请输入结点的值：";cin>>keynum;P=NULL;search2(T,P,keynum);if(P!=NULL){cout<<"该二叉树存在此结点"<<endl;if(P->lchild==NULL&&P->rchild==NULL){cout<<"但是此结点无子孙结点"<<endl;}else{cout<<"该结点的子孙有";preordertravels1(P,P);printf("\n"); cout<<"子孙中最大值为:"<<zisunmax<<endl;cout<<"子孙中最小值为:"<<zisunmin<<endl;	}if(P->data==T->data){cout<<"该结点无祖宗结点"<<endl;}else{cout<<"该结点的祖宗结点为:";PrintAncestors(T,P->data);printf("\n");  cout<<"子孙中最大值为:"<<zuzongmax<<endl;cout<<"子孙中最小值为:"<<zuzongmin<<endl;}}else{cout<<"该二叉树不存在此结点"<<endl;}break;case 5:{cout<<"请输入要判断的两个结点的值"<<endl; cin>>x1>>x2;int flag1=SearchIsWay(T,x1,x2);//cout<<flag1<<endl;if(flag1==1)cout<<"这两个结点在同一条路径上面"<<endl;else cout<<"这两个结点不在同一条路径上面"<<endl; break;}case 6:{cout<<"请输入要寻找共同祖先的两个结点的值"<<endl; cin>>x3>>x4;findlowestCommonAncestor(T,x3,x4);break;}	case 7:{int flag2=IsComBTree(T);if(flag2==1)cout<<"该二叉树是完全二叉树"<<endl;else cout<<"该二叉树不是完全二叉树"<<endl;break;}case 8:{cout<<"请输入要求个数的第K层的值"<<endl; cin>>x5;cout<<"第"<<x5<<"层的结点个数为:";cout<<k_nodecount(T,x5)<<endl;break;}default:printf("请输入正确的选择!\n");break;}}while(choosenum!=77);return 0;//	findlowestCommonAncestor(T,ch1,ch2);
//    char ch1='F',ch2='E';//输入值为ch1,ch2的两个节点 
//    getchar();
//	cout<<"请输入第一个和第二个结点值"; 
//    cin>>ch1>>ch2;
//    printf("\n");}