#endif // BITREE_H_INCLUDED
#include"Bitree.h" #include<iostream> #include<iomanip> #include<stdio.h> #include<stdlib.h> #include<string> using namespace std; void CreateTree(Bitree &bt)///前序递归构造一棵二叉树 { DataType ch; cin>>ch; if(ch=='#')///递归出口 { bt=NULL;///建立空树 return; } bt=new Node;///否则建立根结点 bt->data=ch; CreateTree(bt->lch); CreateTree(bt->rch); } const int row=5;///表示空格 const int col=30;///表示——的输出直到和空格相加满30为止 ///depath表示层次 void PrintTree(Bitree bt,int depath)///按照右子树在前先后层次输出 { if(bt==NULL)///递归的出口 return; PrintTree(bt->rch,depath+1);///先遍历右子树 int i; for(i=0;i<depath*row;i++)///输出空格 cout<<" "; cout<<bt->data; for(int k=i;k<col;k++)///输出"-" cout<<"-"; cout<<endl; PrintTree(bt->lch,depath+1);///先遍历右子树 } void PrintTree(Bitree bt )///包装上面包装上面层次输出子树的函数，屏蔽掉多余的参数 { PrintTree( bt,1); } /**算法思想是：将树的结点放在A【i】中 然后结点总共有n个；完全二叉树是当根存放在i； 左子树存放于2i+1；右子树存放于2i+2；*/ void LinkListArray(Bitree &bt,DataType A[],int n,int i)///将二叉树链表表示的的完全二叉树转换为二叉树的顺序表示 { if(bt==NULL)///递归的出口 return; if(i>=n)///空间不足的时候退出 exit(1); A[i]=bt->data; LinkListArray(bt->lch, A, n,2*i+1); LinkListArray(bt->rch, A, n,2*i+2); } /**已知一棵树具有n个结点的完全二叉树被顺序存储在T【n】中， 写出打印出编号为i的结点的父节点和所有子女*/ void Father_Child(DataType A[],int n,int i)///注意，这里的i是从0开始存放的 { if((i-1)/2>0)///该节点的父节点 cout<<"\t第"<<i<<"结点的父节点是：<"<<A[(i-1)/2]<<">"<<endl<<endl; else cout<<"\t第"<<i<<"结点没有父节点"<<endl<<endl; if((2*i+1)<n)///该节点的左孩子 cout<<"\t第"<<i<<"结点的左孩子节点是：<"<<A[(2*i)+1]<<">"<<endl<<endl; else cout<<"\t第"<<i<<"结点没有左孩子节点"<<endl<<endl; if((2*i+2)<n)///右孩子 cout<<"\t第"<<i<<"结点的右孩子节点是：<"<<A[2*i+2]<<">"<<endl<<endl; else cout<<"\t第"<<i<<"结点没有右孩子节点"<<endl<<endl; } /**设一棵二叉树以二叉链表作为他的存储表示，编写一个key（lch，rch） 输出二叉树各个节点，其中key是根结点的数据，lch和rch是括号形式的 左子树和右子树，要求空树不打印出任何信息，一个节点的树打印形式是 x，而不应该是（x, )的形式。 **/ void Print_KeyBinTree(Bitree bt)///类似前序遍历 { if(bt==NULL)///递归的出口 return; cout<<bt->data;///先输出根 if(bt->lch||bt->rch) { cout<<"("; Print_KeyBinTree(bt->lch);///左子树遍历完了 if(bt->rch)///进行判断右子树 cout<<","; Print_KeyBinTree(bt->rch); cout<<")"; } } /*Node *Parent(Bitree bt,Bitree p)///求指定节点的父节点 { if(bt==NULL)///如果是空树，返回空树 return NULL; if(bt==p)///如果根刚好等于p则无父节点 return NULL; if(bt->lch==p||bt->rch==p) return bt; Node *q=Parent( bt->lch, p); if(q!=NULL)///找到了 return q; else return Parent( bt->rch, p); }*/ /**分别先统计左子树和右子树度为1； 然后在判断根的度是否满足条件，满足则加上1 */ int Degrees_1(Bitree bt)///统计度为1的节点个数 { if(bt==NULL)///空树则返回0 return 0; if((bt->lch==NULL&&bt->rch!=NULL)||(bt->lch!=NULL&&bt->rch==NULL))///如果根只有左子树或者右子树时 return 1+Degrees_1(bt->lch)+Degrees_1(bt->rch); else return Degrees_1(bt->lch)+Degrees_1(bt->rch); } int Degrees_2(Bitree bt)///统计度为2的节点个数 { if(bt==NULL) return 0; if(bt->lch&&bt->rch) return 1+Degrees_2( bt->lch)+Degrees_2( bt->rch); else return Degrees_2( bt->lch)+Degrees_2( bt->rch); } int Height(Bitree bt)///求二叉树的高度 { if(bt==NULL) return 0; int LeftHeight=Height(bt->lch); int ReftHeight=Height(bt->rch); return 1+((LeftHeight>ReftHeight)?LeftHeight:ReftHeight); } /*int Level(Bitree bt,Bitree p,int depth)///求二叉树指定的结点所在的层次 { if(bt==NULL) return 0; if(bt==p)///如果根刚好等于p时，则返回当前的层次 return depth; int q=Level(bt->lch, p,depth+1); if(q>0) return q; else return Level(bt->rch, p,depth+1); }*/ void Delete(Bitree &bt)///删除二叉树中所有的叶子节点 { if(bt==NULL) return; if(bt->lch==NULL&&bt->rch==NULL) { delete bt; bt=NULL; } else { Delete(bt->lch); Delete(bt->rch); } } void Reflect(Bitree bt)///交换以t为根的二叉树中的每个节点的子女 { if(bt==NULL) return; Reflect( bt->lch); Reflect( bt->rch); Node *p=new Node; p=bt->lch; bt->lch=bt->rch; bt->rch=p; } void PrePrint(Bitree bt,int depath)///以前序次序输出一棵二叉树所有节点的数据值及结点所在的层次 { if(bt==NULL) return; cout<<"\t<"<<bt->data<<"--"<<depath<<">"<<setw(5); PrePrint( bt->lch,depath+1); PrePrint( bt->rch,depath+1); } void CreatPre_In(Bitree &bt,DataType pre[],int preL,int preR,DataType in[],int inL,int inR)///以前序和中序还原一棵二叉树 { if(preL>preR)///为空的时候，构造空树 { bt=NULL; return; } bt=new Node; bt->data=pre[preL];///建立根 int i; for(i=0;i<inR;i++)///去找中序根所在的位置 if(in[i]==pre[preL]) break; CreatPre_In( bt->lch, pre , preL+1 , i-inL+preL, in , inL, i-1);///建立左子树 CreatPre_In( bt->rch, pre , i-inL+preL+1, preR , in , i+1, inR);///建立右子树 } void CreatPost_In(Bitree &bt,DataType post[],int postL,int postR,DataType in[],int inL,int inR)///以后序和中序还原一棵二叉树 { if(postL>postR)///为空的时候，构造空树 { bt=NULL; return; } bt=new Node; bt->data=post[postR];///建立根 int i; for(i=0;i<inR;i++)///去找中序根所在的位置 if(in[i]==post[postR]) break; CreatPost_In( bt->lch, post , postL , i-inL+postL-1, in , inL, i-1);///建立左子树 CreatPost_In( bt->rch, post , i-inL+postL, postR-1 , in , i+1, inR);///建立右子树 } /**输出从根结点出发 到指定结点,依次经过的祖先(即路径) * 即简化版的“迷宫"，走过不用标记；t的下一步只有 * 各祖先的指针存入 path[1...depth-1]， * bt 待查二叉树 * elem 待查元素值 * depth为当前长度,( 也即当前结点深度(根为第1层) ) count为个数 **/ Node *path[100];///记录当下路过的结点 void Find_Print(Bitree bt,DataType elem,int depth )///(前序) { if(bt==NULL) return; path[depth]=bt;///把路过的根保留下来 if(bt->data==elem) { for(int i=1;i<depth;i++) cout<<"\t<"<<path[i]->data<<">"; return; } Find_Print( bt->lch, elem, depth+1); Find_Print( bt->rch, elem, depth+1); } Node *Pre_Search_K(Bitree bt,int &count,int k)///利用前序遍历的求前序序列的第k个节点 { if(bt==NULL)///递归的出口 return NULL; count++; if(count==k) return bt; Node *p=Pre_Search_K( bt->lch,count,k); if(p) return p; else return Pre_Search_K( bt->rch,count,k); } ///输出从根结点出发到指定结点,依次经过的祖先(即路径)的个数，《以前序的方式》 int Find_Print_Num(Bitree bt,DataType elem,DataType path[],int depth ,int &count) { if(bt==NULL) return 0; path[depth-1]=bt->data;///根记录下来 if(bt->data==elem) { count=depth; return count; } int n=Find_Print_Num( bt->lch, elem, path , depth+1 , count); if(n>0) return n; else return Find_Print_Num( bt->rch, elem, path , depth+1 , count); } int Find_Print_Num(Bitree bt,DataType elem,DataType path[] ,int &count) { return Find_Print_Num( bt,elem, path ,1 ,count); } /**利用前序遍历求任意指定的两个节点pq间的路径及路径长度; len是返回路径长度 pa【n】是返回结点之间的路径 */ const int n=10; void PathLength(Bitree bt,DataType p,DataType q,DataType pa[],int &len)///这里借助函数 Find_Print { int i,j,k ,p1,q1; DataType path1[n];///记录p的祖先 DataType path2[n];///记录q祖先 Find_Print_Num( bt,p, path1 ,p1);///从根到p的祖先path1及个p1 Find_Print_Num( bt,q, path2 ,q1);///从根到p的祖先path2及个q1 if(!p||!q)///至少有一个不在树中 { len=0;///则没有路径 return; } for(i=0;i<p1&&i<q1;i++)///跳过共同的祖先 if(path1[i]!=path2[i]) break; for(j=p1-1,k=0;j>=i-1;j--,k++)///连接节点间的路径 { pa[k]=path1[j]; cout<<"\t"<<pa[k]; } for(j=i;j<q1;j++,k++) { pa[k]=path2[j]; cout<<"\t"<<pa[k]; } len=k; cout<<endl<<endl<<"\t输出两点之间的路径长度为:"<<len; } ///利用二叉树的后序遍历求二叉树的高度，并判断二叉树是否平衡 ///平衡是指二叉树中任一结点的左右子树高度的差绝对值不能超过1 int HeightBlance(Bitree bt) { if(bt==NULL) return 0; int Lheight= HeightBlance( bt->lch); int Rheight= HeightBlance( bt->rch); return 1+((Lheight>Rheight)?Lheight:Rheight); if(Lheight-Rheight<=1||Lheight-Rheight>=-1) { cout<<endl<<endl<<"\t该树是平衡二叉树"; return 1; } else { cout<<endl<<endl<<"\t该树不是平衡二叉树"; return 0; } } #include<string> #include<stdio.h> #include<iomanip> #include<iostream> #include <windows.h> #include <time.h> #include"Bitree.h" using namespace std; int main() { DataType A[11]; Bitree bt3=NULL; ///输入的时候是这样构造完全二叉树的【A B C I # # J # # D K # # L # # E F H # # # G # #】 cout<<"\t温馨提示：：请输入你需要构造的完全二叉树【bt3】:"<<endl<<endl; CreateTree(bt3); cout<<endl<<endl<<"\t输出构造好的【bt3】完全二叉树如下:"<<endl; PrintTree(bt3); cout<<endl<<endl<<"\t输出【bt1】二叉树链表表示的完全二叉树转换为二叉树的顺序表示如下:"<<endl<<endl; LinkListArray(bt3,A,12,0); PrintTree(bt3); cout<<endl<<endl; Father_Child(A ,12,1); freopen("data.in","r",stdin); Bitree bt; CreateTree(bt); cout<<endl<<endl<<"\t输出构造好的【bt】二叉树如下:"<<endl; PrintTree(bt); cout<<endl<<endl<<"\t输出Key(lch,rch)类型:"<<endl<<endl; Print_KeyBinTree( bt); cout<<endl<<endl<<"\t输出该二叉树度为1的节点个数为:"<<Degrees_1(bt); cout<<endl<<endl<<"\t输出该二叉树度为2的节点个数为:"<<Degrees_2(bt); cout<<endl<<endl<<"\t输出该二叉树高度为:"<<Height(bt); /*Node *p=new Node; p->data='C'; if(Parent( bt,p)==NULL) cout<<endl<<endl<<"无"; else cout<<Parent( bt, p)->data;*/ /*Node *p=new Node; p->data='C'; cout<<endl<<endl<<Level( bt, p,1);*/ Reflect(bt);///交换以t为根的二叉树中的每个节点的子女 cout<<endl<<endl<<"\t输出以交换【bt】为根的二叉树中的每个节点的子女如下:"<<endl<<endl; PrintTree(bt); cout<<endl<<endl<<"\t输出以前序次序输出【bt】二叉树所有节点的数据值及结点所在的层次如下:"<<endl<<endl; PrePrint(bt,1); cout<<endl<<endl<<endl<<"\t输出以前序和中序还原【bt1】二叉树如下:"<<endl<<endl; Bitree bt1; DataType pre[]="ABDHEFCIGJK"; DataType in1[]="HDBEFAICJGK"; CreatPre_In( bt1, pre ,0,10, in1 ,0,10); PrintTree(bt1); cout<<endl<<endl<<endl<<"\t输出以后序和中序还原【bt2】二叉树如下:"<<endl<<endl; Bitree bt2; DataType post[]="HDFEBIJKGCA"; DataType in2[]="HDBEFAICJGK"; CreatPost_In( bt2, post ,0,10, in2 ,0,10); PrintTree(bt2); cout<<endl<<endl<<endl<<"\t输出从根结点出发到【K】结点,依次经过的祖先(即路径)如下:"<<endl<<endl; Find_Print(bt2,'K',1); Delete(bt); cout<<endl<<endl<<endl<<"\t输出删去【bt】二叉树的叶子节点后变为如下:"<<endl<<endl; PrintTree(bt); int count=0; Node *p= Pre_Search_K( bt,count,3); cout<<endl<<endl<<endl<<"\t输出利用前序遍历的求前序序列的第k个节点如下:"<<"<"<<p->data<<">"<<endl<<endl; DataType path[10]; int count1=0; cout<<endl<<endl<<"\t输出从根结点出发到【D】结点,依次经过的祖先(即路径)的个数:"<<Find_Print_Num( bt2,'D', path, count1); DataType pa[10]; int len; cout<<endl<<endl<<endl<<"\t输出两点之间A---K的路径如下:"; PathLength( bt2,'A','K', pa ,len); cout<<endl<<endl<<"\t利用二叉树的后序遍历求二叉树的高度，并判断二叉树是否平衡:"<<HeightBlance(bt2); return 0; system("csl"); }
