1、第四次作业1. 设如下图所示的二叉树 B 的存储结构为二叉链表，root 为根指针，结点结构为：（lchild,data,rchild） 。其中 lchild，rchild 分别为指向左右孩子的指针， data 为字符型，root为根指针，试回答下列问题：(1).对下列二叉树 B，执行下列算法 traversal(root)，试指出其输出结果；C 的结点类型定义如下：struct nodechar data;struct node *lchild, rchild;C 算法如下：void traversal(struct node *root)if (root)printf(“%c”, root
2、-data);traversal(root-lchild);printf(“%c”, root-data);traversal(root-rchild);(2).假定二叉树 B 共有 n 个结点，试分析算法 traversal(root)的时间复杂度。二叉树 B2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。3.把如图所示的树转化成二叉树。AB DC F GE4.画出和下列二叉树相应的森林。5.编写按层次顺序（同一层自左至右）遍历二叉树的算法 (或:按层次输出二叉树中所有结点) 。1. 设如下图所示的二叉树 B 的存储结构为二叉链表，root 为根指针，结点结构为：（l
3、child,data,rchild） 。其中 lchild，rchild 分别为指向左右孩子的指针， data 为字符型，root为根指针，试回答下列问题：(1).对下列二叉树 B，执行下列算法 traversal(root)，试指出其输出结果；C 的结点类型定义如下：struct nodechar data;struct node *lchild, rchild;C 算法如下：void traversal(struct node *root)if (root)printf(“%c”, root-data);traversal(root-lchild);printf(“%c”, root-da
4、ta);traversal(root-rchild);(2).假定二叉树 B 共有 n 个结点，试分析算法 traversal(root)的时间复杂度。二叉树 B解：这是“先根再左再根再右” ，比前序遍历多打印各结点一次，输出结果为：A B C C E E B A D F F D G G特点：每个结点肯定都会被打印两次；但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如 A，B，D 等结点。反之马上就会重复出现。如 C，E，F，G 等结点。时间复杂度以访问结点的次数为主，精确值为 2*n，时间渐近度为 O(n).AB DC F GE2. 试写出如图所示的二叉
5、树分别按先序、中序、后序遍历时得到的结点序列。答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A3.把如图所示的树转化成二叉树。答：注意全部兄弟之间都要连线（包括度为 2 的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。ABE CK F H DL G IM J4.画出和下列二叉树相应的森林。答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。5.编写按层次顺序（同一层自左至右）遍历二叉树的算法 (或:按层次输出二叉树中所有结点) 。解
6、：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用 while 语句不断循环，直到队空之后自然退出该函数。技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，以此产生了按层次输出的效果。层序遍历二叉树的递归算法void LayerOrder(Bitree T) /层序遍历二叉树 InitQueue(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
