20210504

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

回顾

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

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

数据结构-树（四）

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

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

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

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

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

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

1. 先访问根结点
2. 前序遍历左子树,
3. 前序遍历右子树.

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

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

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

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

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

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

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

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

/*二叉树的后序遍历递归算法*/
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。

（一般）树的遍历

• 层次遍历 √（与二叉树完全一样）
• 先序遍历 √
• 后序遍历 √
• 中序遍历！不存在！！

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

结论：

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

森林的遍历

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

则对二叉树：

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