/***************** WZ ASUST 2016
二叉树 的结点计算
配图 栈实现非递归 栈内元素变化图
******************/
#include
#include
#include
#include
using namespace std;
typedef struct BinNode{
char data;
bool flag; //后序非递归中的标记
struct BinNode *lchild,*rchild;
}BinNode,*BinTree;
//按先序创建树
// char ss[]="12##3##";
char ss[]="124##x##3y##5##";
//char ss[]="124###3#5##";
/*************************
* 1
* 2 3
* 4 5
*************************/
int i=0;
void creatTree(BinTree &T)
{
char c;
// cin>>c;
c=ss[i++];
if(c=='#') T=NULL;
else{ // T=(BinTree)malloc(sizeof(BinNode));
T=new BinNode; T->data=c;
creatTree(T->lchild);
creatTree(T->rchild);
}
}
void visit(BinTree T)
{
if(T->data!='#') cout<data<<" ";
}
void preOrder(BinTree T) //前序递归
{
if(T)
{
visit(T);
preOrder(T->lchild);
preOrder(T->rchild);
}
}
void inOrder(BinTree T) //中序递归
{
if(T)
{
inOrder(T->lchild);
visit(T);
inOrder(T->rchild);
}
}
void postOrder(BinTree T) //后序递归
{
if(T)
{
postOrder(T->lchild);
postOrder(T->rchild);
visit(T);
}
}
void preOrderUnrec(BinTree T) //非递归前序遍历
{
BinTree p; p=T;
stack s;
while(p || !s.empty())
{
while(p)
{
visit(p);
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
void inOrderUnrec(BinTree T) ////非递归中序遍历
{
BinTree p; p=T;
stack s;
while(p || !s.empty())
{
while(p)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
visit(p);
s.pop();
p=p->rchild;
}
}
}
void postOrderUnrec1(BinTree T) //非递归后序遍历 这个思路更好理解一些，下面有解释
{
BinTree p,cur; p=T;
stack s; s.push(p);
BinTree pre=NULL;
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL && cur->rchild==NULL)||((pre!=NULL)&&(pre==cur->lchild || pre==cur->rchild)))
{
visit(cur);
s.pop();
pre=cur;
}
else
{
if(cur->rchild)
s.push(cur->rchild);
if(cur->lchild)
s.push(cur->lchild);
}
}
}
void postOrderUnrec2(BinTree T) //非递归后序遍历
{
BinTree cur,p; p=T; p->flag=false;
stack s; s.push(p);
while(!s.empty())
{
cur=s.top();
if(cur->flag==true)
{
visit(cur);
s.pop();
}
else
{
if(cur->rchild){
cur->rchild->flag=false;
s.push(cur->rchild);
}
if(cur->lchild){
cur->lchild->flag=false; // 左右节点为NULL时，开始要出栈
s.push(cur->lchild);
}
cur->flag=true; //左右子节点入栈后，父节点标记为TRUE
}
}
}
void postOrderUnrec3(BinTree T)
{
BinTree cur,p; p=T;
queue q; q.push(p);
while(!q.empty())
{
cur=q.front(); visit(cur); q.pop();
if(cur->lchild!=NULL) q.push(cur->lchild);
if(cur->rchild!=NULL) q.push(cur->rchild);
}
}
void postOrderUnrec4(BinTree T) //非递归后序遍历 不宜用带计数器实现
{
BinTree cur,p; p=T;
BinTree q[10];
int f=0;int r=1;
while(flchild!=NULL)q[r++]=p->lchild;
if(p->rchild!=NULL)q[r++]=p->rchild;
if(r%2==1)f++;//cout<data=c; }
BinTree cur=T;
queue q; q.push(cur);
while(!q.empty())
{
cur=q.front(); q.pop();
if(c=='#') cur->lchild=NULL;
else { cur->lchild=new BinNode; T->data=c; q.push(cur->lchild);}
if(c=='#') cur->rchild=NULL;
else { cur->rchild=new BinNode; T->data=c; q.push(cur->rchild);}
}
}
void print_as_tree(BinTree T,int lay)
{
if(T)
{
print_as_tree(T->rchild,lay+1);
for(int j=0;jdata<lchild,lay+1);
}
else return;
}
size_t count_on_klay(BinTree root,size_t k)
{
//假设参数合法；
if(NULL==root) return 0;
if(k==1) return 1;
return count_on_klay(root->lchild,k-1)+count_on_klay(root->rchild,k-1);
}
size_t count_to_klay(BinTree root,size_t k)
{
//假设参数合法；
size_t count=0;
for(int i=1;i<=k;i++)
count+=count_on_klay(root,i);
return count;
}
int main()
{
BinTree T;
creatTree(T);
preOrder(T);cout<
网站名称：小代码二叉树非递归与结点计算
标题链接：http://bzwzjz.com/article/igcodj.html
