大学课程-数据结构-数据结构常见题型

《大学课程-数据结构-数据结构常见题型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构常见解答题1：二叉树性质3的证明二叉树性质3：：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：设二叉树中结点总数为n，n1为二叉树中度为1的结点数。则n=n0+n1+n2（1）设二叉树中分支数目为B，因为二叉树中的分支都是由度为1和度为2的结点发出，所以分支数目为：B=n1+2n2（2）因为除根结点外，每个结点均对应一个进入它的分支，所以有：n=B+1。（3）将（1）（2）代入（3）中，得n0+n1+n2=n1+2n2+1，整理后得n0=n2+1，故结论成立。2：已知二叉树先序遍

2、历序列和中序遍历序列画出二叉树（或是已知后序和中序）例如已知一棵二叉树的先序序列为ABCDEFGHI中序序列为：BCAEDGHFI试画出二叉树。先序遍历是根左右，中序是左根右。做法：先确定根结点，然后确定左子树的结点，和右子树结点，画出左右子树。首先，由先序序列可知，结点A是二叉树的根结点。其次，根据中序序列，在A之前的所有结点都是根结点左子树的结点，在A之后的所有结点都是根结点右子树的结点，由此得到图(a)所示的状态。然后，再对左子树进行分解，得知B是左子树的根结点，又从中序序列知道，B的左子树为空，B的右子树只有一个结点C。接着对A的右

3、子树进行分解，得知A的右子树的根结点为D；而结点D把其余结点分成两部分，即左子树为E，右子树为F、G、H、I，如图(b)所示。接下去的工作就是按上述原则对D的右子树继续分解下去，最后得到如图(c)的整棵二叉树。AAADBDBFGIHFDEFGHIBCCECEIGH(a)(b)(c)3：线索二叉树：A对下图所示的二叉树进行线索化。CBEFDG先序线索：做法：先给出二叉树的先序遍历序列将没有左孩子的结点用虚线指向遍历序列的前驱，将没有右孩子的结点用虚线指向遍历序列的后继。中序线索与后序线索类似AACBCBEFEFDDGG(a)先序线索二叉树(b

4、)中序线索二叉树ABCEFDG(c)后序线索二叉树4：树和森林与二叉树的相互转换A转化的二叉树记住左是孩子，右是兄弟。ACDGBEFBCEDFG转换后的二叉树森林转换为二叉树森林转换为二叉树的方法如下：（1）将森林中的每棵树转换成相应的二叉树。GC（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。AAIHCBFDEBJKDG(a)一个森林CGAHEHDEIJFIJBKKF(b)森林中每棵树转换为二叉树(c)所有二叉树连接后

5、的二叉树5：赫夫曼树构造及赫夫曼编码赫夫曼树构造：（1）由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，…，Tn}；（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树