遍历二叉树

一、遍历二叉树的基本概念

二叉树是一种非线性的数据结构。在对它进行操作时,总是需要对每个数据元素逐一处理,由此提出了二叉树的遍历操作。所谓遍历二叉树,就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等各种操作。

二叉树的遍历方式分为两大类:一类按根、左子树和右子树三部分进行访问;另一类按层次访问。前者遍历二叉树的顺序存在下面 6 种可能:

TLR(根左右) TRL(根右左)
LTR(左根右) RTL(右根左)
LRT(左右根) RLT(右左根)

其中,TRL、RTL 和 RLT 3 种顺序在左右子树之间均是先右子树后左子树,这与人们先左后右的习惯不同,因此,往往不予采用。

余下的 3 种顺序 TLR、LTR 和 LRT 根据根访问的位置不同,分别被称为先序遍历(或者前序遍历)、中序遍历和后序遍历。由此可以看出:

  1. 遍历操作实际上是将非线性结构线性化的过程,其结果为线性序列,并根据采用的遍历顺序分别称为先序序列、中序序列和后序序列;

  2. 遍历子树的方法和遍历整棵树的方法一致,因此遍历操作是一个递归的过程,这 3 种遍历操作的算法可以用递归函数实现。

一棵二叉树及其经过 3 种遍历得到的相应序列如下图所示。

二叉树的 3 种遍历应用:
二叉树的 3 种遍历应用

二、先序遍历

(一) 先序遍历的基本思想

若二叉树为空,则结束遍历操作;否则

  1. 访问根节点;
  2. 先序遍历根的左子树;
  3. 先序遍历根的右子树。

(二) 先序遍历的递归算法

void BinaryTree::PreOrder(BinTreeNode *current) {
  if(current != NULL){
    cout << current->data;    //输出此结点内容

    Preorder(current->leftChild);  //遍历左子树
    Preorder(current->rightChild); //遍历右子树
  }
}

这个递归算法简单明了,这里用输出结点内容 cout << current->data 作为对访问到的结点所进行的加工处理。当然,也可以对当前访问到的结点做各种其他处理,只要将这条语句换成相应的处理函数就可以。另外,将这条语句的位置调整就能得到中序或者后序遍历的算法。下面讨论遍历的非递归算法。

(三) 利用栈的先序遍历的非递归算法

顺着二叉树的根结点从左孩子可以一直往下访问,但如何访问到各个结点的右孩子?这需要将访问过的结点记录下来。根据遍历的定义,显然后记录(存储)的结点先处理,所以必须用栈。

//带默认参数值root,注意:此函数没有在类中声明
void BinaryTree::PreOrder(BinTreeNode *p = root) {
  SeqStack S;     //见顺序栈,不同的是栈内存储的元素是指针
  while(p || !S.Empty_Stack()) {
    if(p) {
      cout << p->data << endl;
      S.Push_Stack(p);  //预留p指针在栈中
      p = p->leftChild;
    } else {
      S.Pop_Stack(p);
      p = p->rightChild;  //左子树为空,进右子树
    }       
  }
}

三、中序遍历

(一) 中序遍历的基本思想

若二叉树为空,则结束遍历操作;否则

  1. 中序遍历根结点的左子树;
  2. 访问根结点;
  3. 中序遍历根结点的右子树。

(二) 中序遍历的递归算法

void BinaryTree::InOrder(BinTreeNode *current) {
  if(current != NULL){
    InOrder(current->leftChild);
    cout << current->data;
    InOrder(current->rightChild);
  }
}

(三) 利用栈的中序遍历的非递归算法

//带默认参数值 root,注意:此函数没有在类中声明
void BinaryTree::InOrder(BinTreeNode *p = root) {
  SeqStack S;     //见顺序栈,不同的是栈内存储的元素是指针

  while(p || !S.Empty_Stack()) {
    if(p) {
      S.Push _Stack(p);  //预留p指针在栈中
      p = p->leftChild;
    } else { //左子树为空,进右子树
      S.Pop_Stack(p);
      cout << p->data << endl;
      p = p->rightChild;
    }       
  }
}

四、后序遍历

(一) 后序遍历的基本思想

若二叉树为空,则结束遍历操作;否则

  1. 后序遍历根结点的左子树;
  2. 后序遍历根结点的右子树;
  3. 访问根结点。

(二) 后序遍历的递归算法

void BinaryTree::PostOrder(BinTreeNode *current) {
  if(current != NULL) {
    PostOrder(current->leftChild);
    PostOrder(current->rightChild);
    cout << current->data;
  }
}

(三) 利用栈的后序遍历的非递归算法

仔细观察可能会发现,在先序遍历及中序遍历中,每个结点只有一次进栈和一次出栈;而在后序遍历中,每个结点在第一次出栈后,还需再次入栈,也就是说,结点要入两次栈、出两次栈,而访问结点是在第二次出栈时进行。因此,为了区别同一个结点指针的两次出栈,设置一标志 flag,令

  1. flag 为1,第一次出栈,结点不能访问
  2. flag 为0,第二次出栈,结点可以访问

当结点指针进、出栈时,其标志 flag 也同时进、出栈。

//带默认参数值 root,注意:此函数没有在类中声明
void BinaryTree::PostOrder(BinTreeNode *p= root) {
  SeqStack s1; //s1 栈存放结点指针
  SeqStack s2; //s2 栈存放标志flag

  int flag;

  while(p || !s1.Empty_Stack()) {
    if(p) {
      flag = 0;
      s1.Push_Stack(p);   //当前p指针第一次进栈
      s2.Push_Stack(flag);  //标志flag进栈
      p = p->leftChild;
    } else {
      s1.Pop_Stack(p);   //p指针出栈
      s2.Pop_Stack(flag);  //标志flag出栈

      if(flag == 0) {
        flag = 1;
        s1.Push_Stack(p);  //当前p指针第二次进栈
        s2.Push_Stack(flag); //标志flag进栈
        p = p->rightChild; //左子树为空,进右子树
      } else {     //flag为1说明是第二次出栈,访问结点
        cout << p->data << endl;
        p = NULL;
      }
    }
  }
}

五、按层次遍历二叉树

按层次遍历二叉树的实现方法为从上层到下层,每层中从左侧到右侧依次访问每个结点。二叉树按层次顺序访问其中每个结点的遍历序列如下图所示。

按层次遍历二叉树:
按层次遍历二叉树

二叉树用链式存储结构表示时,按层遍历的实现访问过程描述如下:

  1. 访问根结点,并将该结点记录下来。

  2. 若记录的所有结点都已处理完毕,则结束遍历操作;否则重复下列操作。

  3. 取出记录中第一个还没有访问孩子的结点,若它有左孩子,则访问左孩子,并记录下来;若它有右孩子,则访问右孩子,并记录下来。

显然,在这个算法中,存取记录应按照先进先出原则,因此需要使用一个队列结构完成这项操作。所谓记录访问结点,就是入队操作;而取出记录的结点就是出队操作。这样,该算法就可以描述成下列形式:

  1. 访问根结点,并将根结点入队;
  2. 当队列不空时,重复下列操作:
    • 从队列退出一个结点;
    • 若其有左孩子,则访问左孩子,并将其左孩子入队;
    • 若其有右孩子,则访问右孩子,并将其右孩子入队。
用户头像
登录后发表评论