#include "stdafx.h"
#include <iostream>
#include <stack>
#include "BinSTree.h"
#include <queue>
using namespace std;
class CTreeNode
{//树节点类
public:
CTreeNode(const int& item,CTreeNode* lptr = NULL,CTreeNode* rptr = NULL):data(item),left(lptr),right(rptr)
{
}
CTreeNode* Left(void)
{
return left;
}
CTreeNode* Right(void)
{
return right;
}
friend class CBinSTree;
public:
int data;
private:
CTreeNode* left;
CTreeNode* right;
};
typedef enum{LEFT,RIGHT} TagType;//伪节点类型
struct ProTreeNode
{//用于后序遍历的伪节点
CTreeNode* node;
TagType type;
};
CTreeNode* GetTreeNode(const int& item,CTreeNode* lptr=NULL,CTreeNode* rptr=NULL)
{
CTreeNode* p;
p = new CTreeNode(item,lptr,rptr);
if(p==NULL)
{
cerr<<"分配内存失败!"<<endl;
exit(1);
}
return p;
}
void FreeTreeNode(CTreeNode* p)
{
delete p;
p = NULL;
}
void InOrder(CTreeNode* t)
{//中序遍历
stack<CTreeNode*> s;
CTreeNode* p=t;
while (p!=NULL || !s.empty())
{
while (p!=NULL) //遍历左子树
{
s.push(p);
p=p->Left();
}//endwhile
if (!s.empty())
{
p=s.top();
s.pop();
cout<<p->data<<endl; //访问根结点
p=p->Right(); //通过下一次循环实现右子树遍历
}//endif
}//endwhile
}
void PreOrder(CTreeNode* t)
{//前序遍历
stack<CTreeNode*> s;
CTreeNode* p=t;
while (p!=NULL || !s.empty())
{
while (p!=NULL) //遍历左子树
{
cout<<p->data<<endl;
s.push(p);
p=p->Left();
}//endwhile
if (!s.empty())
{
p=s.top();
s.pop();
p=p->Right(); //通过下一次循环实现右子树遍历
}//endif
}//endwhile
}
void PostOrder(CTreeNode* t)
{//后序遍历
stack<ProTreeNode> s;
CTreeNode* p=t;
ProTreeNode x;
do
{
while (p!=NULL) //遍历左子树
{
x.node = p;
x.type = LEFT; //标记为左子树
s.push(x);
p=p->Left();
}
while (!s.empty() && s.top().type==RIGHT)
{
x = s.top();
s.pop();
p = x.node;
cout<<p->data<<endl; //type为RIGHT，表示右子树访问完毕，故访问根结点
}
if (!s.empty())
{
s.top().type = RIGHT; //遍历右子树
p=s.top().node->Right();
}
}while (!s.empty());
}
CTreeNode* MakeSampleTree()
{
CTreeNode *root,*node2,*node3,*node4,*node5;
node4 = GetTreeNode(4);
node2 = GetTreeNode(2,NULL,node4);
node5 = GetTreeNode(5);
node3 = GetTreeNode(3,node5);
root = GetTreeNode(1,node2,node3);
return root;
}
void DeleteTree(CTreeNode* t)
{
if(t!=NULL)
{
DeleteTree(t->Left());
DeleteTree(t->Right());
FreeTreeNode(t);
}
}
void ClearSampleTree(CTreeNode *t)
{
DeleteTree(t);
t = NULL;
}
void CountLeaf(CTreeNode* t,int& count)
{
if(t!=NULL)
{
CountLeaf(t->Left(),count);
CountLeaf(t->Right(),count);
if(t->Left()==NULL&&t->Right()==NULL)
count++;
}
}
int Depth(CTreeNode* t)
{
int depLeft,depRight,depRtv;
if(t==NULL)
depRtv = 0;
else
{
depLeft = Depth(t->Left());
depRight = Depth(t->Right());
depRtv = max(depLeft,depRight)+1;
}
return depRtv;
}
void IndentBlanks(int num)
{
for(int i=0;i<num;++i)
cout<<" ";
}
const int INDENTBLANKS = 6;
void PrintTree(CTreeNode* t,int level)
{//逆时针旋转'打印树
if(t!=NULL)
{
PrintTree(t->Right(),level+1);
IndentBlanks(level*INDENTBLANKS);
cout<<t->data<<endl;
PrintTree(t->Left(),level+1);
}
}
CTreeNode* CopyTree(CTreeNode* t)
{
CTreeNode *newnode,*newlptr,*newrptr;
if(t==NULL)
return NULL;
if(t->Left()!=NULL)
newlptr = CopyTree(t->Left());
else
newlptr = NULL;
if(t->Right()!=NULL)
newrptr = CopyTree(t->Right());
else
newrptr = NULL;
newnode = GetTreeNode(t->data,newlptr,newrptr);
return newnode;
}
void LevelTravel(CTreeNode* t)
{
queue<CTreeNode*> q1;
CTreeNode *p;
q1.push(t);
while(!q1.empty())
{
p = q1.front();
q1.pop();
cout<<p->data<<endl;
if(p->Left()!=NULL)
q1.push(p->Left());
if(p->Right()!=NULL)
q1.push(p->Right());
}
}
int main()
{
CTreeNode *root = NULL;
root = MakeSampleTree();
CTreeNode *root1 = CopyTree(root);
PostOrder(root);
int leafCount=0;
CountLeaf(root,leafCount);
cout<<"叶子数: "<<leafCount<<" 深度:"<<Depth(root)<<endl;
PrintTree(root,0);
cout<<"拷贝后: "<<endl;
PrintTree(root1,0);
cout<<"层序遍历: "<<endl;
LevelTravel(root);
ClearSampleTree(root);
system("pause");
return 0;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/07/20/1247018.html，如需转载请自行联系原作者
