二叉树的遍历

对于二叉树来讲最主要、最基本的运算是遍历。

遍历二叉树 是指以一定的次序访问二叉树中的每个结点，并且每个结点仅被访问一次。所谓访问结点是指对结点进行各种操作的简称。例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。假设遍历二叉树时访问结点的操作就是输出结点数据域的值，那么遍历的结果得到一个线性序列。

　从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

    　（1）访问结点本身(N)，

    　（2）遍历该结点的左子树(L)，

    　（3）遍历该结点的右子树(R)。

以上三种操作有六种执行次序：

    　NLR、LNR、LRN、NRL、RNL、RLN。

注意：

  前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。

　由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

(1)先根遍历二叉树：

NLR：先根遍历(PreorderTraversal亦称(先序遍历))

         ——访问结点的操作发生在遍历其左右子树之前。

先根遍历可以递归的描述如下：

   如果根不空 : (1) 访问根结点；

   (2) 按先根次序遍历左子树；

   (3) 按先根次序遍历右子树；

   否则返回。

先根遍历的递归算法如下：

【算法6.2】

void BiTree::Preorder(NodeType*p)

{ if(p!=NULL)

 { cout<data<<" ";

  preorder(p->lch);

  preorder(p->rch);

  }

}

 

(2)中根遍历二叉树：

LNR：中序遍历(InorderTraversal)

        ——访问结点的操作发生在遍历其左右子树之中(间)。

中根遍历可以递归的描述如下：

   如果根不空 : (1) 按中根次序遍历左子树；

   (2) 访问根结点；

   (3) 按中根次序遍历右子树；；

   否则返回。

中根遍历的递归算法如下：

【算法6.3】

void BiTree::Preorder(NodeType*p)

{if(p!=NULL)

 { preorder(p->lch);

   cout<data<<" ";

   preorder(p->rch);

 }

}

 

(3)后根遍历二叉树：

LRN：后序遍历(PostorderTraversal)

         ——访问结点的操作发生在遍历其左右子树之后。

后根遍历可以递归的描述如下：

如果根不空 : (1) 按后根次序遍历左子树；

   (2) 按后根次序遍历右子树；

   (3) 访问根结点；

   否则返回。

后根遍历的递归算法如下：

【算法6.4】

void BiTree::Preorder(NodeType*p)

{ if(p!=NULL)

 { preorder(p->lch);

  preorder(p->rch);

  cout<data<<" ";

  }

}