二叉树所有相关遍历的算法

xiaoxiao2021-02-28  10

#ifndef BITREE_H_INCLUDED #define BITREE_H_INCLUDED typedef char DataType; typedef struct Node {     DataType data;     struct Node *lch;     struct Node *rch; }Node,*Bitree; void CreateTree(Bitree &bt);///前序递归构造一棵二叉树 void PrintTree(Bitree bt,int depath);///按照右子树在前先后层次输出 void PrintTree(Bitree bt);///包装上面层次输出子树的函数,屏蔽掉多余的参数 void LinkListArray(Bitree &bt,DataType A[],int n,int i);///将二叉树链表表示的的完全二叉树转换为二叉树的顺序表示 void Father_Child(DataType A[],int n,int i); /**已知一棵树具有n个结点的完全二叉树被顺序存储在T【n】中, 写出打印出编号为i的结点的父节点和所有子女 */ void Print_KeyBinTree(Bitree bt); /**设一棵二叉树以二叉链表作为他的存储表示,编写一个key(lch,rch) 输出二叉树各个节点,其中key是根结点的数据,lch和rch是括号形式的 左子树和右子树,要求空树不打印出任何信息,一个节点的树打印形式是 x,而不应该是(x,)的形式。 **/ Node *Parent(Bitree bt,Bitree p);///求指定节点的父节点 int Degrees_1(Bitree bt);///统计度为1的节点个数 int Degrees_2(Bitree bt);///统计度为2的节点个数 int Height(Bitree bt);///求二叉树的高度 int Level(Bitree bt,Bitree p,int depth);///求二叉树指定的结点所在的层次 void Delete(Bitree &bt);///删除二叉树中所有的叶子节点 void Reflect(Bitree bt);///交换以t为根的二叉树中的每个节点的子女 void PrePrint(Bitree bt,int depath);///以前序次序输出一棵二叉树所有节点的数据值及结点所在的层次 void CreatPre_In(Bitree &bt,DataType pre[],int preL,int preR,DataType in[],int inL,int inR);///以前序和中序还原一棵二叉树 void CreatPost_In(Bitree &bt,DataType post[],int postL,int postR,DataType in[],int inL,int inR);///以后序和中序还原一棵二叉树 void Find_Print(Bitree bt,DataType elem,int depath);///输出从根结点出发 到指定结点,依次经过的祖先(即路径) Node *Pre_Search_K(Bitree bt,int &count,int k);///利用前序遍历的求前序序列的第k个节点 int  Find_Print_Num(Bitree bt,DataType elem,DataType path[],int depth,int &count ); ///输出从根结点出发 到指定结点,依次经过的祖先(即路径)的个数 int Find_Print_Num(Bitree bt,DataType elem,DataType path[] ,int &count); ///为了屏蔽掉多余的参数,就是包装上面intFind_Print_Num函数 void  PathLength(Bitree bt,DataType p,DataType q,DataType path[],int &len); /**利用前序遍历求任意指定的两个节点pq间的路径及路径长度*/ int HeightBlance(Bitree bt);///利用二叉树的后序遍历求二叉树的高度,并判断二叉树是否平衡 ///平衡是指二叉树中任一结点的左右子树高度的差绝对值不能超过1

#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"); }

转载请注明原文地址: https://www.6miu.com/read-849985.html

最新回复(0)