5 - 1 判断题_资讯_银财中国网

5 - 1 判断题

创始人

2024-02-09 18:54:31

0次

1.一棵有124个结点的完全二叉树，其叶结点个数是确定的。T

什么是完全二叉树？（会的可以跳过）

完全二叉树：一棵深度为k的有n个结点的二叉树，对其结点按从上至下，从左至右的顺序进行编号，如果编号为i的结点与满二叉树中编号为i的结点在二叉树的位置相同，则这棵二叉树为完全二叉树。

在这里插入图片描述

因为一棵非空二叉树的第i层上最多有 2的（i-1）次方个结点，所以可以推广到完全二叉树

性质1：一棵完全二叉树的第i层上最多有 2的（i-1）次方个结点

因为一棵深度为k的二叉树中，最多有 2的k次方-1 个结点，也可以推广到完全二叉树

性质2：一棵深度为k的完全二叉树中，最多有 2的k次方-1 个结点

性质3：具有n个结点的完全二叉树的深度k为 log₂n向下取整，再+ 1。

例：有5个结点，log₂n向下取整为2，再+1为3。

由性质3可得，log₂124 向下取整 =6，再+1为7。

所以该二叉树的深度为7。

由性质2可得，深度为6的完全二叉树有2的6次方-1个结点，即63个结点。

总共有124个结点，那么还剩下124-63=61个结点，分布在第7层。

由性质1可得，第7层最多有2的（i-1）次方个结点，也就是2的6次方，最多64个，可以容纳下61个结点。

下面计算叶结点，第7层的结点全是叶节点，有61个，剩下的叶节点在第6层。

第7层的每2个结点是第6层的1个结点的左右孩子，因为61是奇数，所以最后还剩下一个结点对应第6层的一个结点。

（61-1）/2=30，即第6层有30个结点有左右孩子，有1个结点有1个孩子，第六层有2的5次方个结点，也就是32个，那么第6层没有孩子的结点有32-30-1=1个，这个结点是叶节点之一。

所以该完全二叉树共有61+1=62个叶节点

2.二叉树中序线索化后，不存在空指针域。 F

（无特殊说明的话，是没有头结点的，如果有头结点的话，为T）

第一个结点无前驱，最后一个结点无后继。

构造一个二叉树就偷点懒，用这个的结果（这叫复习/doge）：

4-14 还原二叉树&&4-15 根据后序和中序遍历输出先序遍历

生成的树：

咱们就中序线索化这个。

代码：（有头结点的中序线索二叉树，不存在空指针域）

#includeusing namespace std;typedef struct Tnode* Tree;
typedef struct Tnode{char data;Tree lchild;Tree rchild;unsigned ltag;unsigned rtag;
};Tree get(char s1[], char s2[], int n) {if (n <= 0) {return NULL;}Tree tree = (Tree)malloc(sizeof(struct Tnode));tree->lchild = NULL;tree->rchild = NULL;tree->ltag = 0;tree->rtag = 0;tree->data = s1[0];int i;for (i = 0; s2[i] != s1[0]; i++);tree->lchild = get(s1+1, s2, i);tree->rchild = get(s1 + i + 1, s2 + i + 1, n - i - 1);return tree;}int len(Tree tree) {if (tree == NULL) {return 0;}int left = len(tree->lchild);int right = len(tree->rchild);return (left >= right ? left : right) + 1;
}Tree pre;void InTreading(Tree tree) {if (tree) {InTreading(tree->lchild);if (tree->lchild == NULL) {tree->ltag = 1;tree->lchild = pre;}if (pre->rchild == NULL) {pre->rtag = 1;pre->rchild = tree;}pre = tree;InTreading(tree->rchild);}
}Tree InOrderThr(Tree tree) {Tree head = (Tree)malloc(sizeof(struct Tnode));head->lchild = 0;head->rtag = 1;head->rchild = head;if (!tree) {head->lchild = head;}else {head->lchild = tree;pre = head;InTreading(tree);pre->rchild = head;pre->rtag = 1;head->rchild = pre;}return head;
}Tree InpostNode(Tree p) {Tree post;post = p->rchild;if (p->rtag != 1) {while (post->ltag == 0) {post = post->lchild;}}return post;
}void Search(Tree tree) {Tree temp;temp = tree->lchild;while (temp->ltag == 0 && temp != tree) {temp = temp->lchild;}while(temp!=tree){printf("%c ", temp->data);temp = InpostNode(temp); }
}int main()
{int n;cin >> n;char s1[51], s2[51];for (int i = 0; i < n; i++) {cin >> s1[i];}for (int i = 0; i < n; i++) {cin >> s2[i];}Tree st= get(s1, s2, n);st = InOrderThr(st);Search(st);return 0;
}

3.对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。T

解析：考察哈弗曼树的构造方法，哈弗曼树的构造思想就是贪心的思想，每次选择权值最小的两个节点来形成新的节点，自底向上建树，因此对于一棵哈弗曼树来说，树中任一非叶节点的权值一定不小于下一层的任意节点的权值。

在构造哈夫曼树时会遇到两种情况，一种是造成树的高度增加，一种是不增加：

高度增加的情况：1,2,3,4。即每向树增加结点，树高加一