先序遍历(根--左--右)
递归法
void PreOrder(BiTree T){
if(T != NULL){
visit(T); //访问根节点
PreOrder(T->lchild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}
非递归法
void PreOrder(BiTree T){
InitStack(S); //使用栈存储二叉树的节点
BiTree p = T; //p为遍历二叉树的指针
while(p || !IsEmpty(S)){ //二叉树不为空或栈不空是继续循环
if(p != NULL){
vist(p) //访问拍p
Push(S,p); //p节点入栈
p = p->lchild; //继续向左遍历
}
else{
Pop(S,p); //p出栈
p = p->rchild; //转向右子树遍历
}
}
}
中序遍历(左--根--右)
递归法
void InOrder(BiTree T){
if(T != NULL){
InOrder(T->lchild); //递归遍历左子树
visit(T); //访问根节点
InOrder(T->rchild); //递归遍历右子树
}
}
非递归法
void InOrder(BiTree T){
InitStack(S); //使用栈存储二叉树的节点
BiTree p = T; //p为遍历二叉树的指针
while(p || !IsEmpty(S)){ //二叉树不为空或栈不空是继续循环
if(p != NULL){
Push(S,p); //p节点入栈
p = p->lchild; //继续向左遍历
}
else{
Pop(S,p); //p出栈
visit(p); //访问p
p = p->rchild; //转向右子树遍历
}
}
}
后序遍历(左--右--根)
递归法
void PostOrder(BiTree T){
if(T != NULL){
PostOrder(T->lchild); //递归遍历左子树
PostOrder(T->rchild); //递归遍历右子树
visit(T); //访问根节点
}
}
非递归法
void PostOrder(BiTree T){
InitStack(S); //使用栈存储二叉树的节点
BiTree p = T; //p为遍历二叉树的指针
BiTree r = NULL; //记录最近访问的节点
while(p || !IsEmpty(S)){ //二叉树不为空或栈不空是继续循环
if(p != NULL){
Push(S,p); //p节点入栈
p = p->lchild; //继续向左遍历
}
else{
GetTop(S,p); //读取栈顶节点,不出栈
if(p->rchild && p->rchild != r){ //右子树存在,且未被访问
p = p->rchild;
Push(S,p); //p节点入栈
p = p->lchild; //转左遍历
}
else{
Pop(S,p); //p出栈
visit(p); //访问p
r = p; //记录最近一次访问的节点
p = NULL;
}
}
}
}
层序遍历
void LevelOrder(BiTree T){
InitQueue(Q); //使用队列存储二叉树节点
BiTree p;
EnQueue(Q,T); //根节点入队
while(!IsEmpty(Q)){ //队列不空继续循环
DeQueue(Q,p); //队头节点出队
vist(p); //访问队头节点
if(p->lchild != NULL){
EnQueue(Q,p->lchild); //左孩子入队
}
if(p->rchild != NULL){
EnQueue(Q,p->rchild); //右孩子入队
}
}
}