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

第四次作业
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
E
二叉树B
2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
。
。
(同一层自左至右)遍历二叉树的算法(或:按层次输出二叉树中所有结点) 。
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
E
二叉树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).
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