第四次作业
1. 设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：
(1).对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果； C的结点类型定义如下： struct node {char data;
struct node *lchild, rchild; };
C算法如下：
void traversal(struct node *root) {if (root)
{printf(“%c”, root->data); traversal(root->lchild); printf(“%c”, root->data); traversal(root->rchild); } }
(2).假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。
A
B D
C F G 二叉树B
E
2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
3.把如图所示的树转化成二叉树。
1 / 4
4.画出和下列二叉树相应的森林。
5.编写按层次顺序（同一层自左至右）遍历二叉树的算法 (或:按层次输出二叉树中所有结点) 。
1. 设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：
(1).对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果； C的结点类型定义如下： struct node {char data;
struct node *lchild, rchild; };
C算法如下：
void traversal(struct node *root) {if (root)
{printf(“%c”, root->data); traversal(root->lchild); printf(“%c”, root->data); traversal(root->rchild); } }
(2).假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。
A
B D
C F G 二叉树B
E
解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：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).
2 / 4
2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A
3.把如图所示的树转化成二叉树。
答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。 A B
E C
K F H D L G I
M J
4.画出和下列二叉树相应的森林。
答：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。
5.编写按层次顺序（同一层自左至右）遍历二叉树的算法 (或:按层次输出二叉树中所有结点) 。
解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。
3 / 4
这是一个循环算法，用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
4 / 4
南京工业大学数据结构作业参考答案作业
