赞
踩
1.前序遍历
void PerOrder(BiTree T){
BiTree p=T;
if(p){
visit(p);//访问节点并输出
PerOrder(p->lchild);//递归访问左子树
PerOrder(p->rchild);//递归访问右子树
}
}
2.中序遍历
void InOrder(BiTree T){
BiTree p=T;
if(p){
InOrder(p->lchild);//递归访问左子树
visit(p);//访问节点并输出
InOrder(p->rchild);//递归访问右子树
}
}
3.后序遍历
void PostOrder(BiTree T){
BiTree p=T;
if(p){
PostOrder(p->lchild);//递归访问左子树
PostOrder(p->rchild);//递归访问右子树
visit(p);//访问节点并输出
}
}
1.前序遍历
void preorder(BiTree T){
BiTree p=T;
InitStack(s);//初始化一个栈
while(p||!isEmpty(s)){
if(p){//一路向左
visit(p);//访问根节点
push(s,p);//将节点压入栈中
p=p->lchild;
}
else{
pop(s,p);//出栈并访问右子树
p=p->rchild;
}
}
}
2.中序遍历
void Inorder(BiTree T){
BiTree p=T;
InitStack(s);
while(p||!isEmpty(s)){
if(p){
push(s,p);
p=p->lchild;
}
else{
pop(s,p);
visit(p);
p=p->rchild;
}
}
}
3.后序遍历
void PostOrder(BiTree T){ BiTree p=T; BiTree r=null; InitStack(s); 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); r=p; p=null; } } } }
4.层次遍历
void LevelOrder(BiTree T){
BiTree p=T;
InitQueue(q);
EnQueue(q,p);
while(!isEmpty(q)){
DeQueue(q,p);
visit(p);
if(p->lchild){
EnQueue(q,p->lchild);
}
if(p->rchild){
EnQueue(q,p->rchild);
}
}
}
思想:正常层次遍历是自上而下,从左到右遍历的,正好与题设相反,要得到相反的输出结果,我们首先想到的是栈,因为栈是一种后进先出的数据结构,能够使输入结果逆序的输出。
即当节点出队时,就进入队列,到最后出栈时访问
void LevelOrder(BiTree T){ BiTree p=T; InitQueue(q); InitStack(s); EnQueue(q,p); while(!isEmpty(q)){ DeQueue(q,p); push(s,p); visit(p); if(p->lchild){ EnQueue(q,p->lchild); } if(p->rchild){ EnQueue(q,p->rchild); } } while(!isEmpty(s)){ pop(s,p); visit(p); } }
1.递归算法(使用前序遍历为例)
int BtDepth(BiTree T,int depth){
BiTree p=T;
if(!p){
return 0;
}
int l=BtDepth(p->lchild);//递归访问左子树
int r=BtDepth(p->rchild);//递归访问右子树
return (l>r?l:r)+1;
}
2.非递归算法(使用层序遍历)
思想:使用层次遍历数列,设置变量level记录当前指针所在层,并设置变量last指向当前层的最右节点。每次遍历访问节点时,都应该比较当前指针和last的值是否相同,如果相等level加一,last指向下一层节点的最右节点。如果不同则直接遍历下一个节点。
int BtDepth(BiTree T){ BiTree p=T; int level=0; int front=-1,rear=-1;; int last=0; InitQueue(q); q[++rear]=p; while(!isEmpty(q)){ p=q[++front]; if(p->lchild){ q[++rear]=p->lchild; } if(p->rchild){ q[++rear]=p->rchild; } if(front==last){ level++; last=rear; } } return level; }
思想:使用层序遍历去遍历每一个节点入队(空节点也入队),遇到空节点时,查看这个节点后是否有空节点,如果有,那就不是完全二叉树
bool isComplete(BiTree T){ BiTree p=T; if(!p) return 1; InitQueue(q); EnQueue(q,p); while(!isEmpty(q)){ DeQueue(q,p); if(p){ EnQueue(q,p->lchild); EnQueue(q,p->rchild); } else{ while(!isEmpty(q)){ DeQueue(q,p); if(p){ return 0; } } retuen 1; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。