C++二叉樹結(jié)構(gòu)的建立與基本操作

更新時間：2013年10月14日 09:17:49 作者：

二叉樹是數(shù)據(jù)結(jié)構(gòu)中的樹的一種特殊情況，有關(guān)二叉樹的相關(guān)概念，這里不再贅述，如果不了解二叉樹相關(guān)概念，建議先學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中的二叉樹的知識點(diǎn)

準(zhǔn)備數(shù)據(jù)
定義二叉樹結(jié)構(gòu)操作中需要用到的變量及數(shù)據(jù)等。

復(fù)制代碼代碼如下:

#define MAXLEN 20    //最大長度
typedef char DATA;    //定義元素類型
struct  CBTType                   //定義二叉樹結(jié)點(diǎn)類型 
{
 DATA data;           //元素數(shù)據(jù) 
 CBTType * left;    //左子樹結(jié)點(diǎn)指針 
 CBTType * right;   //右子樹結(jié)點(diǎn)指針 
};

定義二叉樹結(jié)構(gòu)數(shù)據(jù)元素的類型DATA以及二叉樹結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)CBTType。結(jié)點(diǎn)的具體數(shù)據(jù)保存在一個姐都DATA中，而指針left用來指向左子樹結(jié)點(diǎn)，指針right用來指向右子樹結(jié)點(diǎn)

初始化二叉樹
初始化二叉樹，將一個結(jié)點(diǎn)設(shè)置為二叉樹的根結(jié)點(diǎn)。

復(fù)制代碼代碼如下:

CBTType * InitTree()
{
 CBTType * node;
 if(node = new CBTType)  //申請內(nèi)存 
 {
  cout<<"請先輸入一個根節(jié)點(diǎn)數(shù)據(jù)："<<endl;
  cin>>node->data;
  node->left=NULL;
  node->right=NULL;
  if(node!=NULL)   //如果二叉樹結(jié)點(diǎn)不為空 
  {
   return node;  
  } else
  {
   return NULL;
  }
 }
 return NULL;
}

首先申請一個結(jié)點(diǎn)，然后用戶輸入根結(jié)點(diǎn) 的數(shù)據(jù)，并將左子樹和右子樹的指針置為空，即可完成二叉樹的初始化工作。

查找結(jié)點(diǎn)

查找結(jié)點(diǎn)就是遍歷二叉樹中的每一個節(jié)點(diǎn)，逐個比較數(shù)據(jù)，當(dāng)找到目標(biāo)數(shù)據(jù)時將返回該數(shù)據(jù)所在結(jié)點(diǎn)的指針。

復(fù)制代碼代碼如下:

CBTType *TreeFindNode(CBTType *treeNode,DATA data)
{
 CBTType *ptr;
 if(treeNode==NULL)
 {
  return NULL;
 }else
 {
  if(treeNode->data==data)
  {
   return treeNode;
  }
  else        //分別向左右子樹查找   
  {
   if(ptr=TreeFindNode(treeNode->left,data))  //左子樹遞歸查找 
   {
    return ptr;
   }
   else if(ptr=TreeFindNode(treeNode->right,data))         //右子樹遞歸查找 
   {
    return ptr;
   }
   else
   {
    return NULL;
   }
  }
 } 
} 

輸入?yún)?shù)treeNode為待查找的二叉樹的根結(jié)點(diǎn)，輸入?yún)?shù)data為待查找的結(jié)點(diǎn)數(shù)據(jù)。程序中首先判斷根結(jié)點(diǎn)是否為空，然后根據(jù)數(shù)據(jù)判斷是否為根結(jié)點(diǎn)，然后分別向左右子樹進(jìn)行查找，采用遞歸的方法進(jìn)行查找，查找到該結(jié)點(diǎn)則返回結(jié)點(diǎn)對應(yīng)的指針；如果全都查找不到，則返回NULL。

添加結(jié)點(diǎn)
添加結(jié)點(diǎn)就是在二叉樹中添加結(jié)點(diǎn)數(shù)據(jù)，添加結(jié)點(diǎn)時除了要輸入結(jié)點(diǎn)數(shù)據(jù)外，還需要指定其父結(jié)點(diǎn)，以及添加的結(jié)點(diǎn)作為左子樹還是右子樹。然后將該結(jié)點(diǎn)置為其父結(jié)點(diǎn)的左子樹或者右子樹。

復(fù)制代碼代碼如下:

void AddTreeNode(CBTType *treeNode)
{
 CBTType *pnode,*parent;
 DATA data;
 char menusel;
 if(pnode=new CBTType)     //分配內(nèi)存 
 {
  cout<<"輸入二叉樹結(jié)點(diǎn)數(shù)據(jù)："<<endl;
  cin>>pnode->data;
  pnode->left=NULL;     //設(shè)置左子樹為空 
  pnode->right=NULL;     //設(shè)置左子樹為空 
  cout<<"輸入該結(jié)點(diǎn)的父結(jié)點(diǎn)數(shù)據(jù)"<<endl;
  cin>>data;
  parent=TreeFindNode(treeNode,data);//查找父結(jié)點(diǎn)，獲得結(jié)點(diǎn)指針 
  if(!parent)
  {
   cout<<"沒有找到父結(jié)點(diǎn)"<<endl;
   delete pnode;
   return ;
  }
  cout<<"1.添加該結(jié)點(diǎn)到左子樹；2.添加該結(jié)點(diǎn)到右子樹。請輸入操作對應(yīng)的數(shù)字。"<<endl;
  do
  {
   cin>>menusel;
   if(menusel=='1'||menusel=='2')
   {
    switch(menusel)
    {
     case '1':     //添加結(jié)點(diǎn)到左子樹 
      if(parent->left)                 //左子樹不為空
      {
       cout<<"左子樹結(jié)點(diǎn)不為空"<<endl; 
      } 
      else
      {
       parent->left=pnode;
       cout<<"數(shù)據(jù)添加成功！"<<endl;
      }
      break;
     case '2':     //添加結(jié)點(diǎn)到右子樹 
      if(parent->right)                 //右子樹不為空
      {
       cout<<"右子樹結(jié)點(diǎn)不為空"<<endl;
      } 
      else
      {
       parent->right=pnode;
       cout<<"數(shù)據(jù)添加成功！"<<endl; 
      } 
      break;
     default:
      cout<<"子節(jié)點(diǎn)選擇error!"<<endl;
      break;
    } 
   }
  }while(menusel!='1'&&menusel!='2');
 }
} 

輸入?yún)?shù)treeNode為二叉樹的根結(jié)點(diǎn)，傳入根節(jié)點(diǎn)是為了方便查找父結(jié)點(diǎn)。程序中首先申請內(nèi)存，然后由用戶輸入二叉樹結(jié)點(diǎn)數(shù)據(jù)，并設(shè)置左右子樹為空。接著指定其父結(jié)點(diǎn)，將其置為左子樹或者右子樹。

計算二叉樹的深度
計算二叉樹深度就是計算二叉樹中結(jié)點(diǎn)的最大層數(shù)，這里往往需要采用遞歸算法來實(shí)現(xiàn)。

復(fù)制代碼代碼如下:

int TreeDepth(CBTType *treeNode)
{
 int depleft,depright;
 if(treeNode==NULL)
 {
  return 0;     //結(jié)點(diǎn)為空的時候，深度為0 
 }
 else
 {
  depleft=TreeDepth(treeNode->left);  //左子樹深度（遞歸調(diào)用）
  depright=TreeDepth(treeNode->right);         //右子樹深度（遞歸調(diào)用）
  if(depleft)
  {
   return ++depleft;
  }
  else 
  {
   return ++depright;
  } 
 }
} 

輸入?yún)?shù)treeNode為待計算的二叉樹的根結(jié)點(diǎn)。首先判斷根節(jié)點(diǎn)是否為空，然后分別按照遞歸調(diào)用來計算左子樹深度和右子樹深度，從而完成整個二叉樹深度的計算。

顯示結(jié)點(diǎn)數(shù)據(jù)

復(fù)制代碼代碼如下:

void ShowNodeData(CBTType *treeNode)
{
 cout<<treeNode->data<<"\t";     //直接輸出結(jié)點(diǎn)數(shù)據(jù) 
} 

輸入?yún)?shù)為需要顯示的結(jié)點(diǎn)的指針。

清空二叉樹
清空二叉樹就是將二叉樹變成一個空樹，這里也需要使用遞歸算法來實(shí)現(xiàn)。

復(fù)制代碼代碼如下:

void ClearTree(CBTType *treeNode)
{
 if(treeNode)        //判斷當(dāng)前樹不為空 
 {
  ClearTree(treeNode->left);            //清空左子樹
  ClearTree(treeNode->right);            //清空右子樹
  delete treeNode;      //釋放當(dāng)前結(jié)點(diǎn)所占用的內(nèi)存 
 }
} 

輸入?yún)?shù)treeNode為待清空的二叉樹的根節(jié)點(diǎn)。程序中按照遞歸的方法清空左子樹和右子樹以及根節(jié)點(diǎn)，釋放結(jié)點(diǎn)占用的內(nèi)存空間，從而完成清空操作。

遍歷二叉樹
遍歷二叉樹就是逐個查找二叉樹中所有的結(jié)點(diǎn)，這里為了直觀的顯示查找的結(jié)果，將會按照查找的順序，依次輸出對應(yīng)的結(jié)點(diǎn) 。

按層遍歷算法
按層遍歷算法是最直觀的算法。即：首先輸出第一層即根結(jié)點(diǎn)，然后輸出第一個結(jié)點(diǎn)的左右子數(shù)，也就是第二層……這樣循環(huán)處理，就可以逐層遍歷，一層一層按照從上到下，從左到右的順序輸出結(jié)點(diǎn)。

復(fù)制代碼代碼如下:

void LevelTree(CBTType *treeNode)
{
 CBTType *p;
 CBTType *q[MAXLEN];       //定義一個隊列 
 int head=0,tail=0;
 if(treeNode)        //如果隊首指針不為空
 {
  tail=(tail+1)%MAXLEN;             //計算循環(huán)隊列隊尾序號
  q[tail]=treeNode;      //二叉樹根指針進(jìn)入隊列 
  while(head!=tail)
  {
   head=(head+1)%MAXLEN;            //計算循環(huán)隊列的隊首序號
   p=q[head];      //獲取隊首元素
   ShowNodeData(p);     //輸出隊首元素
   if(p->left!=NULL)     //如果存在左子樹
   {
    tail=(tail+1)%MAXLEN;           //計算隊列的隊尾序號
    q[tail]=p->left;    //左子樹入隊 
   }
   if(p->right!=NULL)     //如果存在右子樹
   {
    tail=(tail+1)%MAXLEN;           //計算隊列的隊尾序號
    q[tail]=p->right;    //右子樹入隊 
   } 
  } 
 } 
} 

輸入?yún)?shù)treeNode為需要遍歷的二叉樹的根結(jié)點(diǎn)，程序在整個處理過程中，首先從根節(jié)點(diǎn)開始，將每層的結(jié)點(diǎn)逐步進(jìn)入循環(huán)隊列，并且每次循環(huán)都是輸出隊首的一個結(jié)點(diǎn)數(shù)據(jù)，然后再使它的左右子樹進(jìn)入隊列。如此循環(huán)直到隊列中的所有的數(shù)據(jù)都輸出完畢。

先序遍歷算法
先序遍歷算法就是先訪問根節(jié)點(diǎn)，然后訪問左子樹，然后訪問右子樹。程序中可以按照遞歸的思想遍歷左子樹和右子樹。

復(fù)制代碼代碼如下:

void DLRTree(CBTType *treeNode)
{
 if(treeNode)
 {
  ShowNodeData(treeNode);     //顯示結(jié)點(diǎn)內(nèi)容
  DLRTree(treeNode->left);    //顯示左子樹內(nèi)容
  DLRTree(treeNode->right);    //顯示右子樹內(nèi)容 
 }
} 

中序遍歷算法
先序遍歷算法就是先訪問左子樹，然后訪問根節(jié)點(diǎn)，然后訪問右子樹。程序中可以按照遞歸的思想遍歷左子樹和右子樹。

復(fù)制代碼代碼如下:

void LDRTree(CBTType *treeNode)
{
if(treeNode)
{

  LDRTree(treeNode->left);    //顯示左子樹內(nèi)容
  ShowNodeData(treeNode);     //顯示結(jié)點(diǎn)內(nèi)容
  DLRTree(treeNode->right);    //顯示右子樹內(nèi)容
}
}

后序遍歷算法
先序遍歷算法就是先訪問左子樹，然后訪問右子樹，然后訪問根節(jié)點(diǎn)。程序中可以按照遞歸的思想遍歷左子樹和右子樹。

復(fù)制代碼代碼如下:

void LRDTree(CBTType *treeNode)
{
 if(treeNode)
 {
  LRDTree(treeNode->left);    //顯示左子樹內(nèi)容 
  DLRTree(treeNode->right);    //顯示右子樹內(nèi)容    
  ShowNodeData(treeNode);     //顯示結(jié)點(diǎn)內(nèi)容
 } 
} 

完整代碼示例操作：

在文件中加入頭文件，然后包含上述所有函數(shù)，然后再寫一個main函數(shù)即可：

復(fù)制代碼代碼如下:

#include<iostream>
using namespace std;
#define MAXLEN 20            //最大長度
typedef char DATA;            //定義元素類型
struct CBTType                           /定義二叉樹結(jié)點(diǎn)類型
{
DATA data;     //元素數(shù)據(jù)
CBTType * left;     //左子樹結(jié)點(diǎn)指針
CBTType * right;    //右子樹結(jié)點(diǎn)指針
};
/*********************初始化二叉樹***********************/
CBTType * InitTree()
{
CBTType * node;
if(node = new CBTType)                   //申請內(nèi)存
{
  cout<<"請先輸入一個根節(jié)點(diǎn)數(shù)據(jù)："<<endl;
  cin>>node->data;
  node->left=NULL;
  node->right=NULL;
  if(node!=NULL)            //如果二叉樹結(jié)點(diǎn)不為空
  {
   return node;
  } else
  {
   return NULL;
  }
}
return NULL;
}
/***********************查找結(jié)點(diǎn)*************************/
CBTType *TreeFindNode(CBTType *treeNode,DATA data)
{
CBTType *ptr;
if(treeNode==NULL)
{
  return NULL;
}else
{
  if(treeNode->data==data)
  {
   return treeNode;
  }
  else        //分別向左右子樹查找
  {
   if(ptr=TreeFindNode(treeNode->left,data))  //左子樹遞歸查找
   {
    return ptr;
   }
   else if(ptr=TreeFindNode(treeNode->right,data))         //右子樹遞歸查找
   {
    return ptr;
   }
   else
   {
    return NULL;
   }
  }
}
}
/**********************添加結(jié)點(diǎn)*************************/
void AddTreeNode(CBTType *treeNode)
{
CBTType *pnode,*parent;
DATA data;
char menusel;
if(pnode=new CBTType)              //分配內(nèi)存
{
  cout<<"輸入二叉樹結(jié)點(diǎn)數(shù)據(jù)："<<endl;
  cin>>pnode->data;
  pnode->left=NULL;     //設(shè)置左子樹為空
  pnode->right=NULL;     //設(shè)置左子樹為空
  cout<<"輸入該結(jié)點(diǎn)的父結(jié)點(diǎn)數(shù)據(jù)"<<endl;
  cin>>data;
  parent=TreeFindNode(treeNode,data);                     //查找父結(jié)點(diǎn)，獲得結(jié)點(diǎn)指針
  if(!parent)
  {
   cout<<"沒有找到父結(jié)點(diǎn)"<<endl;
   delete pnode;
   return ;
  }
  cout<<"1.添加該結(jié)點(diǎn)到左子樹；2.添加該結(jié)點(diǎn)到右子樹。請輸入操作對應(yīng)的數(shù)字。"<<endl;
  do
  {
   cin>>menusel;
   if(menusel=='1'||menusel=='2')
   {
    switch(menusel)
    {
     case '1':     //添加結(jié)點(diǎn)到左子樹
      if(parent->left)                 //左子樹不為空
      {
       cout<<"左子樹結(jié)點(diǎn)不為空"<<endl;
      }
      else
      {
       parent->left=pnode;
       cout<<"數(shù)據(jù)添加成功！"<<endl;
      }
      break;
     case '2':     //添加結(jié)點(diǎn)到右子樹
      if(parent->right)                 //右子樹不為空
      {
       cout<<"右子樹結(jié)點(diǎn)不為空"<<endl;
      }
      else
      {
       parent->right=pnode;
       cout<<"數(shù)據(jù)添加成功！"<<endl;
      }
      break;
     default:
      cout<<"子節(jié)點(diǎn)選擇error!"<<endl;
      break;
    }
   }
  }while(menusel!='1'&&menusel!='2');
}
}
/***********************計算二叉樹的深度********************************/
int TreeDepth(CBTType *treeNode)
{
int depleft,depright;
if(treeNode==NULL)
{
  return 0;     //結(jié)點(diǎn)為空的時候，深度為0
}
else
{
  depleft=TreeDepth(treeNode->left);  //左子樹深度（遞歸調(diào)用）
  depright=TreeDepth(treeNode->right);        //右子樹深度（遞歸調(diào)用）
  if(depleft)
  {
   return ++depleft;
  }
  else
  {
   return ++depright;
  }
}
}
/*************************顯示結(jié)點(diǎn)數(shù)據(jù)*********************************/
void ShowNodeData(CBTType *treeNode)
{
cout<<treeNode->data<<"\t";     //直接輸出結(jié)點(diǎn)數(shù)據(jù)
}
/***********************清空二叉樹************************************/
void ClearTree(CBTType *treeNode)
{
if(treeNode)       //判斷當(dāng)前樹不為空
{
  ClearTree(treeNode->left);    //清空左子樹
  ClearTree(treeNode->right);    //清空右子樹
  delete treeNode;     //釋放當(dāng)前結(jié)點(diǎn)所占用的內(nèi)存
}
}
/**************************按層遍歷算法*********************************/
void LevelTree(CBTType *treeNode)
{
CBTType *p;
CBTType *q[MAXLEN];      //定義一個隊列
int head=0,tail=0;
if(treeNode)       //如果隊首指針不為空
{
  tail=(tail+1)%MAXLEN;     //計算循環(huán)隊列隊尾序號
  q[tail]=treeNode;     //二叉樹根指針進(jìn)入隊列
  while(head!=tail)
  {
   head=(head+1)%MAXLEN;    //計算循環(huán)隊列的隊首序號
   p=q[head];     //獲取隊首元素
   ShowNodeData(p);    //輸出隊首元素
   if(p->left!=NULL)    //如果存在左子樹
   {
    tail=(tail+1)%MAXLEN;   //計算隊列的隊尾序號
    q[tail]=p->left;   //左子樹入隊
   }
   if(p->right!=NULL)    //如果存在右子樹
   {
    tail=(tail+1)%MAXLEN;   //計算隊列的隊尾序號
    q[tail]=p->right;   //右子樹入隊
   }
  }
}
}
/*************************先序遍歷算法**********************************/
void DLRTree(CBTType *treeNode)
{
if(treeNode)
{
  ShowNodeData(treeNode);     //顯示結(jié)點(diǎn)內(nèi)容
  DLRTree(treeNode->left);    //顯示左子樹內(nèi)容
  DLRTree(treeNode->right);    //顯示右子樹內(nèi)容
}
}
/***********************中序遍歷算法************************************/
void LDRTree(CBTType *treeNode)
{
if(treeNode)
{

  LDRTree(treeNode->left);    //顯示左子樹內(nèi)容
  ShowNodeData(treeNode);     //顯示結(jié)點(diǎn)內(nèi)容
  DLRTree(treeNode->right);    //顯示右子樹內(nèi)容
}
}
/***********************后序遍歷算法************************************/
void LRDTree(CBTType *treeNode)
{
if(treeNode)
{
  LRDTree(treeNode->left);    //顯示左子樹內(nèi)容
  DLRTree(treeNode->right);    //顯示右子樹內(nèi)容
  ShowNodeData(treeNode);     //顯示結(jié)點(diǎn)內(nèi)容
}
}
/*************************主函數(shù)部分************************************/
int main()
{
CBTType *root=NULL;      //root為指向二叉樹根結(jié)點(diǎn)的指針
char menusel;
//設(shè)置根結(jié)點(diǎn)
root=InitTree();
//添加結(jié)點(diǎn)
do
{
  cout<<"請選擇菜單添加二叉樹的結(jié)點(diǎn)："<<endl;
  cout<<"0.退出;1.添加二叉樹的結(jié)點(diǎn)。"<<endl;
  cin>>menusel;
  switch(menusel)
  {
   case '1':
    AddTreeNode(root);
    break;
   case '0':
    break;
   default:
    cout<<"添加結(jié)點(diǎn)error"<<endl;
    break;
  }
}while(menusel!='0');
//輸出樹的深度
cout<<"depth:"<<TreeDepth(root)<<endl;
//輸出結(jié)點(diǎn)內(nèi)容
do
{
  cout<<"請選擇菜單遍歷二叉樹，輸入0表示退出："<<endl;
  cout<<"1.按層遍歷"<<endl;
  cout<<"2.先序遍歷DLR"<<endl;
  cout<<"3.中序遍歷LDR"<<endl;
  cout<<"4.后序遍歷LRD"<<endl;
  cin>>menusel;
  switch(menusel)
  {
   case '0':break;
   case '1':
     cout<<"按層遍歷的結(jié)果："<<endl;
     LevelTree(root);
       cout<<endl;
    break;
   case '2':
    cout<<"先序遍歷的結(jié)果："<<endl;
    DLRTree(root);
    cout<<endl;
    break;
   case '3':
    cout<<"中序遍歷的結(jié)果："<<endl;
    LDRTree(root);
    cout<<endl;
    break;
   case '4':
    cout<<"后序遍歷的結(jié)果："<<endl;
    LRDTree(root);
    cout<<endl;
    break;
   default:
    cout<<"遍歷方式選擇出錯！"<<endl;
    break;
  }
}while(menusel!='0');
//清空二叉樹
ClearTree(root);
return 0;
}