遍历二叉树的代码实现

二叉树的遍历

• ​​先序遍历（根--左--右）​​

• ​​递归法​​
• ​​非递归法​​

• ​​中序遍历（左--根--右）​​

• ​​递归法​​
• ​​非递归法​​

• ​​后序遍历（左--右--根）​​

• ​​递归法​​
• ​​非递归法​​

• ​​层序遍历​​

先序遍历（根–左--右）

递归法

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);  //右孩子入队
    }
  }     
}