雷火电竞-中国电竞赛事及体育赛事平台

歡迎來(lái)到入門教程網(wǎng)！

C語(yǔ)言

當(dāng)前位置：主頁(yè) > 軟件編程 > C語(yǔ)言 >

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

來(lái)源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語(yǔ)言|點(diǎn)擊： 次

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

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

#define MAXLEN 20    //最大長(zhǎng)度
typedef char DATA;    //定義元素類型
struct  CBTType                   //定義二叉樹結(jié)點(diǎn)類型
{
 DATA data;           //元素?cái)?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ù)保存在一個(gè)姐都DATA中，而指針left用來(lái)指向左子樹結(jié)點(diǎn)，指針right用來(lái)指向右子樹結(jié)點(diǎn)

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

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

CBTType * InitTree()
{
 CBTType * node;
 if(node = new CBTType)  //申請(qǐng)內(nèi)存
 {
  cout<<"請(qǐng)先輸入一個(gè)根節(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;
}

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

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

查找結(jié)點(diǎn)就是遍歷二叉樹中的每一個(gè)節(jié)點(diǎn)，逐個(gè)比較數(shù)據(jù)，當(dāng)找到目標(biāo)數(shù)據(jù)時(shí)將返回該數(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)對(duì)應(yīng)的指針；如果全都查找不到，則返回NULL。

添加結(jié)點(diǎn)
添加結(jié)點(diǎn)就是在二叉樹中添加結(jié)點(diǎn)數(shù)據(jù)，添加結(jié)點(diǎn)時(shí)除了要輸入結(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<<"沒(méi)有找到父結(jié)點(diǎn)"<<endl;
   delete pnode;
   return ;
  }
  cout<<"1.添加該結(jié)點(diǎn)到左子樹；2.添加該結(jié)點(diǎn)到右子樹。請(qǐng)輸入操作對(duì)應(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)。程序中首先申請(qǐng)內(nèi)存，然后由用戶輸入二叉樹結(jié)點(diǎn)數(shù)據(jù)，并設(shè)置左右子樹為空。接著指定其父結(jié)點(diǎn)，將其置為左子樹或者右子樹。

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

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

int TreeDepth(CBTType *treeNode)
{
 int depleft,depright;
 if(treeNode==NULL)
 {
  return 0;     //結(jié)點(diǎn)為空的時(shí)候，深度為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為待計(jì)算的二叉樹的根結(jié)點(diǎn)。首先判斷根節(jié)點(diǎn)是否為空，然后分別按照遞歸調(diào)用來(lái)計(jì)算左子樹深度和右子樹深度，從而完成整個(gè)二叉樹深度的計(jì)算。

顯示結(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)的指針。

清空二叉樹
清空二叉樹就是將二叉樹變成一個(gè)空樹，這里也需要使用遞歸算法來(lái)實(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)存空間，從而完成清空操作。

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

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

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

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

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


先序遍歷算法
先序遍歷算法就是先訪問(wèn)根節(jié)點(diǎn)，然后訪問(wèn)左子樹，然后訪問(wè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)容
 }
}

中序遍歷算法
先序遍歷算法就是先訪問(wèn)左子樹，然后訪問(wèn)根節(jié)點(diǎn)，然后訪問(wè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)容    
 } 
}


后序遍歷算法
先序遍歷算法就是先訪問(wèn)左子樹，然后訪問(wèn)右子樹，然后訪問(wèn)根節(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ù)，然后再寫一個(gè)main函數(shù)即可：

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

#include<iostream>
using namespace std;
#define MAXLEN 20            //最大長(zhǎng)度
typedef char DATA;            //定義元素類型
struct  CBTType                           /定義二叉樹結(jié)點(diǎn)類型
{
 DATA data;     //元素?cái)?shù)據(jù)
 CBTType * left;     //左子樹結(jié)點(diǎn)指針
 CBTType * right;    //右子樹結(jié)點(diǎn)指針
};
/*********************初始化二叉樹***********************/
CBTType * InitTree()
{
 CBTType * node;
 if(node = new CBTType)                   //申請(qǐng)內(nèi)存
 {
  cout<<"請(qǐng)先輸入一個(gè)根節(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<<"沒(méi)有找到父結(jié)點(diǎn)"<<endl;
   delete pnode;
   return ;
  }
  cout<<"1.添加該結(jié)點(diǎn)到左子樹；2.添加該結(jié)點(diǎn)到右子樹。請(qǐng)輸入操作對(duì)應(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');
 }
}
/***********************計(jì)算二叉樹的深度********************************/
int TreeDepth(CBTType *treeNode)
{
 int depleft,depright;
 if(treeNode==NULL)
 {
  return 0;     //結(jié)點(diǎn)為空的時(shí)候，深度為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];      //定義一個(gè)隊(duì)列
 int head=0,tail=0;
 if(treeNode)       //如果隊(duì)首指針不為空
 {
  tail=(tail+1)%MAXLEN;     //計(jì)算循環(huán)隊(duì)列隊(duì)尾序號(hào)
  q[tail]=treeNode;     //二叉樹根指針進(jìn)入隊(duì)列
  while(head!=tail)
  {
   head=(head+1)%MAXLEN;    //計(jì)算循環(huán)隊(duì)列的隊(duì)首序號(hào)
   p=q[head];     //獲取隊(duì)首元素
   ShowNodeData(p);    //輸出隊(duì)首元素
   if(p->left!=NULL)    //如果存在左子樹
   {
    tail=(tail+1)%MAXLEN;   //計(jì)算隊(duì)列的隊(duì)尾序號(hào)
    q[tail]=p->left;   //左子樹入隊(duì)
   }
   if(p->right!=NULL)    //如果存在右子樹
   {
    tail=(tail+1)%MAXLEN;   //計(jì)算隊(duì)列的隊(duì)尾序號(hào)
    q[tail]=p->right;   //右子樹入隊(duì)
   }
  }
 }
}
/*************************先序遍歷算法**********************************/
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<<"請(qǐng)選擇菜單添加二叉樹的結(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<<"請(qǐng)選擇菜單遍歷二叉樹，輸入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<<"遍歷方式選擇出錯(cuò)！"<<endl;
    break;
  }
 }while(menusel!='0');
 //清空二叉樹 
 ClearTree(root);
 return 0; 
}


對(duì)應(yīng)的樹形結(jié)構(gòu)圖如圖：

程序運(yùn)行界面：

上一篇：枚舉類型的定義和應(yīng)用總結(jié)

欄    目：C語(yǔ)言

下一篇：用typedef定義類型詳細(xì)總結(jié)

本文標(biāo)題：C++二叉樹結(jié)構(gòu)的建立與基本操作

本文地址：http://www.jygsgssxh.com/a1/Cyuyan/3959.html

網(wǎng)頁(yè)制作CMS教程網(wǎng)絡(luò)編程軟件編程腳本語(yǔ)言數(shù)據(jù)庫(kù)服務(wù)器

如果侵犯了您的權(quán)利，請(qǐng)與我們聯(lián)系，我們將在24小時(shí)內(nèi)進(jìn)行處理、任何非本站因素導(dǎo)致的法律后果，本站均不負(fù)任何責(zé)任。

聯(lián)系QQ：835971066 | 郵箱：835971066#qq.com(#換成@)

Copyright © 2002-2020 腳本教程網(wǎng) 版權(quán)所有