探討:C++實現(xiàn)鏈?zhǔn)蕉鏄?用非遞歸方式先序,中序,后序遍歷二叉樹)
更新時間:2013年05月29日 11:55:10 作者:
本篇文章是對用C++實現(xiàn)鏈?zhǔn)蕉鏄?用非遞歸方式先序,中序,后序遍歷二叉樹)的方法進行了詳細的分析介紹,需要的朋友參考下
如有不足之處,還望指正!
// BinaryTree.cpp : 定義控制臺應(yīng)用程序的入口點。
//C++實現(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<<"請輸入根節(jié)點:"<<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é)點,向右一步
************************************************************************/
template <class T>
void BiTree<T>::InOrderTraverse()
{
stack<BiNode<T>*> sta; //定義一個存放BiNode型指針的空棧
BiNode<T>* p = root;
sta.push(p); //將根指針入棧
while(!sta.empty())
{
while (NULL != p)
{//向左走到盡頭,并保留所經(jīng)過的節(jié)點指針,入棧
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é)點。出棧,向右一步
************************************************************************/
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é)點指針,入棧
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é)點開始,向左走到盡頭,并入棧,同時設(shè)置標(biāo)志位為1.
出棧時如果這個節(jié)點有右子樹,則判斷是第幾次訪問,如果是第1次訪問,
則不出棧,將標(biāo)志位改為2;如果是第二次訪問,則出棧。
************************************************************************/
template<class T>
void BiTree<T>::PostOrderTraverse()
{
stack<BiNode<T>*> sta; //存放節(jié)點指針的棧
stack<int> flagsta; //存放標(biāo)志位的棧,每出(入)一個節(jié)點指針,同步出(入)一個標(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é)點指針,入棧
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); //第一次訪問時元素不出棧,但將標(biāo)志位設(shè)置為2
p = p->rchild; //向右一步
sta.push(p);
flagsta.push(1);
}
else
{
sta.pop(); //元素出棧
cout << p->data << " "; //訪問棧頂元素
p = NULL; //將指針置為空
}
}
}
}
//測試程序
void main()
{
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,(這里逗號代表實際輸入時的回車鍵),即構(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
達到預(yù)期效果。
復(fù)制代碼 代碼如下:
// BinaryTree.cpp : 定義控制臺應(yīng)用程序的入口點。
//C++實現(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<<"請輸入根節(jié)點:"<<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é)點,向右一步
************************************************************************/
template <class T>
void BiTree<T>::InOrderTraverse()
{
stack<BiNode<T>*> sta; //定義一個存放BiNode型指針的空棧
BiNode<T>* p = root;
sta.push(p); //將根指針入棧
while(!sta.empty())
{
while (NULL != p)
{//向左走到盡頭,并保留所經(jīng)過的節(jié)點指針,入棧
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é)點。出棧,向右一步
************************************************************************/
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é)點指針,入棧
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é)點開始,向左走到盡頭,并入棧,同時設(shè)置標(biāo)志位為1.
出棧時如果這個節(jié)點有右子樹,則判斷是第幾次訪問,如果是第1次訪問,
則不出棧,將標(biāo)志位改為2;如果是第二次訪問,則出棧。
************************************************************************/
template<class T>
void BiTree<T>::PostOrderTraverse()
{
stack<BiNode<T>*> sta; //存放節(jié)點指針的棧
stack<int> flagsta; //存放標(biāo)志位的棧,每出(入)一個節(jié)點指針,同步出(入)一個標(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é)點指針,入棧
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); //第一次訪問時元素不出棧,但將標(biāo)志位設(shè)置為2
p = p->rchild; //向右一步
sta.push(p);
flagsta.push(1);
}
else
{
sta.pop(); //元素出棧
cout << p->data << " "; //訪問棧頂元素
p = NULL; //將指針置為空
}
}
}
}
復(fù)制代碼 代碼如下:
//測試程序
void main()
{
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,(這里逗號代表實際輸入時的回車鍵),即構(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
達到預(yù)期效果。
相關(guān)文章
C++實現(xiàn)LeetCode(137.單獨的數(shù)字之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(137.單獨的數(shù)字之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07詳解C++編程中的靜態(tài)成員與可變數(shù)據(jù)成員
這篇文章主要介紹了詳解C++編程中的靜態(tài)成員與可變數(shù)據(jù)成員,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2016-01-01C語言數(shù)據(jù)結(jié)構(gòu)創(chuàng)建及遍歷十字鏈表
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)十字鏈表的創(chuàng)建及遍歷,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步早日升職加薪2021-10-10IOS開發(fā)之UIScrollView實現(xiàn)圖片輪播器的無限滾動
這篇文章主要介紹了IOS開發(fā)之UIScrollView實現(xiàn)圖片輪播器的無限滾動的相關(guān)資料,需要的朋友可以參考下2017-07-07