多做题,通过考试没问题!

数据结构

睦霖题库>大学试题(计算机科学)>数据结构

设如下图所示的二叉树B的存储结构为二叉链表,root为根指针,结点结构为:(lchild,data,rchild)。其中lchild,rchild分别为指向左右孩子的指针,data为字符型,root为根指针,试回答下列问题: 假定二叉树B共有n个结点,试分析算法traversal(root)的时间复杂度。

正确答案:特点:①每个结点肯定都会被打印两次;②但出现的顺序不同,其规律是:凡是有左子树的结点,必间隔左子树的全部结点后再重复出现;如A,B,D等结点。反之马上就会重复出现。如C,E,F,G等结点。
时间复杂度以访问结点的次数为主,精确值为2*n,时间渐近度为O(n).
答案解析:
进入题库查看解析

微信扫一扫手机做题