计130121第三次作业教材.doc

第三次作业 一、选择题 1、在一棵树中，如果结点A有3个兄弟，B是A的双亲，则B的度为 D A. 1 B. 2 C. 3 D. 4 2、深度为h的完全二叉树至少有 D 个结点，至多有 B 个结点 A. 2h B. 2h-1 C. 2h+1 D. 2h-1 3、具有n个结点的满二叉树有 C 个叶结点。 A. n/2 B. (n-1)/2 C. (n+1)/2 D. n/2+1 4、一棵具有25个叶结点的完全二叉树最多有 C 个结点。 A. 48 B. 49 C. 50 D. 51 5、已知二叉树的先根遍历序列是ABCDEF，中根遍历序列是CBAEDF，则后根遍历序列是 A 。 A. CBEFDA B. FEDCBA C. CBEDFA D. 不定 6、具有10个叶结点的二叉树中有 B 个度为2的结点。 A. 8 B. 9 C. 10 D. 11 7、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 D 。 A. 所有非叶结点均无左孩子 B. 所有非叶结点均无右孩子 C. 只有一个叶子结点 D. A和B同时成立 8、在线索二叉树中，t所指结点没有左子树的充要条件是 C 。 A. t-left=NULL B. t-ltag=TRUE C. t-ltag=TRUE且t-left=NULL D. 以上都不对 9、n个结点的线索二叉树上含有的线索数为 D 。 A. 2n B. n-1 C. n+1 D. n 二、填空题 1、一棵二叉树有67个结点，结点的度是0和2。问这棵二叉树中度为2的结点有 33 个。 2、含A, B, C三个结点的不同形态的二叉树有 5 棵。 3、含有4个度为2的结点和5个叶子结点的完全二叉树，有 1或0 个度为1的结点。 4、具有100个结点的完全二叉树的叶子结点数为 50 。 5、在用左右链表示的具有n个结点的二叉树中，共有 2n 个指针域，其中 n-1 个指针域用于指向其左右孩子，剩下的 n+1 个指针域是空的。 三、试分别画出具有4个结点的二叉树的所有不同形态。 四、已知一棵二叉树的中根序列和后根序列分别是BDCEAHFG和DECBHGFA，请画出此二叉树。 二叉树由build_BTREE_from_pre_in_orderSuper_Print_BTREE 负责输出 题目输出/////以下是四 五 #includeiostream #includequeue #includestring #includevector #includecmath #define POW2(X) (1X) using namespace std; typedef char ele; struct Node; typedef Node* BTREE; struct Node{ ele data; BTREE L; BTREE R; Node(ele _data) :data(_data){ L = R = NULL; } }; int toInt(char* begin, char* end){ int ret = 0; while (begin != end) { ret = ret * 10 + *begin - 0; begin++; } return ret; } // {1,2,#,#,5} BTREE build_BTREE(char* str){ bool mark = 0; queueBTREE que0, que1; int padding; BTREE root = NULL, p = NULL; str++; if (*str == }) return NULL; while (*str != 0) { padding = 1; if (root == NULL){ while (*(str + padding) != , *(str + padding) != }) ++padding; //if (*(str + padding) == } padding == 1) break; root = new Node(toInt(str, str + padding)); que0.push(root); str += pa