论坛 › 数据结构与算法 › 前序遍历代码的理解

仅有的倔强 发表于 2018-8-21 10:43:11

前序遍历代码的理解

左边是 题目， 右边是 代码

leve 结点所在的层数

从A 开始遍历，level=1;
然后 又遍历了A的左孩子， B， level+1=2；
当又遍历B的左孩子的时候， B没有左孩子，但level 还是加 1 变成了 3是吗？？？
此时，T 是 结点B的地址， T->rchild，开始遍历右孩子， leve+1 不是变成了 4了嘛。不是不对了嘛   

请问 我哪里想错了 ？？ 请指教

claws0n 发表于 2018-8-21 11:29:22

本帖最后由 claws0n 于 2018-8-21 11:32 编辑

姐姐好~ 上次链表的还没解决？？第二个的

这道题，只有三层，哪来 level 4？
递归与函数作用域的问题~

void PreOrderTraverse(BiTree T, int level)
{
        if(T)
        {
                visit(T->data, level);   #这个只是打印数据而已
                PreOrderTraverse(T->lchild, level +1);
                PreOrderTraverse(T->rchild, level +1);
        }
}

二叉树：AB DCE   #
一开始 visit >> A level 1 接 PreOrderTraverse(T->lchild, level +1)
      进入新函数的作用域 visit >> B level 2 接 PreOrderTraverse(T->lchild, level +1)
             T == NULL，退出，回到上一个函数的作用域
      PreOrderTraverse(T->rchild, level +1)>> D level 3，函数体执行完毕
A 的 rchild 还没有执行 visit >> C level 2

以此类推。用缩进说明递归的层数。因为 level 是局部变量，所以它们的值在每一层是不会互相影响的~

claws0n 发表于 2018-8-21 11:49:52

比较完整的分析
level = 1
visit >> A, level 1
A->lchild, level + 1 == 2
    T != NULL
    visit >> B, level 2
    B->lchild
      T == NULL
    B->rchild, level +1 == 3
      T != NULL
      visit >> D, level 3
      D->lchild, level +1 == 4
            T == NULL
      D->rchild, level +1 == 4
            T == NULL
A->rchild, A.level == 1, level + 1 == 2
    T != NULL
    visit >> C, level 2
      C->rchild, level +1 == 3
            T != NULL
            visit >> E, level 3
            E->lchild, level +1 == 4
                  T == NULL
            E->rchild, level +1 == 4
                  T == NULL

仅有的倔强 发表于 2018-8-21 14:11:10

claws0n 发表于 2018-8-21 11:49
比较完整的分析
level = 1
visit >> A, level 1


嗯嗯嗯谢谢你这么详细的为我解答

A->lchild, level + 1 == 2
      T != NULL
    visit >> B, level 2
    B->lchild
      T == NULL

为什么到了B的地方的时候， 先是判断 第 它的左孩子 是不是空，才决定 level 加不加 一
而之前 都是 直接 加上 1，再判断 T 是不是空的

   

claws0n 发表于 2018-8-21 14:25:25

仅有的倔强 发表于 2018-8-21 14:11
嗯嗯嗯谢谢你这么详细的为我解答

A->lchild, level + 1 == 2


因为是前序遍历，遍历函数的优先次序
void PreOrderTraverse(BiTree T, int level)
{
    if(T)
    {
      visit(T->data, level);   // 打印 A
      PreOrderTraverse(T->lchild, level +1);                //接下来是寻找 A 的左孩子
                //展开
                if(T)
                {
                      visit(T->data, level);   // 打印 B
                      PreOrderTraverse(T->lchild, level +1);                //接下来是寻找左孩子，左孩子为空，跳出函数
                      PreOrderTraverse(T->rchild, level +1);                //接下来是寻找右孩子，找到 D ……两个空孩子
                }                //B结点遍历完毕
      PreOrderTraverse(T->rchild, level +1);                // 寻找 A 的右孩子
    }
}

仅有的倔强 发表于 2018-8-21 14:53:15

claws0n 发表于 2018-8-21 14:25
因为是前序遍历，遍历函数的优先次序
void PreOrderTraverse(BiTree T, int level)
{


void PreOrderTraverse(BiTree T, int level)      此时level 是1
{
    if(T)
    {
      visit(T->data, level);   // 打印 Alevel=1
      PreOrderTraverse(T->lchild, level +1);                //接下来是寻找 A 的左孩子,level=2
                //展开
                if(T)
                {
                      visit(T->data, level);   // 打印 B   level=2
                      PreOrderTraverse(T->lchild, level +1);                //寻找B的左孩子， level=3？？？
                      PreOrderTraverse(T->rchild, level +1);                //接下来是寻找右孩子，找到 D ……两个空孩子
                }                //B结点遍历完毕 \
      PreOrderTraverse(T->rchild, level +1);             \
    }
}



    它每次调用它自己的时候， 都是先将level 加一， 不管 孩子结点是否为空哇， 我看着是，
    然后 才进去 判断 孩子结点 是否为空， 就跳出来了循环， 但是 level 之前是加了1 的 。 它并没有改变

仅有的倔强 发表于 2018-8-21 14:55:14

claws0n 发表于 2018-8-21 11:29
姐姐好~ 上次链表的还没解决？？第二个的

这道题，只有三层，哪来 level 4？


恩上次的链表也算解决吧按照自己理解的 算是想通拉
谢谢你每次的 帮忙解决问题

仅有的倔强 发表于 2018-8-21 14:56:41

claws0n 发表于 2018-8-21 11:49
比较完整的分析
level = 1
visit >> A, level 1


恩
在我看来是这样的

A->lchild, level + 1 == 2
      T != NULL
    visit >> B, level 2
    B->lchild，level 3
      T == NULL
B->rchild ,level 4

仅有的倔强 发表于 2018-8-21 15:06:30

claws0n 发表于 2018-8-21 14:25
因为是前序遍历，遍历函数的优先次序
void PreOrderTraverse(BiTree T, int level)
{


void PreOrderTraverse(BiTree T, int level)    level==1
{
    if(T)
    {
      visit(T->data, level);   // 打印 A      level==1
      PreOrderTraverse(T->lchild, level +1);                //接下来是寻找 A 的左孩子level==2
                //展开
                if(T)
                {
                      visit(T->data, level);   // 打印 B      level==2
                      PreOrderTraverse(T->lchild, level +1);                //接下来是寻找左孩子，level==3
                      PreOrderTraverse(T->rchild, level +1);                //接下来是寻找右孩子，level==4
                }                //B结点遍历完毕
      PreOrderTraverse(T->rchild, level +1);                // 寻找 A 的右孩子
    }
}



我突然觉得我有点乱乱的啦， 明明知道是错的，   是因为我没有搞清楚 level 作用域的关系吗

claws0n 发表于 2018-8-21 15:09:51

仅有的倔强 发表于 2018-8-21 14:56
恩
在我看来是这样的



嗯，如果问题解决了，可以回到帖子编辑成已经解决或采纳答案
还好，略懂，没理解很透，姐姐给机会复习{:5_91:}

level 是局部变量，每进入函数一次，将采用函数外最后一个被定义的值。而在函数内部的任何操作将不会作用到函数外部的值
level 1
{
    level 2
    {
         level 3
   }
    level 2
}
如果 level 有 static 的修饰，才会是你说的情形

仅有的倔强 发表于 2018-8-21 15:32:10

claws0n 发表于 2018-8-21 15:09
嗯，如果问题解决了，可以回到帖子编辑成已经解决或采纳答案
还好，略懂，没理解很透，姐姐给机会复习 ...

嗯嗯呢恩   对 我的问题就是出在了 level 的作用域上， 我或许懂了，谢谢你！

查看完整版本: 前序遍历代码的理解