Tree traversal

遍历是二叉树各种操作的基础。

在计算机程序中,遍历本身是一个线性操作。所以,遍历同样是具有线性结构的数组或者链表等,是一件轻而易举的事情。反观二叉树,是典型的非线性数据结构。那么在遍历的时候,就需要将非线性关联的节点转换成一个线性的序列。从宏观角度来看,二叉树的遍历可分为深度优先遍历和广度优先遍历。

深度优先和广度优先这两个概念,不止局限于二叉树,它们更是一种算法思想,决定了以怎样的方式来访问那些复杂的数据结构。

深度优先遍历:先序、中序、后序。

上述三种遍历算法均可使用递归描述。

以中序遍历为例,简单说明:


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) {
      Push(S,p); // 当前节点入栈
      p = p->lchild;
    }
    // 首次运行,从左子树的最左边的左孩子节点开始回溯
    else {
      Pop(S,p);
      visit(p);
      p = p->rchild;
    }
  }
}

广度优先遍历:层次遍历。


void LevelOrder(BiTree T) {
  InitQueue(Q);
  BiTree p;
  EnQueue(Q,T); // 将根节点入队
  while(!isEmpty(Q)) {
    DeQueue(Q,p); // 队头节点出队
    visit(p);
    if(p->lchild != NULL) {
      EnQueue(Q,p->lchild);
    }
    if(p->rchild != NULL){
      EnQueue(Q,p->rchild)
    }
  }
}