《计130121第三次作业》由会员分享，可在线阅读，更多相关《计130121第三次作业（13页珍藏版）》请在金锄头文库上搜索。
1、第三次作业一、选择题1、在一棵树中，如果结点A有3个兄弟，B是A的双亲，则B的度为 D A. 1B. 2C. 3D. 42、深度为h的完全二叉树至少有 D 个结点，至多有 B 个结点A. 2hB. 2h-1C. 2h+1D. 2h-13、具有n个结点的满二叉树有 C 个叶结点。A. n/2B. (n-1)/2C. (n+1)/2D. n/2+14、一棵具有25个叶结点的完全二叉树最多有 C 个结点。A. 48B. 49C. 50D. 515、已知二叉树的先根遍历序列是ABCDEF，中根遍历序列是CBAEDF，则后根遍历序列是 A 。A. CBEFDAB. FEDCBAC. CBEDFAD. 不
2、定6、具有10个叶结点的二叉树中有 B 个度为2的结点。A. 8B. 9C. 10D. 117、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 D 。A. 所有非叶结点均无左孩子B. 所有非叶结点均无右孩子C. 只有一个叶子结点D. A和B同时成立8、在线索二叉树中，t所指结点没有左子树的充要条件是 C 。A. t-left=NULLB. t-ltag=TRUEC. t-ltag=TRUE且t-left=NULLD. 以上都不对9、n个结点的线索二叉树上含有的线索数为 D 。A. 2nB. n-1C. n+1D. n二、填空题1、一棵二叉树有67个结点，结点的度是0和2
3、。问这棵二叉树中度为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_order 构建，S
4、uper_Print_BTREE 负责输出满二叉树类似题目输出/以下是四 五 六题的代码#include#include#include#include#include#define POW2(X) (1X)using namespace std;typedef char ele;struct Node;typedef Node* BTREE;struct Nodeele data;BTREE L;BTREE R;Node(ele _data) :data(_data) L = R = NULL; ;int toInt(char* begin, char* end)int ret = 0;wh
5、ile (begin != end) ret = ret * 10 + *begin - 0;begin+;return ret;/ 1,2,#,#,5BTREE build_BTREE(char* str)bool mark = 0;queue 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) != )
6、 +padding;/if (*(str + padding) = & padding = 1) break;root = new Node(toInt(str, str + padding);que0.push(root);str += padding + 1;continue;if (mark) p = que1.front();que1.pop();elsep = que0.front();que0.pop();while (*(str + padding) != , & *(str + padding) != ) +padding;/if (*(str + padding) = & p
7、adding = 1) break;if (*(str + padding - 1) != #)p-L = new Node(toInt(str, str + padding);if (mark) que0.push(p-L);elseque1.push(p-L);str += padding + 1;if (*str = 0) break;padding = 1;while (*(str + padding) != , & *(str + padding) != ) +padding;/if (*(str + padding) = & padding = 1) break;if (*(str
8、 + padding - 1) != #)p-R = new Node(toInt(str, str + padding);if (mark) que0.push(p-R);elseque1.push(p-R);str += padding + 1;if (mark) if (que1.empty() mark = 0;elseif (que0.empty() mark = 1;return root;void _count2(BTREE T, int& cnt)if (T)if (T-L & T-R) cnt+;_count2(T-L,cnt);_count2(T-R,cnt);int co
9、uunt2(BTREE T)int cnt = 0;_count2(T, cnt);return cnt;void print_BTREE(BTREE root )if (root)cout data;print_BTREE(root-L);print_BTREE(root-R);void print_BTREE_char(BTREE root)if (root)cout data);print_BTREE_char(root-L);print_BTREE_char(root-R);void _leafnum(BTREE T, int& cnt)if (T)if (T-L = NULL & T
10、-R = NULL)cnt+;_leafnum(T-L, cnt);_leafnum(T-R, cnt);int leafnum(BTREE T)int cnt = 0;if (T)if (T-L = NULL & T-R = NULL)cnt+;_leafnum(T-L,cnt);_leafnum(T-R,cnt);return cnt;class Super_Print_BTREEenum ChildLEFT,RIGHT;int weigth;vector vec;int middle;int GetDepth(BTREE& root,int depth)if (root)return m
11、ax(GetDepth(root-L,depth+1),GetDepth(root-R,depth+1);return (depth - 1);void FillData(BTREE& tree,int depth,int postion,bool Dir)if (tree)char sign = Dir = LEFT ? (postion = middle ? | : /) : (postion middle ? : |);vecdepth * 2 - 1postion = sign;vecdepth*2postion = tree-data;if (postion = middle)Fil
12、lData(tree-L, depth + 1, postion,LEFT);FillData(tree-R, depth + 1, postion+1,RIGHT);elseFillData(tree-L, depth + 1, postion-1,LEFT);FillData(tree-R, depth + 1, postion,RIGHT);public:void operator()(BTREE& root)if (root = NULL) return;int depth = GetDepth(root,1);weigth = POW2(depth);middle = weigth 1;vec = vector(depth*2, string(weigth + 1, );vec0middle = root-data;FillData(root-L, 1, middle - 1,LEFT);FillData(root-R, 1, mid
