判断题(2023年暨南大学

在一棵二叉树中,中序遍历的第一个结点,是二叉树的最左下结点。

答案解析

讨论

已知一颗二叉树的先序序列和后序序列,一定能构造出该树。

由树转化为二叉树,该二叉树的右子树不一定为空。

设二叉树中度为0的结点数为30,度为1的结点数为20,则该二叉树中总共有_____个结点数。

在N个结点的线索二叉树中线索的数目为______.

阅读下面的程序代码,写出此函数的功能。void F(Bitree T,Stack &S){ if(T){ Push(S,T->data); if(!T->Lchild && !T->Rchild)PrintStack(S); else{ F(T->Lchild,S); F(T->Rchild,S); } Pop(S); }}

假设表中关键字序列为(41,36,58,12,79,25),将关键字依次插入一棵初始为空的二叉排序树,然后删除结点 41。(1) 画出二叉排序树的生成过程;(2)画出删除结点41后的二叉排序树。

假设二叉树采用二叉链表存储结构,试编写一个非递归算法,输出中序遍历序列中第k个结点的数据值。

阅读以下说明和C函数,填补代码中的空缺(1)~(6)。二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数 GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组 counter[], counter[i]存放第i层上的结点数,并按照层次顺序来遍历二又树中的结点,在此过程中可获得每个结点的层次值,最后从counter[]中取出最大的元素就是树的宽度。按照层次顺序遍历二叉树的实现方法是借助一个队列,按访问结点的先后顺序来记录结点,离根结点越近的结点越先进入队列,具体处理过程为:先令根结点及其层次号(为1)进入初始为空的队列,然后在队列非空的情况下,取出队头所指示的结点及其层次号,然后将该结点的左子树根结点及层次号入队列(若左子树存在),其次将该结点的右子树根结点及层次号入队列(若右子树存在),然后再取队头,重复该过程直至完成遍历。设二叉树采用二叉链表存储,结点类型定义如下:typedef struct BTNode{ TElemType data; struct BTNode *left, *right;}BTNode, *BiTree;队列元素的类型定义如下:typedef struct{ BTNode *ptr; int LevelNumber;}QElemType;Get Width()函数中用到的函数原型如下所述,队列的类型名为 QUEUE:InitQueue(QUEUE *Q):初始化一个空队列,成功时返回值为1,否则返回值0isEmpty(QUEUE Q):判断队列是否为空,是空则为1,否则为0EnQueue( QUEUE*Q, QElemType a):将元素a加入队列,成功返回值为1,否则返回值0DeQueue(QUEUE *Q, QElemType *):删除队头元素,并通过参数带回其值,成功则返回值1,否则返回值0GetHeight (BiTree root):返回值为二叉树的高度(即层次数,空二叉树的高度为0)int Getwidth(BiTree root){ QUEUE Q; QElemType a, b; int width,height= GetHeight(root); int i, *counter =(int *)calloc(height+1, sizeof (int)); if(__(1)__) return -1;/*申请空间失败*/ if(! root) return 0;/*空树的宽度为0*/ if(__(2)__) return -1;/*初始化队列失败时返回*/ a.ptr= root; a.LevelNumber=1; if(! EnQueue(&Q,a)) return -1;/*元素入队列操作失败时返回*/ while (! isEmpty(Q)){ if(__(3)__)return -1;/*出队列操作失败时返回*/ counter[b. LevelNumber]++;/*对层号为b. LevelNumber的结点计数*/ if(b.ptr->left){/*若左子树存在,则左子树根结点及其层次号入队*/ a.ptr= b.ptr->left; a.LevelNumber=__(4)__; if(!EnQueue(&Q,a)) return -1; } if(b.ptr-> right){/*若右子树存在,则右子树根结点及其层次号入队*/ a.ptr= b.ptr->right; a. LevelNumber=__(5)__; if(! EnQueue(&Q,a)) return -1; } } width= counter[1]; for(i=1; i< height +1; 1++)/*求 counter[]中的最大值*/ if(__(6)__)width= counter [i]; free(counter); return width;}

最优二叉树(或哈夫曼树)是指权值为w1,w2,…,wn的n个叶结点的二叉树中带权路径长度最小的二叉树。【 】是哈夫曼树(叶结点中的数字为其权值)。

与算术表达式3-(2+7)/4对应的二又树为【 】。

在一棵树中,堂兄弟的双亲是兄弟关系。

对二叉树中的结点如下编号:树根结点编号为1,根的左孩子结点编号为2、右孩子结点编号为3,以此类推,对于编号为i的结点,其左孩子编号为2i、右孩子编号为2i+1。例如,下图所示二又树中有6个结点,结点a、b、c、d、e、f的编号分别为1、2、3、5、7、11。那么,当结点数为n(n>0)的【 】时,其最后一个结点编号为2n-1。

某二叉树的先序遍历(根、左、右)序列为 EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG,则该二叉树根结点的左孩子结点和右孩子结点分别是【 】

有n个数顺序(依次)进栈,则出栈顺序有Cn种。Cn=×

某二叉树共有7个结点,其中叶子结点只有1个,则该二叉树的深度为(假设根结点在第1层)【 】

一棵二叉树有10个度为1的结点,7个度为2的结点,则该二叉树共有结点个数为【 】。

某二叉树有5个度为2的结点,则该二叉树中的叶子结点数是【 】。

对于前序遍历和中序遍历结果相同的二叉树为__________;对于前序遍历和后序遍历结果相同的二叉树是为__________。一般二叉树只有根结点的二叉树要结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子树的二叉树所有结点只有右子树的二叉树

由二叉树的前序和后序遍历序列【 】唯一地确定这棵二叉树。

具有7个结点的互不相识的二叉树共有__________棵。