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

探討:C++實(shí)現(xiàn)鏈?zhǔn)蕉鏄?用非遞歸方式先序,中序,后序遍歷二叉樹)

 更新時(shí)間:2013年05月29日 11:55:10   作者:  
本篇文章是對(duì)用C++實(shí)現(xiàn)鏈?zhǔn)蕉鏄?用非遞歸方式先序,中序,后序遍歷二叉樹)的方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
如有不足之處,還望指正!
復(fù)制代碼 代碼如下:

// BinaryTree.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//C++實(shí)現(xiàn)鏈?zhǔn)蕉鏄?,采用非遞歸的方式先序,中序,后序遍歷二叉樹
#include "stdafx.h"
#include<iostream>
#include<string>
#include <stack>
using namespace std;
template<class T>
struct BiNode
{
 T data;
 struct BiNode<T> *rchild,*lchild;
};
template<class T>
class BiTree
{
public:
 BiTree(){
  cout<<"請(qǐng)輸入根節(jié)點(diǎn):"<<endl;
  Create(root);
  if (NULL != root)
  {
   cout<<"root="<<root->data<<endl;
  }
  else
  {
   cout << "The BinaryTree is empty." << endl;
  }
 }
 ~BiTree(){Release(root);}
 void InOrderTraverse();
 void PreOrderTraverse();
 void PostOrderTraverse();
private:
 BiNode<T> *root;
 void Create(BiNode<T>* &bt);
 void Release(BiNode<T> *bt);
};
//析構(gòu)函數(shù)
template <class T>
void BiTree<T>::Release(BiNode<T> *bt)
{

 if(bt==NULL)
 {
  Release(bt->lchild );
  Release(bt->rchild );
  delete bt;
 }
}
//建立二叉樹
template <class T>
void BiTree<T>::Create(BiNode<T>* &bt)
{
 T ch;
    cin>>ch;
    if(ch== 0)bt=NULL;
    else
    {
     bt=new BiNode<T>;
     bt->data =ch;
     cout<<"調(diào)用左孩子"<<endl;
     Create(bt->lchild );
     cout<<"調(diào)用右孩子"<<endl;
     Create(bt->rchild );
    }
}
/************************************************************************
方法:中序遍歷(非遞歸形式)
思想:向左走到盡頭,入棧。出棧,訪問節(jié)點(diǎn),向右一步
************************************************************************/
template <class T>
void BiTree<T>::InOrderTraverse()
{
 stack<BiNode<T>*> sta; //定義一個(gè)存放BiNode型指針的空棧
 BiNode<T>* p = root;
 sta.push(p);   //將根指針入棧
 while(!sta.empty())
 {
  while (NULL != p)
  {//向左走到盡頭,并保留所經(jīng)過的節(jié)點(diǎn)指針,入棧
   p = p->lchild;
   if (NULL != p)
   {
    sta.push(p);
   }
  }
  if (!sta.empty())
  {
   p = sta.top(); 
   cout << p->data << " ";  //訪問棧頂元素,
   sta.pop();     //棧頂元素出棧
   p = p->rchild;  //向右一步 
   if (NULL != p)
   {
    sta.push(p);
   }
  }  
 }
}
/************************************************************************
方法:先序遍歷(非遞歸形式)
思想:向左走到盡頭,入棧,訪問節(jié)點(diǎn)。出棧,向右一步
************************************************************************/
template<class T>
void BiTree<T>::PreOrderTraverse()
{
 stack<BiNode<T>*> sta;
 BiNode<T>* p = root;
 sta.push(p);   //將根指針入棧
 while(!sta.empty())
 {
  while (NULL != p)
  {//向左走到盡頭,并保留所經(jīng)過的節(jié)點(diǎn)指針,入棧
   cout << p->data << " ";
   p = p->lchild;
   if (NULL != p)
   {
    sta.push(p);
   } 
  }
  if (!sta.empty())
  {
   p = sta.top(); 
   sta.pop();     //棧頂元素出棧
   p = p->rchild;  //向右一步 
   if (NULL != p)
   {
    sta.push(p);
   }
  }  
 }
}
/************************************************************************
 后序遍歷(非遞歸形式)                                              
 思想:從根節(jié)點(diǎn)開始,向左走到盡頭,并入棧,同時(shí)設(shè)置標(biāo)志位為1.
 出棧時(shí)如果這個(gè)節(jié)點(diǎn)有右子樹,則判斷是第幾次訪問,如果是第1次訪問,
 則不出棧,將標(biāo)志位改為2;如果是第二次訪問,則出棧。

************************************************************************/
template<class T>
void BiTree<T>::PostOrderTraverse()
{
 stack<BiNode<T>*> sta; //存放節(jié)點(diǎn)指針的棧
 stack<int> flagsta;  //存放標(biāo)志位的棧,每出(入)一個(gè)節(jié)點(diǎn)指針,同步出(入)一個(gè)標(biāo)志位
 unsigned flag;  //設(shè)置標(biāo)志位,1-第一次訪問,2-第二次訪問
 BiNode<T>* p = root;
 sta.push(p);   //將根指針入棧
 flagsta.push(1);
 while(!sta.empty())
 {
  while (NULL != p && NULL != p->lchild)
  {//向左走到盡頭,并保留所經(jīng)過的節(jié)點(diǎn)指針,入棧
   p = p->lchild;
   sta.push(p);
   flagsta.push(1);
  }
  if (!sta.empty())
  {
   flag = flagsta.top();
   flagsta.pop();
   p = sta.top();
   if ((NULL != p->rchild) && flag == 1 )
   {//如果右子樹不空,且是第一次訪問
    flagsta.push(2);   //第一次訪問時(shí)元素不出棧,但將標(biāo)志位設(shè)置為2 
    p = p->rchild;    //向右一步
    sta.push(p);
    flagsta.push(1);
   }
   else
   {
    sta.pop(); //元素出棧
    cout << p->data << " ";  //訪問棧頂元素
    p = NULL; //將指針置為空
   }  
  }  
 }
}

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

//測試程序
void main()
{
&nbsp;&nbsp;&nbsp; BiTree<int> a;
 cout << "The InOrderTraverse is: " ;
 a.InOrderTraverse();
 cout << endl;
 cout << "The PreOrderTraverse is: " ;
 a.PreOrderTraverse();
 cout << endl;
 cout << "The PostOrderTraverse is: " ;
 a.PostOrderTraverse();
 cout << endl;
}

當(dāng)在鍵盤上一次輸入3,2,5,0,0,4,0,0,6,0,0,(這里逗號(hào)代表實(shí)際輸入時(shí)的回車鍵),即構(gòu)造了二叉樹
          3
     2      6
5     4
輸出:
root=3
The InOrderTraverse is: 5 2 4 3 6
The PreOrderTraverse is: 3 2 5 4 6
The PostOrderTraverse is: 5 4 2 6 3
達(dá)到預(yù)期效果。

相關(guān)文章

  • c++ 實(shí)現(xiàn)KMP算法

    c++ 實(shí)現(xiàn)KMP算法

    這篇文章主要介紹了c++ 實(shí)現(xiàn)KMP算法的示例,幫助大家更好的理解和學(xué)習(xí)c++,感興趣的朋友可以了解下
    2020-10-10
  • 深入理解C++模板如何實(shí)現(xiàn)多態(tài)思想

    深入理解C++模板如何實(shí)現(xiàn)多態(tài)思想

    這篇文章主要為大家詳細(xì)介紹了C++模板如何實(shí)現(xiàn)多態(tài)的相關(guān)資料,文中的示例代碼講解詳細(xì),對(duì)我們深入了解C++有一定的幫助,感興趣的可以了解一下
    2023-03-03
  • C++實(shí)現(xiàn)LeetCode(137.單獨(dú)的數(shù)字之二)

    C++實(shí)現(xiàn)LeetCode(137.單獨(dú)的數(shù)字之二)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(137.單獨(dú)的數(shù)字之二),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C++的繼承特性你了解嗎

    C++的繼承特性你了解嗎

    這篇文章主要為大家詳細(xì)介紹了C++的繼承特性,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03
  • 詳解C++編程中的靜態(tài)成員與可變數(shù)據(jù)成員

    詳解C++編程中的靜態(tài)成員與可變數(shù)據(jù)成員

    這篇文章主要介紹了詳解C++編程中的靜態(tài)成員與可變數(shù)據(jù)成員,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下
    2016-01-01
  • C++中vector類的一些簡單實(shí)現(xiàn)

    C++中vector類的一些簡單實(shí)現(xiàn)

    C++中的std::vector是一個(gè)動(dòng)態(tài)數(shù)組(也被稱為可變大小數(shù)組)的容器類,它是C++標(biāo)準(zhǔn)庫提供的其中一種容器類,提供了方便的操作和管理動(dòng)態(tài)數(shù)組的功能,本文就給大家介紹了C++中vector類的簡單實(shí)現(xiàn)代碼,需要的朋友可以參考下
    2023-08-08
  • C++ 實(shí)現(xiàn)2048游戲示例

    C++ 實(shí)現(xiàn)2048游戲示例

    《2048》是比較流行的一款數(shù)字游戲。原版2048首先在github上發(fā)布,原作者是Gabriele Cirulli。它是基于《1024》和《小3傳奇》的玩法開發(fā)而成的新型數(shù)字游戲。
    2014-06-06
  • C語言數(shù)據(jù)結(jié)構(gòu)創(chuàng)建及遍歷十字鏈表

    C語言數(shù)據(jù)結(jié)構(gòu)創(chuàng)建及遍歷十字鏈表

    這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)十字鏈表的創(chuàng)建及遍歷,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步早日升職加薪
    2021-10-10
  • IOS開發(fā)之UIScrollView實(shí)現(xiàn)圖片輪播器的無限滾動(dòng)

    IOS開發(fā)之UIScrollView實(shí)現(xiàn)圖片輪播器的無限滾動(dòng)

    這篇文章主要介紹了IOS開發(fā)之UIScrollView實(shí)現(xiàn)圖片輪播器的無限滾動(dòng)的相關(guān)資料,需要的朋友可以參考下
    2017-07-07
  • 深度剖析C++中的異常機(jī)制

    深度剖析C++中的異常機(jī)制

    異常是面向?qū)ο笳Z言常用的一種處理錯(cuò)誤的方式,當(dāng)一個(gè)函數(shù)發(fā)現(xiàn)自己無法處理的錯(cuò)誤時(shí)就可以拋出異常,本文我們將對(duì)C++ 異常機(jī)制進(jìn)行深入剖析,感興趣的同學(xué)跟著小編一起來看看吧
    2023-07-07

最新評(píng)論