假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法,求二叉树b的宽度(二叉树b的宽度是指其中所有层的节点个数的最大值)。

假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法,求二叉树b的宽度(二叉树b的宽度是指其中所有层的节点个数的最大值)。


参考答案和解析
intlog2(int x) // 求以2为底的x的对数 { int i=0; while (x!=1) { i++; x=x/2; } return i; } intLevel(SqBTree t ,int n,int i) //输出编号为i的节点的层次 { if (i<1 || i>n) return 0; else return log2(i)+1; }

相关考题:

采用邻接表存储的图的宽度优先遍历算法类似于二叉树的()。 A、先序遍历B、中序遍历C、后序遍历D、按层遍历

设二叉树根节点的层次为0,一棵高度为h的满二叉树的节点个数是【 】。

在下列关于二叉树的叙述,选出正确的一项A.在二叉树中,任何一个节点的度都是2B.二叉树的度为2C.在二叉树中至少有一个节点的度是2D.一棵二叉树的度可以小于2

下面关于二叉树的叙述,正确的是( )。A.完全二叉树的高度h与其结点数n之间存在确定的关系B.在二叉树的顺序存储和链式存储结构中,完全二叉树更适合采用链式存储结构C.完全二叉树中一定不存在度为1的结点D.完全二叉树中必定有偶数个叶子结点

假设一棵平衡二叉树的每个结点都表明了平衡因子b,试设计一个算法,求平衡二叉树的高度。

计算二叉树最大的宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。

某二叉树中度为2的节点有n个,则该二叉树中有______个叶子节点。

设只包含根节点的二叉树的高度为0,则高度为A的二叉树的剔、节点数为【 】。

如果将该二叉树存储为对称序线索二叉树,则节点H的左线索指向______。A.节点AB.节点CC.节点ED.节点G

阅读以下函数说明和C代码,将C程序中(1)~(5)空缺处的内容补充完整。【说明】对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d}及其权值2、7、4、5,可构造如图6-15所示的最优二叉树,以及相应的结构数组Ht(如表6-14所示,其中数组元素Ht[0]不用)。结构数组Ht的类型定义如下:define MAXLEAFNUM 20struct 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;&

二叉树的基本操作主要有() A、遍历B、求二叉树的深度C、求某个节点的左子女D、求某个节点的左子女

在完全二叉树的顺序存储中,若节点{有左子女,则其左子女是节点【 】。

编写递归算法,求以二叉链表存储的二叉树的深度。

编写递归算法,交换二叉链表存储的二叉树中每个结点的左、右子树。

在二叉树的顺序存储中,每个节点的存储位置与其父节点、左右子树节点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个节点,采用三叉链表存储时,每个节点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,则最后一个节点下标为k(起始下标为1),那么采用顺序存储更节省空间的条件是(59)。A.B.C.D.

实现任意二叉树的后序遍历的非递归算法用栈结构,最佳方案是二叉树采用______存储结构。A.二叉链表B.顺序存储结构C.三又链表D.广义表存储结构

某二叉树共有730个节点,其中度为1的节点有30个,则叶子节点个数为( )。 A.不存在这样的二叉树B.351C.1D.350

在深度为7的满二叉树中,度为2的节点个数为( )。

在对二叉树进行顺序存储时,若它的下标为5的节点既有双亲节点,又有左子女节点和右子女节点,它的双亲节点的下标为【 】。

具有n个结点的二叉树,采用二叉链表存储,共有______个空链域。A.n-1B.nC.n+1D.由于二叉树形态不定导致空链域个数不定

有关二叉树的下列说法正确的是 ______。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中任何一个节点的度都为2D.任何一棵二叉树中至少有一个节点的度为2

以下有关数据结构的叙述,正确的是______。A.线性表的线性存储结构优于链式存储结构B.二叉树的第i层上有2i-1个节点,深度为k的二叉树上有2k-1个节点C.二维数组是其数据元素为线性表的线性表D.栈的操作方式是先进先出

某二叉树如图所示,若进行顺序存储(即用一维数组元素存储该二叉树中的节点且通过下标反映节点间的关系,例如,对于下标为i的节点,其左孩子的下标为2i、右孩子的下标为2i+1),则该数组的大小至少为 (请作答此空) ;若采用三叉链表存储该二叉树(各个节点包括节点的数据、父节点指针、左孩子指针、右孩子指针),则该链表的所有节点中空指针的数目为 ( ) 。A.6B.10C.12D.15

前序遍历和中序遍历结果相同的二叉树是()。A.所有节点只有左子树的二叉树B.所有节点只有右子树的二叉树C.根节点无左孩子的二叉树D.根节点无右孩子的二叉树

以下说法正确的是()。A.树的节点包含一个数据元素及若干指向其子树的分支B.二叉树只能进行链式存储C.二叉树的子树无左右之分D.二叉树的特点是每个节点至多只有两棵子树

以下关于二叉树说法正确的是()。A、二叉树的特点是每个结点至多只有两棵子树。B、二叉树的子树无左右之分。C、二叉树只能进行链式存储。D、树的结点包含一个数据元素及若干指向其子树的分支。

完全二叉树的存储结构通常采用顺序存储结构。

二叉树的所有结点的层次的最大值是()。A、二叉树的高度B、二叉树的深度C、二叉树的度D、结点的度