検討: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,0,6,0,0を1回入力すると、二叉樹を構成します。 3 2 65。 4出力:root=3 The InOrderTraveris:5 4 3 The PreOrder Traveris:3 5 5 5 4 The PostOrder Traveris:5 4 6 3は予期効果を達成します。