假设二叉树中每个节点值为单个字符，采用二叉链存储结构存储。设计一个算法求二叉树b的最小枝长。所谓最小最小枝长是指的是根节点到最近叶子节点的路径长度。
题目
假设二叉树中每个节点值为单个字符，采用二叉链存储结构存储。设计一个算法求二叉树b的最小枝长。所谓最小最小枝长是指的是根节点到最近叶子节点的路径长度。
相似考题
更多“假设二叉树中每个节点值为单个字符，采用二叉链存储结构存储。设计一个算法求二叉树b的最小枝长。所谓最小最小枝长是指的是根节点到最近叶子节点的路径长度。”相关问题
-
第1题：
假设一棵平衡二叉树的每个结点都表明了平衡因子b,试设计一个算法,求平衡二叉树的高度。参考答案：因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左(当b=1时)或右(当b=-1时)向下查找。
[算法描述]
int Height(BSTree t)
// 求平衡二叉树t的高度
{level=0;p=t;
while(p)
{level++; // 树的高度增1
if(p->bf<0)p=p->rchild;//bf=-1 沿右分枝向下
//bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存储定义
else p=p->lchild; //bf>=0 沿左分枝向下
}//while
return (level);//平衡二叉树的高度
} //算法结束
-
第2题：
某二叉树中度为2的节点有n个，则该二叉树中有______个叶子节点。
正确答案：n+1
n+1 解析：在任意一棵二叉树中，度为0的节点(即叶子节点)总是比度为0的节点多一个。 -
第3题：
阅读以下函数说明和C代码，将C程序中(1)～(5)空缺处的内容补充完整。
【说明】
对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a,b,c,d}及其权值2、7、4、5，可构造如图6-15所示的最优二叉树，以及相应的结构数组Ht(如表6-14所示，其中数组元素Ht[0]不用)。
结构数组Ht的类型定义如下：
define MAXLEAFNUM 20
struct node{
char ch; /*扫当前节点表示的字符，对于非叶子节点，此域不用*/
Int weight； /*当前节点的权值*/
int parent; /*当前节点的父节点的下标，为0时表示无父节点*/
int lchild, rchild;
/*当前节点的左、右孩子节点的下标，为0时表示无对应的孩子节点*/
)Ht[2*MAXLEAFNUM];
用“0”或“广标识最优二叉树中分支的规则是：从一个节点进入其左(右)孩子节点，就用“0”(或“1”)标识该分支，如图6-15所示。
若用上述规则标识最优二叉树的每条分支后，从根节点开始到叶子节点为止，按经过分支的次序将相应标识依次排列，可得到由“0”、“1”组成的一个序列，称此序列为该叶子节点的前缀编码。例如，图6-15所示的叶子节点a、b、c、d的前缀编码分别是110、0、111、10。
函数void LeafCode(int root,int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子节点，为所有的叶子节点构造前缀编码。其中，形参root为最优二叉树的根节点下标；形参n为叶子节点个数。在函数void LeafCode(int root,int n)构造过程中，将Ht[p].weight域用做被遍历节点的遍历状态标志。
函数void Decode(char *buff,int root)的功能是：将前缀编码序列翻译成叶子节点的字符序列，并输出。其中，形参root为最优二叉树的根节点下标；形参buff指向前缀编码序列。
【函数4.1】
char **HC;
void LeafCode(int root, int n)
{ /*为最优二叉树中的n个叶子节点构造前缀编码，root是树的根节点下标*/
int I,p=root,cdlen=0;
char code[20];
Hc = (char **)malloc((n+1)*sizeof(char *)); /*申请字符指针数组*/
For(i = 1;i＜= p;++I)
Ht [i]. weight = 0; /*遍历最优二叉树时用做被遍历节点的状态标志* /
While (p) { /*以非递归方法遍历最优二叉树，求树中每个叶子节点的编码*/
If(Ht[p].weight == 0) { /*向左*/
Ht[p].weight = 1;
If(Ht[p].lchild != 0) {
p = Ht[p].lchild;
code[cdlen++] = '0';
}
else if(Ht[p].rchild == 0) { /*若是叶子节点,则保存其前缀编码*/
Hc[p] = (char *)malloc((cdlen+1)*sizeof(char));
(1);
strcpy (Hc [p],code);
}
}
else if(Ht[p].weight == 1) { /*向右*/
Ht [p].weight = 2;
If(Ht[p].rchild != 0) {
p = Ht [p].rchild;
code[cdlen++] ='1';
}
}
else { /*Ht[p].weight == 2,回退/
Ht [p].weight = 0;
p =(2);
(3); /*退回父节点*/
}
} / *while .结束* /
}
【函数4.2】
void Decode(char *buff,int root)
{ int pre = root,p;
while(*buff != '\0') {
p = root;
&
正确答案：(1)code[cdlen]='\0'或code[cdlen]=0 (2)Ht[p].parent (3)—cdlen或其等价形式 (4)*buff='0'或其等价形式 (5)buff—或其等价形式
(1)code[cdlen]='\0'或code[cdlen]=0 (2)Ht[p].parent (3)—cdlen或其等价形式 (4)*buff='0'或其等价形式 (5)buff—或其等价形式 解析：这是一道要求读者在用哈夫曼算法构造的最优二叉树上进行编码和译码的程序设计题。本题的解答思路如下。
哈夫曼算法构造最优二叉树的过程如下。
1)根据给定的n个权值{W1,W2,W3,...Wn)构成n棵二叉树的集合F=(T1,T2,T3,...Tn)，其中每棵二叉树引中只有一个带权为Wi的根节点，其左、右子树均为空。
2)在F中选取两棵根节点权值最小的树作为左、右子树构造一棵新的二叉树，且设置新的二叉树的根节点的权值为其左、右子树根节点的权值之和。
3)在F中删除这两棵二叉树，同时将新得到的二叉树加入F中。
4)重复步骤2)和3)，直到F只含一棵树为止。这棵树便是最优二叉树。
综上所述，最优二叉树是从叶子到根构造起来的，每次都是先确定一棵二叉树的左、右子树，然后再构造出树根节点，因此最优二叉树中只有叶子节点和分支数为2的内部节点。若已知叶子的数目为n，则内部节点数比叶子少1，因此整棵树所需的存储空间规模是确定的，可以采用数组空间来存储最优二叉树。
例如，给定字符集合{a,b,c,d)及其权值2、7、4、5，构造最优二叉树的过程如图6-19所示。
由于算法中对构成左、右子树的二叉树不进行限定，因此用哈夫曼算法构造出的最优二叉树的形态不是唯一的。另外，题干中已给出了存放最优二叉树的结构数组Ht的类型定义，以及存储图6-19所构造出的最优二叉树的结构数组Ht(见表6-14)。
由于二叉树中的节点最多只有两个分支，若用“0”和“1”分别标识最优二叉树中的左子树分支和右子树分支，那么从根节点开始到叶子节点为止，按经过分支的次序将相应标识依次排列，可得到由“0”和“1”组成的一个序列，称此序列为该叶子节点的前缀编码。例如，如图6-15所示的最优二叉树叶子节点a、b、c、d的前缀编码分别是110、0、111、10。
当最优二叉树的构造完成后，每个节点的weight域就可挪做他用，在构造哈夫曼编码的过程中，weight域用做被遍历节点的遍历状态标志。从树根出发，以非递归方式遍历最优二叉树的方法是：先沿着树根的左分支向叶子方向搜索，并用code[]记下所经过的分支的标识，同时用cdlen记录节点的路径长度，一直到叶子节点为止，即可得到当前正在访问的叶子的编码。然后，从该叶子节点回退到其父节点F。若刚才是从F的左子树回到F，则下一次应进入F的右子树进行遍历；若是从F的右子树回到F节点，则下一步应继续向F的父节点回退。
由以上分析可知，对于节点F，遍历过程中最多可能以3种不同的情况经过该节点，因此要为F节点的weight域赋予不同的值进行标识。初始时weight=0，当沿遍历路径到达该节点时其weight域值等于0，则进入其左子树分支进行遍历，并将weight置为1：若沿遍历路径到达该节点时其weight域值等于1，则说明刚从其左子树返回，下面应进入其右子树进行遍历并将weight置为2；若沿遍历路径到达该节点时其 weight域值等于2，则说明刚从其右子树返回，下面应继续向该节点的父节点回退，并将weight置为0。遍历路线如图6-20中箭头方向所示。
函数void LeafCode(int root,int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子节点，为所有的叶子节点构造前缀编码。由于在该函数(1)空缺处之后的语句“strcpy(Hc[p1,code);”，是进行字符串的复制运算，则需要对源串中的串结束标志进行设置，因此(1)空缺处所填写的语句是“code[cdlen]='\0'”或“code[cdlen]=0”。
(2)空缺处是从右子树向父节点回退的处理，因此该空缺处所填入的内容是“Ht[p].parent”。由于每向上层回退一次，节点的路径长度就会减1，因此(3)空缺处所填写的语句是“—cdlen”或其等价形式。
函数void Decode(char *buff,int root)的功能是：将前缀编码序列翻译成叶子节点的字符序列，并输出。译码的过程是：从根出发，若编码序列的当前字符是“0”，则进入左子树分支，否则进入右子树分支，直到到达一个叶子节点时为止，此时叶子所表示的字符就是翻译出的字符。若编码序列还没有结束，则重新从树根出发，重复上述过程，直到将编码序列结束。所以(4)空缺处所填写的语句是“*buff=='0'”或其等价形式。
由于到达一个叶子节点时，超前读入了一个编码序列中的字符，因此(5)空缺处所填写的语句是“buff—”或其等价形式。 -
第4题：
设计递归算法计算以二叉链表存储的二叉树的叶子结点数目。参考答案：
-
第5题：
若二叉树的前序遍历序列与中序遍历序列相同且树中节点数大于1，则该二叉树的______。
A．只有根节点无左予树
B．只有根节点无右子树
C．非叶子节点只有左子树
D．非叶子节点只有右子树
A．
B．
C．
D．
正确答案：D
-
第6题：
霍夫曼算法是求具有最【 】带权外部路径长度的扩充二叉树的算法。
正确答案：小
小 解析：霍夫曼算法是用来求具有最小带权外部路径长度的扩充二叉树的算法。 -
第7题：
一棵二叉树中共有70个叶子节点与与80个度为1的节点，则该二叉树中的总节点数为。 A．219 B．221 C．229 D．231
正确答案：A
-
第8题：
下面关于数据结构的叙述中，正确的叙述是 ______。
A．顺序存储方式的优点是存储密度大，且插入、删除运算效率高
B．链表中的每一个节点都恰好包含一个指针
C．包含n个节点的二叉排序树的最大检索长度为log2n
D．将一棵树转换为二叉树后，根节点没有右子树
正确答案：D
-
第9题：
某二叉树如图所示，若进行顺序存储（即用一维数组元素存储该二叉树中的节点且通过下标反映节点间的关系，例如，对于下标为i的节点，其左孩子的下标为2i、右孩子的下标为2i+1），则该数组的大小至少为 （请作答此空） ；若采用三叉链表存储该二叉树（各个节点包括节点的数据、父节点指针、左孩子指针、右孩子指针），则该链表的所有节点中空指针的数目为 （ ） 。
A.6
B.10
C.12
D.15答案：D解析：采用顺序存储结构存储二叉树时，一般的二叉树也必须按照完全二叉树的形式存储，需要填上一些不存在的"虚节点"。题中二叉树的高度为4，需要的存储空间为24-1=15，如下：
可见，空指针的数目为8。 -
第10题：
二叉树是有()基本单元构成。A.右子树
B.叶子节点
C.左子树
D.根节点答案：A,C,D解析：二叉树由左子树、右子树和根节点构成。 -
第11题：
以下说法正确的是()。A.树的节点包含一个数据元素及若干指向其子树的分支
B.二叉树只能进行链式存储
C.二叉树的子树无左右之分
D.二叉树的特点是每个节点至多只有两棵子树答案：A,D解析：二叉树可以使用顺序存储也可以使用链式存储， -
第12题：
填空题霍夫曼算法是求具有最（）带权外部路径长度的扩充二叉树的算法。正确答案： 小解析： 暂无解析 -
第13题：
输出二叉树中从每个叶子结点到根结点的路径。参考答案：采用先序遍历的递归方法，当找到叶子结点*b时，由于*b叶子结点尚未添加到path中，因此在输出路径时还需输出b->data值。
[算法描述]
void AllPath(BTNode *b,ElemType path[],int pathlen)
{int i;
if (b!=NULL)
{if (b->lchild==NULL && b->rchild==NULL) //*b为叶子结点
{cout << " " << b->data << "到根结点路径:" << b->data;
for (i=pathlen-1;i>=0;i--)
cout << endl;
}
else
{path[pathlen]=b->data; //将当前结点放入路径中
pathlen++; //路径长度增1
AllPath(b->lchild,path,pathlen); //递归扫描左子树
AllPath(b->rchild,path,pathlen); //递归扫描右子树
pathlen--; //恢复环境
}
}// if (b!=NULL)
}//算法结束
-
第14题：
如果将该二叉树存储为对称序线索二叉树，则节点H的左线索指向______。
A．节点A
B．节点C
C．节点E
D．节点G
正确答案：B
-
第15题：
在完全二叉树的顺序存储中，若节点{有左子女，则其左子女是节点【 】。
正确答案：2i
2i 解析：对一棵有n个节点的完全二叉树中节点i(2i≤n)的左子女节点是2i。 -
第16题：
在二叉树的顺序存储中，每个节点的存储位置与其父节点、左右子树节点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个节点，采用三叉链表存储时，每个节点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个节点下标为k(起始下标为1)，那么采用顺序存储更节省空间的条件是(59)。
A．
B．
C．
D．
正确答案：A
解析：采用三叉链表存储二叉树时，每个节点需要占用d+4×3个字节，n个节点则需要n(d+12)。若顺序存储最后一个节点下标为k，则共需kd个字节，那么采用顺序存储更节省空间的条件是kdn(d+12)，即
。
-
第17题：
设一棵完全二叉树共有700个节点，则在该二叉树中有______个叶子节点。
正确答案：350
350 解析：完全二叉树中，设高度为n，则除h层外其他层节点数都到达最大，可以算出h=10,1～9层节点个数为 2^9-1=511，最后一层节点个数为700-511=189个，189/2=95，除最后一层外共有节点2^(9-1)-95=161个，所以所有的节点个数为=189+161=350个。 -
第18题：
某二叉树有5个度为2的节点，则该二叉树中的叶子节点数是
A．10
B．8
C．6
D．4
正确答案：C
解析：对于任何一棵二叉树T，如果其终端节点(叶子)数为n1，度为2的节点数为n2，则n1=n2+1。所以该二叉树的叶子节点数等于5+1=6。 -
第19题：
某二叉树中有n个度为2的节点，则该二叉树中的叶子节点为( )。
A．n+1
B．n-1
C．2n
D．n/2
正确答案：A
解析：对任何一棵二叉树T，如果其叶子节点数为n0，度为2的节点数为n2，则n0=n2+1，即叶子节点数总是比度为2的节点数多1。 -
第20题：
设只包含根节点的二叉树的高度为0，则高度为A的二叉树的最小节点数为______。
正确答案：k+1
k+1 解析：若要使高度为k的二叉树的节点数最少，则此二叉树除叶节点外都只有一个分支节点。此二叉树的节点数为k+1。 -
第21题：
前序遍历和中序遍历结果相同的二叉树是()。A.所有节点只有左子树的二叉树
B.所有节点只有右子树的二叉树
C.根节点无左孩子的二叉树
D.根节点无右孩子的二叉树答案：B解析：前序遍历是首先访问根节点，然后前序遍历左子树，最后前序遍历右子树。中序遍历是首先中序遍历左子树，然后访问根节点，最后中序遍历右子树。当所有节点都没有左子树时，前序遍历和中序遍历的遍历结果相同。 -
第22题：
完全二叉树()。A.某些节点有右子树则必有左子树
B.不一定适合顺序结构存储
C.叶子节点可在任一层出现
D.适合于顺序结构存储答案：A,D解析：完全二叉树除了最下面一层，其余层的节点都是满的。 -
第23题：
具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n）其中带权路径最小的二叉树被称为（）。
正确答案:哈夫曼树（最优二叉树） -
第24题：
填空题具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n）其中带权路径最小的二叉树被称为（）。正确答案： 哈夫曼树（最优二叉树）解析： 暂无解析