#include<iostream>
#include<math.h>
#include<stdlib.h>
#define TElemType char
using namespace std;
typedef struct Tnode
{
TElemType data;
struct Tnode *lchild, *rchild;
}TNODE, *DTree;
class Tree
{
private:
TElemType data;
int dmax;
int dleft;
int dright;
DTree T;
public:
Tree();
DTree getT();
int Init_Tree(DTree& q);
void PreOrderTraverser(DTree q);
void InOrderTraverser(DTree q);
int PostOrderTraverser(DTree q);
int PostOrderDepth(DTree q);
int getnode(DTree q);
};
Tree::Tree()
{
cout<<"请输入数据"<<endl;
cout<<"以#键结束"<<endl;
cout<<"*为空树"<<endl;
Init_Tree(T);
cout<<"初始化结束"<<endl;
}
DTree Tree::getT()
{
return T;
}
int Tree::Init_Tree(DTree& q)
{
data = getchar();
if(data=='#')
{
return 0;
}
if(data=='*')
q = NULL;
else
{
q = (TNODE*) new TNODE[1];
if(!q)
{
cout<<"错误"<<endl;
exit(OVERFLOW);
}
q->data = data;
Init_Tree(q->lchild);
Init_Tree(q->rchild);
}
}
void Tree::PreOrderTraverser(DTree q)
{
if(q)
{
cout<<q->data<<" ";
PreOrderTraverser(q->lchild);
PreOrderTraverser(q->rchild);
}
}
void Tree::InOrderTraverser(DTree q)
{
if(q)
{
InOrderTraverser(q->lchild);
cout<<q->data<<" ";
InOrderTraverser(q->rchild);
}
}
int Tree::PostOrderTraverser(DTree q)
{
if(q)
{
PostOrderTraverser(q->lchild);
PostOrderTraverser(q->rchild);
cout<<q->data<<" ";
return 0;
}
else
return 0;
}
int Tree::getnode(DTree q)
{
static int node = 0;
if(q)
{
return (getnode(q->lchild)+getnode(q->rchild)+1);
}
else
return 0;
}
int Tree::PostOrderDepth(DTree q)
{
if(q)
{
dleft = PostOrderDepth(q->lchild);
dright = PostOrderDepth(q->rchild);
dmax = dleft > dright ? dleft : dright;
return (dmax+1);
}else
return 0;
}
int main()
{
Tree BinaryTree;
cout<<"先序遍历:";
BinaryTree.PreOrderTraverser(BinaryTree.getT());
cout<<endl;
cout<<"中序遍历:";
BinaryTree.InOrderTraverser(BinaryTree.getT());
cout<<endl;
cout<<"后续遍历:";
BinaryTree.PostOrderTraverser(BinaryTree.getT());
cout<<endl;
cout<<"深度:";
cout<<BinaryTree.PostOrderDepth(BinaryTree.getT());
cout<<endl;
cout<<"...."<<endl;
cout<<"结点个数:";
cout<<BinaryTree.getnode(BinaryTree.getT());
cout<<endl;
return 0;
}
