20210504

五四青年节 | 回顾 | GS2-660-C3-42~50,157~159 | 数据结构-树(四)

Table of Contents

五四青年节快乐!不要在这个年纪安逸!!

回顾

GS2-660-C3-42~50,157~159

开始第三章了,今天碰到几个题都用到了极值的第二充分条件,在这里mark一下。

数据结构-树(四)

二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得某个结点被访问一次且仅被访问一次。

二叉树的遍历-广度优先遍历-层次遍历

若树为空,则空操作返回,否则

  1. 从树的第一层,也就是根结点开始访问
  2. 从上而下逐层遍历
  3. 在同一层中,按从左到右的顺序对结点逐个访问

二叉树的遍历-深度优先遍历-先序遍历

若二叉树为空,则空操作返回,否则

  1. 访问结点
  2. 前序遍历子树,
  3. 前序遍历子树.

遍历的顺序为:ABDGHCEIF

/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BiTree T)
{
if(T==NULL) //若树为空,返回为空
return;
printf("%c",T->data); //显示结点数据,可以更改为其它对结点操作
PreOrderTraverse(T->lchild); //再先序遍历左子树
PreOrderTraverse(T->rchild); //最后先序遍历右子树
}

二叉树的遍历-深度优先遍历-中序遍历

若树为空,则空操作返回,否则

  1. 从根结点开始(注意不是先访问根结点)
  2. 中序遍历根结点的左子树,然后是访问根结点
  3. 中序遍历右子树

遍历的顺序为GDHBAEICF

/*二叉树的中序遍历递归算法*/
void InOrderTraverse(BiTree T)
{
    if(T == NULL)
            return;
    InOrderTraverse(T->lchild);    //中序遍历左子树
    printf("%c",T->data);                //显示结点数据,能够更改为其它对结点操作
    InOrderTraverse(T->rchild);    //最后中序遍历右子树
}

二叉树的遍历-深度优先遍历-后序遍历

若树为空,则空操作返回,否则

  1. 从左到右先叶子后结点的方式遍历访问左右子树
  2. 最后是访问根结点.

遍历的顺序为:GHDBIEFCA

/*二叉树的后序遍历递归算法*/
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild);//先后序遍历左子树
PostOrderTraverse(T->rchild);//再后序遍历右子树
printf("%c",T->data); //显示结点数据。能够更改为其它对结点操作
}

例题

分析:本题从3开始就已经不符合所学的三种深度优先遍历与层次遍历,可以先给遍历序列编个号观察规律,如图:

不难发现:在遍历完2的右子树之后才开始访问2,最后一个是4,即遍历完2的右子树之后再遍历2的左子树。同样地也满足遍历完1的右子树之后然后访问1,最后遍历1的左子树。

即先,选C


(一般)树的遍历

  • 层次遍历 √(与二叉树完全一样)
  • 先序遍历 √
  • 后序遍历 √
  • 中序遍历!不存在!!

如果一棵树被转换成了一颗二叉树,那么如何对这棵树执行我们想要的某种遍历呢?

二叉树
先序:A1 A2 A5 A6 A3 A4 先序:A1 A2 A5 A6 A3 A4
后序:A5 A6 A2 A3 A4 A1 中序:A5 A6 A2 A3 A4 A1

结论:

  1. 如果一棵二叉树是由某棵树转换而来,那对这棵二叉树进行先序遍历就等效于对原来的树进行先序遍历 2. 对这棵二叉树进行中序遍历就等效于对原来的树进行后序遍历。

森林的遍历

与树类似,也是没有中序遍历。

森林 二叉树
先序:A1 A2 A3 A5 A6 A4 A7 A8 A9 A10 A11 A12 A13 先序:一样
后序:A2 A5 A6 A3 A4 A1 A8 A9 A10 A7 A12 A13 A11 中序:才一样

则对二叉树:

  • 先序遍历 <=> 对原森林 先序遍历
  • 中序遍历 <=> 对原森林 后序遍历