试题详情
简答题设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild，data，rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题： 假定二叉树B共有n个结点，试分析算法traversal（root）的时间复杂度。
  • 特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A，B，D等结点。反之马上就会重复出现。如C，E，F，G等结点。
    时间复杂度以访问结点的次数为主，精确值为2*n，时间渐近度为O（n）.

  • 关注下方微信公众号，在线模考后查看

热门试题