南京工业大学 数据结构 作业答案 作业4

《南京工业大学 数据结构 作业答案 作业4》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四次作业1.设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：(1).对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；C的结点类型定义如下：structnode{chardata;structnode*lchild,rchild;};C算法如下：voidtraversal(structnode*root){if(root

2、){printf(“%c”,root->data);traversal(root->lchild);printf(“%c”,root->data);traversal(root->rchild);}}(2).假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。ABDCFGE二叉树B2.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。3.把如图所示的树转化成二叉树。4.画出和下列二叉树相应的森林。5.编写按层次顺序（同一层自左至右）遍历二叉树的算法(或:按层次输出二叉树中所有结点

3、)。1.设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：(1).对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；C的结点类型定义如下：structnode{chardata;structnode*lchild,rchild;};C算法如下：voidtraversal(structnode*root){if(root){p

4、rintf(“%c”,root->data);traversal(root->lchild);printf(“%c”,root->data);traversal(root->rchild);}}(2).假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。ABDCFGE二叉树B解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：ABCCEEBADFFDGG特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A

5、，B，D等结点。反之马上就会重复出现。如C，E，F，G等结点。时间复杂度以访问结点的次数为主，精确值为2*n，时间渐近度为O(n).2.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答：DLR：ABDFJGKCEHILMLDR:BFJDGKACHELIMLRD：JFKGDBHLMIECA3.把如图所示的树转化成二叉树。答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。ABECKFHDLGIMJ4.画出和下列二叉树相应的森林。答：注意根右边的子

6、树肯定是森林，而孩子结点的右子树均为兄弟。5.编写按层次顺序（同一层自左至右）遍历二叉树的算法(或:按层次输出二叉树中所有结点)。解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，……以此产生了按层次输出的效果。层序遍历二叉树的递归算法voidLayerOrder(BitreeT)//层序遍历二叉树{InitQueue(

7、Q);//建立工作队列EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);visit(p);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}//LayerOrder