# C++ Exercises（十六）--二叉树的简单实现

+关注继续查看
#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;
}

+关注