二叉樹實作例題

//二叉樹的實作

#include <iostream>

using namespace std;

//二叉樹的結點定義

typedef struct bitreenode

{

  char data;

  struct bitreenode *lchild,*rchild;

}*Bitree;

//建立二叉樹

void creatbitree(Bitree &T)

{

  char ch;

  ch=getchar();

  if(ch=='#')

    T=NULL;

  else

  {

    T=new bitreenode;

    T->data=ch;

    creatbitree(T->lchild);

    creatbitree(T->rchild);  //AB#D##CE###

  }

}

//遞歸的方法先序周遊二叉樹

void preordertraverse(Bitree T)

{

  if(T!=NULL)

  {

    cout<<T->data<<" ";

    preordertraverse(T->lchild);

    preordertraverse(T->rchild);

  }

}

//遞歸的方法中序周遊二叉樹

void inordertraverse(Bitree T)

{

  if(T)

  {

    inordertraverse(T->lchild);

    cout<<T->data<<" ";

    inordertraverse(T->rchild);

  }

}

//遞歸的方法中序周遊二叉樹

void postordertraverse(Bitree T)

{

  if(T)

  {

    postordertraverse(T->lchild);

    postordertraverse(T->rchild);

    cout<<T->data<<" ";

  }

}

//求二叉樹的深度

int depthofbitree(Bitree T)

{

  int ldepth,rdepth;

  if(T==NULL)

    return 0;

  ldepth=depthofbitree(T->lchild);

  rdepth=depthofbitree(T->rchild);

  if(ldepth>rdepth)

    return ldepth+1;

  else

    return rdepth+1;

}

//求葉子結點的個數

int leafcount(Bitree T)

{

  if(T==NULL)

    return 0;

  else if(T->lchild==NULL && T->rchild==NULL)

    return 1;

  else

  {

    int n=leafcount(T->lchild);

    int m=leafcount(T->rchild);

    return m+n;

  }

}

//輸出二叉樹中度為1的結點的值，并求其數量

int onesoncount(Bitree T)

{

  if(T==NULL)

    return 0;

  else if((T->lchild!=NULL && T->rchild==NULL)||(T->rchild!=NULL && T->lchild==NULL))

  {

    cout<<"度為1的結點的字母為："<<T->data<<endl;

    return onesoncount(T->lchild)+onesoncount(T->rchild)+1;

  }

  else

    return onesoncount(T->lchild)+onesoncount(T->rchild);

}

//輸出二叉樹中所有度為2的結點的資料值，并統計其數目

int twoson(Bitree T)

{

  if(T==NULL)

    return 0;

  else if(T->lchild!=NULL && T->rchild!=NULL)

    cout<<"度為2的結點的字元是："<<T->data<<endl;

  return twoson(T->lchild)+twoson(T->lchild) + 1;

}

//求二叉樹T中非葉子結點的數目

int notleafcount(Bitree T)

{

  if(T==NULL)

    return 0;

  else if(T->lchild==NULL && T->rchild==NULL)

    return 0;

  else

  {

    cout<<T->data<<" ";

    int n=notleafcount(T->lchild);

    int m=notleafcount(T->rchild);

    return (m+n+1);

  }

}

//求二叉樹中全部結點的數量

int node_num(Bitree T)

{

  if(T==NULL)

    return 0;

  else

    return node_num(T->lchild)+node_num(T->rchild)+ 1;

}

//輸出二叉樹中的重複值

int same_node(Bitree T) 

{  

  if(T== NULL )  

         return 0;

    else

         if (T->data=='C')

               return(same_node(T->lchild)+same_node(T->rchild)+1);

         else

               return(same_node(T->lchild)+same_node(T->rchild));

} 

//交換二叉樹的左右子樹

void Exchange(Bitree T)

{

  Bitree temp=NULL;

  if(T!=NULL)

  {

    temp=T->rchild;

    T->rchild=T->lchild;

    T->lchild=temp;

    Exchange(T->lchild);

    Exchange(T->rchild);

  }

  else

  return;

}

//判斷某個結點所在的層

int node_layer(Bitree T,int level,char key)

{

  int l;

  if(T) 

  { 

    if(T->data == key) 

    {

      return level;

    } 

    l = node_layer(T->lchild,level+1,key);

    if(l != 0) 

    {

      return l;

    } 

    else 

    {

      return node_layer(T->rchild,level+1,key) ;  

    }  

  }

  return 0;

}

//按先序序列輸出葉子結點的值

void preorder(Bitree T)

{

  if(T)

  {

    if((T->lchild==NULL)&&(T->rchild==NULL))

      cout<<T->data<<" ";

    preorder(T->lchild);

    preorder(T->rchild);

  }

}

//主函數

int main()

{

  Bitree t=NULL;

  cout<<"請按以下兩種序列輸入二叉樹的結點："<<endl;

  printf("AB#D##CE### 或 ABD##E##C#F##\n");

  creatbitree(t);

  cout<<"先序周遊：";

  preordertraverse(t);

  cout<<endl;

  cout<<"中序周遊：";

  inordertraverse(t);

  cout<<endl;

  cout<<"後序周遊：";

  postordertraverse(t);

  cout<<endl;

  cout<<"二叉樹的深度為："<<depthofbitree(t)<<endl;

  int leaf=0;

  leaf=leafcount(t);

  cout<<"葉子結點的個數為："<<leaf<<endl;

  int oneson1=0;

  oneson1=onesoncount(t);

  cout<<"度為１的結點個數為："<<oneson1<<endl;

  int notleafcount1=0;

  cout<<"非葉子結點的字元為：";

  notleafcount1=notleafcount(t);

  cout<<"非葉子結點的數量為："<<notleafcount1<<endl;

    cout<<endl;

  int all_node=0;

  all_node=node_num(t);

  cout<<"二叉樹中全部結點數量為："<<all_node<<endl;

  int same_num=0;

  same_num=same_node(t);

  cout<<"二叉樹中相同C結點數量為："<<same_num<<endl;

    //判斷某個結點所在的層

  int layer=1;

  int la;

  //char ch;

  la=node_layer(t,layer,'C');

    cout<<"結點C在的層是："<<la<<endl;

  cout<<"先序列印二叉樹中葉子結點的值："<<endl;

  preorder(t);

  cout<<endl;

  Exchange(t);

  cout<<"左右子樹交換後先序周遊：";

  preordertraverse(t);

  cout<<endl;

  cout<<"左右子樹交換後中序周遊：";

  inordertraverse(t);

  cout<<endl;

  cout<<"左右子樹交換後的後序周遊：";

  postordertraverse(t);

  cout<<endl;

  return 1;

}