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

C++ 遍歷二叉樹(shù)實(shí)例詳解

 更新時(shí)間：2017年06月02日 08:48:18   投稿：lqh  
這篇文章主要介紹了C++ 遍歷二叉樹(shù)實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下

C++ 遍歷二叉樹(shù)實(shí)例詳解

2叉數(shù)又叫紅黑樹(shù)，關(guān)于2叉數(shù)的遍歷問(wèn)題，有很多，一般有三種常用遍歷方法：

(1)前序遍歷(2)中序遍歷(3)后續(xù)遍歷

       以下是經(jīng)典示例：

#include "stdafx.h" 
 
#include<stdio.h> 
#include<malloc.h> 
#include <math.h > 
#define MaxSize 20 
 
typedef struct BiTNode 
{ 
 int data; 
 struct BiTNode *lchild, *rchild; 
}BiTNode,*BiTree; 
 
//建立二叉樹(shù) 
void CreateBiTree(BiTree *T) 
{ 
 char ch; 
 scanf("%c",&ch); 
 getchar(); 
 if(ch==' ') 
 { 
  printf("不產(chǎn)生子樹(shù)。\n"); 
  *T=NULL; 
 } 
 else 
 { 
  if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))) 
  { 
   printf("分配空間失敗"); 
   return; 
  }//生成一個(gè)新節(jié)點(diǎn) 
  (*T)->data = ch; 
  printf("產(chǎn)生左右子樹(shù)。\n"); 
  CreateBiTree(&(*T)->lchild);        
  CreateBiTree(&(*T)->rchild);        
 } 
} 
 
//遞歸前序遍歷 
void Preorder(BiTNode *T) 
{ 
 if(T) 
 { 
  printf("%c ",T->data); 
  Preorder(T->lchild);         
  Preorder(T->rchild);        
 } 
} 
 
//遞歸中序遍歷 
void Inorder(BiTNode *T) 
{ 
 if(T) 
 { 
  Inorder(T->lchild); 
  printf("%c ",T->data); 
  Inorder(T->rchild); 
 } 
} 
 
//遞歸后序遍歷 
void Postorder(BiTNode *T) 
{ 
 if(T) 
 { 
  Postorder(T->lchild); 
  Postorder(T->rchild); 
  printf("%c ",T->data); 
 } 
} 
 
//非遞歸前序遍歷 
void NPreorder(BiTNode *T) 
{ 
 BiTNode *stack[MaxSize],*p; 
 int top=-1; 
 if(T) 
 { 
  top++; 
  stack[top]=T;     //根節(jié)點(diǎn)進(jìn)棧 
  while(top>-1)     //棧不為空時(shí)循環(huán) 
  { 
   p=stack[top];    //退棧并訪問(wèn)該節(jié)點(diǎn) 
   top--; 
   printf("%c ",p->data); 
   if(p->rchild)    //右孩子進(jìn)棧 
   { 
    top++; 
    stack[top]=p->rchild; 
   } 
   if(p->lchild)    //左孩子進(jìn)棧 
   { 
    top++; 
    stack[top]=p->lchild; 
   } 
  }       
 } 
} 
 
//非遞歸中序遍歷 
void NInorder(BiTNode *T) 
{ 
 BiTNode *stack[MaxSize],*p; 
 int top=-1; 
 p=T; 
 while(p||top!=-1) 
 { 
  if(p) 
  { 
   top++; 
   stack[top]=p; 
   p=p->lchild; 
  }        //根節(jié)點(diǎn)進(jìn)棧，遍歷左子樹(shù) 
  else       //根節(jié)點(diǎn)退棧，訪問(wèn)根節(jié)點(diǎn)，遍歷右子樹(shù) 
  { 
   p=stack[top]; 
   top--; 
   printf("%c ",p->data); 
   p=p->rchild; 
  } 
 } 
} 
 
//非遞歸后序遍歷 
void NPostorder(BiTNode *T) 
{ 
 BiTNode *stack[MaxSize],*p; 
 int flag,top=-1; 
 do 
 { 
  while(T) 
  { 
   top++; 
   stack[top]=T; 
   T=T->lchild; 
  }        //所有左節(jié)點(diǎn)進(jìn)棧 
  p=NULL;      //p總是指向當(dāng)前節(jié)點(diǎn)的前一個(gè)已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn) 
  flag=1;      //flag為1表示當(dāng)前節(jié)點(diǎn)已經(jīng)訪問(wèn)過(guò)了 
  while(top!=-1 && flag) 
  { 
   T=stack[top]; 
   if(T->rchild==p)   //右子樹(shù)不存在或者已經(jīng)被訪問(wèn)過(guò)時(shí) 
   { 
    printf("%c ",T->data); 
    top--; 
    p=T;     //調(diào)整p指針 
   } 
   else 
   { 
    T=T->rchild; 
    flag=0;    //調(diào)整訪問(wèn)標(biāo)志 
   } 
  } 
 } while(top!=-1); 
} 
 
//層次遍歷二叉樹(shù) 
void Translever(BiTNode *T) 
{ 
 struct node 
 { 
  BiTNode *vec[MaxSize]; 
  int f,r;    //r為隊(duì)尾，f為隊(duì)頭 
 }queue; 
 BiTNode *p; 
 p=T; 
 queue.f=0; 
 queue.r=0; 
 if(T) 
  printf("%c ", p->data); 
 queue.vec[queue.r]=p; 
 queue.r=queue.r+1; 
 while(queue.f<queue.r) 
 { 
  p=queue.vec[queue.f]; 
  queue.f=queue.f+1; 
  if(p->lchild) 
  { 
   printf("%c ",p->lchild->data); 
   queue.vec[queue.r]=p->lchild; 
   queue.r=queue.r+1; 
  } 
  if(p->rchild) 
  { 
   printf("%c ",p->rchild->data); 
   queue.vec[queue.r]=p->rchild; 
   queue.r=queue.r+1; 
  } 
 } 
 printf("\n"); 
} 
 
//求二叉樹(shù)的深度 
int Depth(BiTNode *T) 
{ 
 int dep1,dep2; 
 if(T==NULL) 
  return(0); 
 else 
 { 
  dep1=Depth(T->lchild); 
  dep2=Depth(T->rchild); 
  if(dep1>dep2) 
   return(dep1+1); 
  else 
   return(dep2+1); 
 } 
} 
 
//輸出二叉樹(shù) 
void Disptree(BiTNode *T) 
{ 
 if(T) 
 { 
  printf("%c",T->data); 
  if(T->lchild || T->rchild) 
  { 
   printf("("); 
   Disptree(T->lchild); 
   if(T->rchild) 
    printf(","); 
   Disptree(T->rchild); 
   printf(")"); 
  } 
 } 
}

main.cpp

void main() 
{ 
 BiTree T=NULL; 
 char j; 
 int sign = 1; 
 
 printf("本程序可以進(jìn)行建立二叉樹(shù)、遞歸與非遞歸先序、中序、后序遍歷二叉樹(shù)、層次遍歷二叉樹(shù)、輸出二叉樹(shù)的擴(kuò)展序列的操作。\n"); 
 printf("請(qǐng)將二叉樹(shù)的先序序列輸入以建立二叉樹(shù)，葉子節(jié)點(diǎn)用空格代替。\n"); 
 printf("您必須一個(gè)一個(gè)地輸入字符。\n"); 
 while(sign) 
 { 
  printf("請(qǐng)選擇: \n"); 
  printf("0.生成二叉樹(shù)         1.求二叉樹(shù)的深度\n"); 
  printf("2.遞歸先序遍歷        3.非遞歸先序遍歷\n"); 
  printf("4.遞歸中序遍歷        5.非遞歸中序遍歷\n"); 
  printf("6.遞歸后序遍歷        7.非遞歸后序遍歷\n"); 
  printf("8.層次遍歷         9.輸出二叉樹(shù)的廣義表形式\n"); 
  printf("q.退出程序\n"); 
  scanf("%c",&j); 
  getchar(); 
  switch(j) 
  { 
  case '0': 
   printf("生成二叉樹(shù):"); 
   CreateBiTree(&T); 
   printf("\n"); 
   printf("\n"); 
   break; 
  case '1': 
   if(T) 
   { 
    printf("此二叉樹(shù)的深度為:"); 
    printf("%d",Depth(T)); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉樹(shù)為空!\n"); 
   break; 
  case '2': 
   if(T) 
   { 
    printf("遞歸先序遍歷二叉樹(shù):"); 
    Preorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else 
    printf("二叉樹(shù)為空!\n"); 
   break; 
  case '3': 
   if(T) 
   { 
    printf("非遞歸先序遍歷二叉樹(shù):"); 
    NPreorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else 
    printf("二叉樹(shù)為空!\n"); 
   break; 
  case '4': 
   if(T) 
   { 
    printf("遞歸中序遍歷二叉樹(shù):"); 
    Inorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉樹(shù)為空!\n"); 
   break; 
  case '5': 
   if(T) 
   { 
    printf("非遞歸中序遍歷二叉樹(shù):"); 
    NInorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉樹(shù)為空!\n"); 
   break; 
  case '6': 
   if(T) 
   { 
    printf("遞歸后序遍歷二叉樹(shù):"); 
    Postorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉樹(shù)為空!\n"); 
   break; 
  case '7': 
   if(T) 
   { 
    printf("非遞歸后序遍歷二叉樹(shù):"); 
    NPostorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉樹(shù)為空!\n"); 
   break; 
  case '8': 
   if(T) 
   { 
    printf("層次遍歷二叉樹(shù):"); 
    Translever(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉樹(shù)為空!\n"); 
   break; 
  case '9': 
   if(T) 
   { 
    printf("輸出二叉樹(shù):"); 
    Disptree(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉樹(shù)為空!\n"); 
   break; 
  default: 
   sign=0; 
   printf("程序運(yùn)行結(jié)束，按任意鍵退出!\n"); 
  } 
 } 
}

示例：

轉(zhuǎn)換成雙向鏈表

先序列：H      F       C       D      M     I        N
中序列：C       F       D      H      I        M     N
后序列：C       D      F       I        N      M     H  

#include <iostream> 
using namespace std; 
struct BSTreeNode{ 
 char m_val; 
 BSTreeNode *m_pLeft; 
 BSTreeNode *m_pRight; 
}; 
BSTreeNode *pHead;//鏈表顯示的頭結(jié)點(diǎn) 
BSTreeNode *pListIndex;//游標(biāo)指針 
void showOrderLiust(BSTreeNode *pCurrent); 
void createBSTree(BSTreeNode *&pCurrent,char ch) 
{ 
 if (NULL == pCurrent) { 
 pCurrent = new BSTreeNode; 
 pCurrent->m_val = ch; 
 pCurrent->m_pLeft = NULL; 
 pCurrent->m_pRight = NULL; 
 }else { 
 if (pCurrent->m_val > ch) { 
 createBSTree(pCurrent->m_pLeft,ch); 
 }else if (pCurrent->m_val < ch) { 
 createBSTree(pCurrent->m_pRight,ch); 
 } 
 else 
 { 
 return; 
 } 
 } 
} 
//遍歷二叉樹(shù)/*先序遍歷*/ 
void PreOrderTraverse(BSTreeNode *pCurrent) 
{ 
 if (NULL == pCurrent) { 
 return; 
 } 
 
 if (NULL!=pCurrent) 
 { 
 //先遍歷根節(jié)點(diǎn) 
 cout<<pCurrent->m_val<<endl; 
 //在遍歷左節(jié)點(diǎn) 
 PreOrderTraverse(pCurrent->m_pLeft); 
 //在遍歷右節(jié)點(diǎn) 
 PreOrderTraverse(pCurrent->m_pRight); 
 } 
 
} 
//中序遍歷 
void InOrderTraverse(BSTreeNode *pCurrent) 
{ 
 if (NULL == pCurrent) { 
 return; 
 } 
 if (NULL != pCurrent->m_pLeft) { 
 InOrderTraverse(pCurrent->m_pLeft); 
 } 
 
 showOrderLiust(pCurrent); 
 //在遍歷右節(jié)點(diǎn) 
 if (NULL != pCurrent->m_pRight) { 
 InOrderTraverse(pCurrent->m_pRight); 
 } 
} 
//后序遍歷 
void EndOrderTraverse(BSTreeNode *pCurrent) 
{ 
 if (NULL == pCurrent) { 
 return; 
 } 
 if (NULL != pCurrent->m_pLeft) { 
 EndOrderTraverse(pCurrent->m_pLeft); 
 } 
 cout<<pCurrent->m_val<<endl; 
 //在遍歷右節(jié)點(diǎn) 
 if (NULL != pCurrent->m_pRight) { 
 EndOrderTraverse(pCurrent->m_pRight); 
 } 
} 
/*該二元查找樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。 
 要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向*/ 
void showOrderLiust(BSTreeNode *pCurrent) 
{ 
 pCurrent->m_pLeft = pListIndex; 
 if (NULL != pListIndex) { 
 pListIndex->m_pRight = pCurrent; 
 }else 
 { 
 pHead = pCurrent; 
 } 
 pListIndex = pCurrent; 
 cout<<pCurrent->m_val<<endl; 
} 
int main(int argc,char**argv) 
{ 
 BSTreeNode *pRoot = NULL; 
 pHead = NULL; 
 pListIndex = NULL; 
 createBSTree(pRoot,'H'); 
 createBSTree(pRoot,'F'); 
 createBSTree(pRoot,'C'); 
 createBSTree(pRoot,'D'); 
 createBSTree(pRoot,'M'); 
 createBSTree(pRoot,'I'); 
 createBSTree(pRoot,'N'); 
 PreOrderTraverse(pRoot); 
 InOrderTraverse(pRoot); 
 EndOrderTraverse(pRoot); 
 delete pRoot; 
 return 0; 
}

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

相關(guān)文章

  • C語(yǔ)言的合法標(biāo)識(shí)符與整型詳解

    C語(yǔ)言的合法標(biāo)識(shí)符與整型詳解

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言的合法標(biāo)識(shí)符與整，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助
    2022-02-02
  • 詳解C++中多態(tài)的底層原理

    詳解C++中多態(tài)的底層原理

    要了解C++多態(tài)的底層原理需要我們對(duì)C指針有著深入的了解，這個(gè)在打印虛表的時(shí)候就可以見(jiàn)功底，所以快來(lái)跟隨小編一起學(xué)習(xí)一下吧
    2022-04-04
  • OpenCV圖像文件批量讀取編程實(shí)例

    OpenCV圖像文件批量讀取編程實(shí)例

    這篇文章主要為大家詳細(xì)介紹了OpenCV圖像文件批量讀取編程實(shí)例，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
    2018-01-01
  • C語(yǔ)言指針應(yīng)用簡(jiǎn)單實(shí)例

    C語(yǔ)言指針應(yīng)用簡(jiǎn)單實(shí)例

    這篇文章主要介紹了C語(yǔ)言指針應(yīng)用簡(jiǎn)單實(shí)例的相關(guān)資料,需要的朋友可以參考下
    2017-05-05
  • 如何通過(guò)函數(shù)指針調(diào)用函數(shù)(實(shí)現(xiàn)代碼)

    如何通過(guò)函數(shù)指針調(diào)用函數(shù)(實(shí)現(xiàn)代碼)

    指針可以不但可以指向一個(gè)整形，浮點(diǎn)型，字符型，字符串型的變量，也可以指向相應(yīng)的數(shù)組，而且還可以指向一個(gè)函數(shù)
    2013-09-09
  • C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中堆排序的分析總結(jié)

    C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中堆排序的分析總結(jié)

    堆是計(jì)算機(jī)科學(xué)中一類(lèi)特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱(chēng)，通常是一個(gè)可以被看做一棵完全二叉樹(shù)的數(shù)組對(duì)象。而堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。本文將通過(guò)圖片詳細(xì)介紹堆排序，需要的可以參考一下
    2022-04-04
  • C++中順序表操作的示例代碼

    C++中順序表操作的示例代碼

    這篇文章主要為大家詳細(xì)介紹了C++中順序表的基礎(chǔ)操作的相關(guān)代碼，主要有順序表的輸出、插入和刪除數(shù)據(jù)等，感興趣的小伙伴可以了解一下
    2022-10-10
  • C++文件依存關(guān)系介紹

    C++文件依存關(guān)系介紹

    如果現(xiàn)在你做的C++項(xiàng)目（課題）包含的文件沒(méi)有超過(guò)1000個(gè)，你可以選擇略過(guò)此文，不過(guò)建議繼續(xù)瀏覽
    2013-01-01
  • C++?STL容器詳解之紅黑樹(shù)部分模擬實(shí)現(xiàn)

    C++?STL容器詳解之紅黑樹(shù)部分模擬實(shí)現(xiàn)

    本文主要對(duì)紅黑樹(shù)進(jìn)行了詳細(xì)介紹，并對(duì)其核心功能進(jìn)行了模擬實(shí)現(xiàn)。文中的代碼對(duì)我們的學(xué)習(xí)或工作有一定的價(jià)值，感興趣的小伙伴可以了解一下
    2021-12-12
  • C++中字符串與整型及浮點(diǎn)型轉(zhuǎn)換全攻略

    C++中字符串與整型及浮點(diǎn)型轉(zhuǎn)換全攻略

    C++算法刷題等過(guò)程中經(jīng)常會(huì)遇到字符串與數(shù)字類(lèi)型的轉(zhuǎn)換，在這其中雖然樸素的算法有不少，但是對(duì)于double等類(lèi)型還是可以說(shuō)遇到一些麻煩，所以今天就來(lái)說(shuō)說(shuō)使用C++標(biāo)準(zhǔn)庫(kù)中的函數(shù)實(shí)現(xiàn)這些功能。感興趣的小伙伴一起參與閱讀吧
    2021-09-09

最新評(píng)論