#include
using namespace std;
#define MAX 100
class btree
{
public:
char data;
btree *lchild;
btree *rchild;
};
btree *creatree() //非递归建立二叉树
{
char ch;
int front = 1,rear = 0; //初始化队列
btree *root,*s,*Q[MAX];
root=NULL;
cout << "'@' 表示'空','#'表示'结束',按层建树:" << endl;
ch=getchar();
while(ch!='#')
{
s = NULL; //先假设读入的为空结点"@"
if(ch != '@')
{
s = new btree;
s->data = ch;
s->lchild = NULL;
s->rchild = NULL;
}
rear++; //队尾指针自增
Q[rear] = s;
if(rear == 1)
root = s; //根
else
{
if(s && Q[front]) //当前结点及其双亲结点都不是空结点
if(rear%2 == 0)
Q[front]->lchild=s;
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=getchar(); //读出下一个结点的值
}
return root;
}
void postorder(btree *bt)
{
btree *p=bt, *stack[MAX];//p表示当前结点,栈stack[]用来存储结点
int tag[MAX];
int top=-1;
do
{
while(p != NULL)//先处理结点的左孩子结点,把所有左孩子依次入栈
{
stack[++top] = p;
tag[top] = 0;
p = p->lchild;
}
if(top >= 0) //所有左孩子处理完毕后
{
if(!tag[top]) //如果当前结点的右孩子还没被访问
{
p = stack[top];//输出栈顶结点 ,但不退栈 ,因为要先输出其孩子结点
p = p->rchild; //处理其右孩子结点
tag[top] = 1; //表示栈中top位置存储的结点的右孩子被访问过了,下次轮到它退栈时可直接输出
}
else
{
cout << stack[top--]->data; //栈顶元素出栈,输出该结点,此时结点p指向NULL
}
}
} while((p != NULL)||(top >= 0));
}
int main()
{
btree *bt;
bt = creatree();
cout<<'\n'<<"后序:";
postorder(bt);
cout<
return 0;
}
int BiTreeDepthHierarchy(BiThrTree T) //非递归类层次遍历求二叉树深度
{
int depth=0,hp,tp,lc; //hp为已访问的结点数,tp历史入队的结点总数,lc为每层最后一个结点标记
LinkQueue Q;
BiThrNode *p;
if(T)
{
p=T;
hp=0;tp=1;lc=1;
InitQueue(Q);
EnQueue(Q,p);
while(!QueueEmpty(Q))
{
DeQueue(Q,p);
hp++; //hp为已访问的结点数
if(p->lchild)
{
EnQueue(Q,p->lchild);
tp++; //tp记录历史入队的结点总数
}
if(p->rchild)
{
EnQueue(Q,p->rchild);
tp++;
}
if(hp==lc) //当hp=lc时,表明本层结点均已访问完
{
depth++;
lc=tp; //lc=tp,更新下层的末结点标记
}
}
}
return depth;
}