欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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)中的二叉樹的知識點

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

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

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

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

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

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

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

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

查找結(jié)點

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

復(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;      //二叉樹根指針進入隊列
  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é)點，程序在整個處理過程中，首先從根節(jié)點開始，將每層的結(jié)點逐步進入循環(huán)隊列，并且每次循環(huán)都是輸出隊首的一個結(jié)點數(shù)據(jù)，然后再使它的左右子樹進入隊列。如此循環(huán)直到隊列中的所有的數(shù)據(jù)都輸出完畢。


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

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

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

中序遍歷算法
先序遍歷算法就是先訪問左子樹，然后訪問根節(jié)點，然后訪問右子樹。程序中可以按照遞歸的思想遍歷左子樹和右子樹。
復(fù)制代碼 代碼如下:

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

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


后序遍歷算法
先序遍歷算法就是先訪問左子樹，然后訪問右子樹，然后訪問根節(jié)點。程序中可以按照遞歸的思想遍歷左子樹和右子樹。
復(fù)制代碼 代碼如下:

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

完整代碼示例操作：

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

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

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


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

程序運行界面：

相關(guān)文章

  • C++數(shù)據(jù)封裝以及定義結(jié)構(gòu)的詳細(xì)講解

    C++數(shù)據(jù)封裝以及定義結(jié)構(gòu)的詳細(xì)講解

    這篇文章主要詳細(xì)講解了C++數(shù)據(jù)封裝以及定義結(jié)構(gòu)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-05-05
  • QT實現(xiàn)多線程兩種方式案例詳解

    QT實現(xiàn)多線程兩種方式案例詳解

    這篇文章主要介紹了QT實現(xiàn)多線程兩種方式案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • C語言函數(shù)封裝及變量的作用域

    C語言函數(shù)封裝及變量的作用域

    這篇文章主要介紹了C語言函數(shù)封裝及變量的作用域，以及分享一些字符串的相關(guān)實戰(zhàn)練習(xí)，字符串轉(zhuǎn)整數(shù)、整數(shù)轉(zhuǎn)字符串、浮點數(shù)轉(zhuǎn)字符串、字符串轉(zhuǎn)浮點數(shù)、判斷平年閏年、技術(shù)字符串長度等等。下文詳細(xì)內(nèi)容需要的小伙伴可以參考一下
    2022-05-05
  • 詳解C語言實現(xiàn)空間索引四叉樹

    詳解C語言實現(xiàn)空間索引四叉樹

    本文主要介紹了用C語言實現(xiàn)四叉樹，對算法感興趣的同學(xué)，可以參考下，并且試驗一下。
    2021-05-05
  • C++中bitset位圖介紹及模擬實現(xiàn)

    C++中bitset位圖介紹及模擬實現(xiàn)

    位圖就是用每一位來存放某種狀態(tài)，適用于海量數(shù)據(jù)，本文就介紹一下C++中bitset位圖介紹及模擬實現(xiàn)，具有一定的參考價值，感興趣的可以了解一下
    2023-07-07
  • C語言中循環(huán)語句練習(xí)實例

    C語言中循環(huán)語句練習(xí)實例

    大家好，本篇文章主要講的是C語言中循環(huán)語句練習(xí)實例，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下
    2022-01-01
  • 基于C++ list中erase與remove函數(shù)的使用詳解

    基于C++ list中erase與remove函數(shù)的使用詳解

    本篇文章是對C++ list中erase與remove函數(shù)的使用進行了詳細(xì)的分析介紹，需要的朋友參考下
    2013-05-05
  • 用Visual Studio2017寫C++靜態(tài)庫圖文詳解

    用Visual Studio2017寫C++靜態(tài)庫圖文詳解

    這篇文章主要介紹了用Visual Studio2017寫C++靜態(tài)庫的圖文教程,需要的朋友可以參考下
    2017-04-04
  • 一文詳解C++11中decltype的使用

    一文詳解C++11中decltype的使用

    這篇文章主要為大家分享了C++11中decltype關(guān)鍵字的使用示例，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧
    2023-07-07
  • c語言獲取直播吧最近一周nba比賽信息

    c語言獲取直播吧最近一周nba比賽信息

    這篇文章主要介紹了使用c語言獲取直播吧最近一周nba比賽信息的方法,需要的朋友可以參考下
    2014-04-04

最新評論