1. 非递归中序遍历
void Inorder(Bitree T){
InitStack(s); //初始化栈以及所需变量
Bitree p=T;
while(p||!IsEmpty(s)){//循环条件
if(p){ //执行单元的条件
Push(S,p); //左全入栈
p=p->lchild
}
else{
Pop(S,p);visit(p);//左先访问然后根
p=p->rchild; //左子树和根节点的右子树都要访问写在一起
}
}
}
2. 非递归后序遍历
void Postorder(Bitree T){
InitStack(S);
BiNode *p=T; //工作指针
r=NULL; //区分前一个访问的是左还是右
while(p||!IsEmpty(S))//循环条件
{
if(p){ //老三样 先左全入
Push(S,p);
p=p->lchild;
}
else{
GetTop(S,p);//取栈顶
if(p->rchild&&p->rchild!=r){//在访问根节点起作用，若是右则不执行
p=p->rchild;
Push(S,p);//右节点在根前面插队
p=p->lchild;
}
else{//最后
pop(S,p);
visit(p->data);//左右节点都是确定为叶子才访问，根节点是确定左右都访问过才访问
r=p;
p=NULL;
}
}
}
}
3. 层次遍历
void LevelOrder(Bitree T){
InitQueue(Q);
BiTree p;
EnQueue(Q,T);//第一个根节点入队需要提前免得循环进不去
while(!IsEmpty){
DeQueue(Q,P);//队头指针取出并当作根节点
visit(p);
if(p->lchild!=NULL)
EnQueue(Q,p->lchild);
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
4. 依据中序和先序序列构造二叉树
依据先序确定第一个根节点，再根据中序确定左右子树长度，在左右子树回到第一步先确定根节点再确定左右子树
Bitree PreInCreat(Elemtype A[],Elemtype B[],int l1,int h1,int l2,int h2){
//l1 h1是先序的第一个点和最后一个点的下标
BiNode root=(Binode *)malloc(sizeof(BiNode));
root= A[l1];
for(int i=l2;B[i]!=root->data;i++)
llen=i-l2;
rlen=h2-i;
if(llen)
root->lchild=PreInCreat(A,B,l1+1,l1+llen,
l2,l2+llen-1
)
else
root->lchld=NULL;
if(rlen)
root->rchild=PreInCreat(A,B,h1-rlen+1,h1,h2-rlen+1,h2);
else
root->rchild=NULL;
return root;
}
5. 确定二叉树是否为完全二叉树
利用层次遍历，若遇到节点非空则左右子树入队，若遇到节点为空则使用一个while找后面节点若有不为空的则不是完全二叉树
