程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> 探討:C++實現鏈式二叉樹(用非遞歸方式先序,中序,後序遍歷二叉樹)

探討:C++實現鏈式二叉樹(用非遞歸方式先序,中序,後序遍歷二叉樹)

編輯:C語言基礎知識
如有不足之處,還望指正!
代碼如下:

// BinaryTree.cpp : 定義控制台應用程序的入口點。
//C++實現鏈式二叉樹,采用非遞歸的方式先序,中序,後序遍歷二叉樹
#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<<"請輸入根節點:"<<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);
};
//析構函數
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<<"調用左孩子"<<endl;
     Create(bt->lchild );
     cout<<"調用右孩子"<<endl;
     Create(bt->rchild );
    }
}
/************************************************************************
方法:中序遍歷(非遞歸形式)
思想:向左走到盡頭,入棧。出棧,訪問節點,向右一步
************************************************************************/
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)
  {//向左走到盡頭,並保留所經過的節點指針,入棧
   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);
   }
  }  
 }
}
/************************************************************************
方法:先序遍歷(非遞歸形式)
思想:向左走到盡頭,入棧,訪問節點。出棧,向右一步
************************************************************************/
template<class T>
void BiTree<T>::PreOrderTraverse()
{
 stack<BiNode<T>*> sta;
 BiNode<T>* p = root;
 sta.push(p);   //將根指針入棧
 while(!sta.empty())
 {
  while (NULL != p)
  {//向左走到盡頭,並保留所經過的節點指針,入棧
   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);
   }
  }  
 }
}
/************************************************************************
 後序遍歷(非遞歸形式)                                              
 思想:從根節點開始,向左走到盡頭,並入棧,同時設置標志位為1.
 出棧時如果這個節點有右子樹,則判斷是第幾次訪問,如果是第1次訪問,
 則不出棧,將標志位改為2;如果是第二次訪問,則出棧。

************************************************************************/
template<class T>
void BiTree<T>::PostOrderTraverse()
{
 stack<BiNode<T>*> sta; //存放節點指針的棧
 stack<int> flagsta;  //存放標志位的棧,每出(入)一個節點指針,同步出(入)一個標志位
 unsigned flag;  //設置標志位,1-第一次訪問,2-第二次訪問
 BiNode<T>* p = root;
 sta.push(p);   //將根指針入棧
 flagsta.push(1);
 while(!sta.empty())
 {
  while (NULL != p && NULL != p->lchild)
  {//向左走到盡頭,並保留所經過的節點指針,入棧
   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);   //第一次訪問時元素不出棧,但將標志位設置為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;
}

當在鍵盤上一次輸入3,2,5,0,0,4,0,0,6,0,0,(這裡逗號代表實際輸入時的回車鍵),即構造了二叉樹
          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
達到預期效果。
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved