假设非空二叉树采用顺序存储结构，每个节点值为单个字符。设计一个算法输出编号为i的节点的所有祖先节点值。
假设非空二叉树采用顺序存储结构，每个节点值为单个字符。设计一个算法输出编号为i的节点的所有祖先节点值。
参考答案和解析
A
相关考题：
如果一棵二叉树中任一节点的值都大于其左子树中所有节点的值，且小于其右子树中所有节点的值，现欲得到各节点值的递增序列，试问应采用的遍历的方法是( )。A．先序遍历B．中序遍历C．后序遍历D．层次遍历
有n个节点的顺序表中,算法的时间复杂度是O(1)的操作是() A、访问第i个节点(1≤i≤n)B、在第i个节点后插入一个新节点(1≤i≤n)C、删除第i个节点(1≤i≤n)D、将n个节点从小到大排序
某二叉树T有n个节点，设按某种顺序对T中的每个节点进行编号，编号值为1，2，… n，且有如下性质：T中任一节点v，其编号等于左子树上的最小编号减1，而v的右子树的节点中，其最小编号等于v左子树上的节点的最大编号加1。此二叉树是按( )顺序编号的。A．前序遍历B．中序遍历C．后序遍历D．按层次遍历
阅读以下函数说明和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;&
在包含1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最短?A．线性表按顺序方式存储，查找关键码值为666的节点B．线性表按链接方式存储，查找关键码值为666的节点C．线性表按顺序方式存储，查找线性表中第900个节点D．线性表按链接方式存储，查找线性表中第900个节点
在二叉树的顺序存储中，每个节点的存储位置与其父节点、左右子树节点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个节点，采用三叉链表存储时，每个节点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个节点下标为k(起始下标为1)，那么采用顺序存储更节省空间的条件是(59)。A．B．C．D．
二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：特其左子树非空，则左子树上所有节点的值均小于根节点的值；若其右子树非空，则右子树上所有节点的值均大于根节点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行______遍历，可得到一个节点元素的递增序列。A．前序(根、左、右)B．中序(左、根、右)C．后序(左、右、根)D．层序(从树根开始，按层次)A．B．C．D．
阅读以下说明和C语言函数，应填入(n)处。【说明】在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树型结构，如图10-9所示。信号源是树根，树中的每个节点(除了根)表示一个可以放置放大器的子节点，其中某些节点同时也是信号消耗点，信号从一个节点流向其子节点。每个节点有一个d值，表示从其父节点到该节点的信号衰减量。例如，在图10-9中，节点w、p、q的d值分别为2、1、3，树根节点表示信号源，其d值为0。每个节点有一个M值，表示从该节点出发到其所有叶子的信号衰减量的最大值。显然，叶子节点的M值为0。对于非叶子节点j，M(j)=max{M(k)+d(k)|k是j的孩子节点}。在此公式中，要计算节点的M值，必须先算出其所有子节点的M值。在计算M值的过程中，对于某个节点i，其有一个子节点k满足d(k)+M(k)大于容忍值，则应在k处放置放大器，否则，从节点i到某叶子节点的信号衰减量会超过容忍值，使得到达该叶子节点时信号不可用，而在节点i处放置放大器并不能解决到达叶子节点的信号衰减问题。例如，在图10-9中，从节点p到其所有叶子节点的最大衰减值为4。若容忍值为3，则必须在s处放置信号放大器，这样可使得节点p的M值为2。同样，需要在节点小v处放置信号放大器，如图10—10阴影节点所示。若在某节点放置了信号放大器，则从该节点输出的信号与信号源输出的信号等价。函数placeBoosters(TreeNode*root)的功能是：对于给定树型分布网络中各个节点，计算其信号衰减量的最大值，并确定应在树中的哪些节点放置信号放大器。全局变量Tolerance保存信号衰减容忍值。树的节点类型定义如下：typedef struct TreeNode{int id； /*当前节点的识别号*/int ChildNum； /*当前节点的子节点数目*/int d; /*父节点到当前节点的信号衰减值*/struct TreeNode **childptr； /*向量，存放当前节点到其所有子节点的指针*/int M； /*当前节点到其所有子节点的信号衰减值中的最大值*/bool boost； /*是否在当前节点放置信号放大器的标志*/}TreeNode；【C语言函数】void placeBoosters(TreeNode *root){ /* 计算root所指节点处的衰减量，如果衰减量超出了容忍值，则放置放大器*/TreeNode *p；int i，degradation；if( (1) ){degradation = 0；root-＞M = 0；i=0；if (i＞=root-＞ChildNum)return；p=(2)；for(;i＜root-＞ChildNum p； i++，p =(3)){p-＞M = 0；(4)；if (p-＞d+p-＞M＞Tolerance) { /*在p所指节点中放置信号放大器*/p-＞boost=true；p-＞M = 0；}if (p-＞d + p-＞M ＞ degradation)degradation = p-＞d + p-＞M；}root-＞M =(5)；}}
某二叉树如图所示，若进行顺序存储（即用一维数组元素存储该二叉树中的节点且通过下标反映节点间的关系，例如，对于下标为i的节点，其左孩子的下标为2i、右孩子的下标为2i+1），则该数组的大小至少为 （请作答此空） ；若采用三叉链表存储该二叉树（各个节点包括节点的数据、父节点指针、左孩子指针、右孩子指针），则该链表的所有节点中空指针的数目为 （ ） 。A.6B.10C.12D.15
多选题线性四叉树在存储是每个节点存储（）。A莫顿码B深度C节点值D节点大小