给出在中序线索二叉树中查找节点p的后继节点的过程。
给出在中序线索二叉树中查找节点p的后继节点的过程。
参考答案和解析
在中序线索二叉树中: 若 p - >rtag=1 ,则 p - >rchild 即为后继节点。 若 p - >rtag=0 , p 节点的右子树中中序遍历中的第一个节点即为 p 节点的后继节点。
相关考题：
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。【说明】函数DeleteNode(Bitree*r，inte)的功能是：在树根节点指针为r的二叉查找(排序)树上删除键值为e的节点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树节点的类型定义为：typedef struct Tnode{int data;/*节点的键值*/struct Tnode *Lchild,*Rchiid;/*指向左、右子树的指针*/}*Bitree;在二叉查找树上删除一个节点时，要考虑3种情况。①若待删除的节点p是叶子节点，则直接删除该节点。②若待删除的节点p只有一个子节点，则将这个子节点与待删除节点的父节点直接连接，然后删除节点。③若待删除的节点p有两个子节点，则在其左子树上，用中序遍历寻找关键值最大的节点 s，用节点s的值代替节点p的值，然后删除节点s，节点s必属于上述①、②情况之一。【函数5-5】int DeleteNode(Bitree *r,int e){Bitree p=*r,pp,s,c;while( (1) {/*从树根节点出发查找键值为e的节点*/pp=p;if(e＜p-＞data)p=p-＞Lchild;else p=p-＞Rehild;}if(!p)retrn -1;/*查找失败*/if(p-＞Lchild p-＞Rchild){/*处理情况③*/s=(2); pp=p;while( (3)){pp=s;s=s-＞Rchild;}p-＞data=s-＞data;p=s;}/* 处理情况①、②*/if((4))c=p-＞Lchild;else c=p-＞Rchild;if(p== *r)*r=c;else if((5))pp-＞Lchild=c;else pp-＞Rchild=c;free(p);return 0;}
如果一棵二叉树中任一节点的值都大于其左子树中所有节点的值，且小于其右子树中所有节点的值，现欲得到各节点值的递增序列，试问应采用的遍历的方法是( )。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;&
某二叉树的前序遍历节点访问顺序是abdgcefh，中序遍历的节点访问顺序是dgbaechf，则后序遍历的节点访问顺序是______。A．bdgcefhaB．gdbecfhaC．bdgaechfD．gdbehfca
若二叉树的前序遍历序列与中序遍历序列相同且树中节点数大于1，则该二叉树的______。A．只有根节点无左予树B．只有根节点无右子树C．非叶子节点只有左子树D．非叶子节点只有右子树A．B．C．D．
单链表的每个节点中包括一个指针link，它指向该节点的后继节点。现要将指针q指向的新节点插入到指针p指向的单链表节点之后，下面的操作序列中哪一个是正确的? ______。A．q：=p^.link；p^.link：=q^.link；B．p^.link：=q^.link；q：=p^.link；C．q^.link：=p^.link；p^link：=q；D．p^.link：=q；q^.link：=p^.link；
一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为(57)个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则(58)。A．m+2B．m+1C．mD．m-1
最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度∑wl最小的树，其中对于最优二叉树，n表示(31)；对于最优查找树，n表示(32)；构造这两种树均(33)。A．节点数B．叶节点数C．非叶节点数D．度为2的节点数
某二叉树的先序遍历节点访问顺序是ABCDEFG，中序遍历的节点访问顺序是 CBDAFGE，则其后序遍历的节点访问顺序是 ______。A．CDBGFEAB．CDGFEABC．CDBAGFED．CDBFAGE
某二叉树为单枝树(即非叶子节点只有一个孩子节点)且具有n个节点(n＞1)，则该二叉树______。A．共有n层，每层有一个节点B．共有log2n层，相邻两层的节点数正好相差一倍C．先序遍历序列与中序遍历序列相同D．后序遍历序列与中序遍历序列相同A．B．C．D．
若某二叉树的前序遍历节点访问顺序是abdgcefh：中序遍历的节点访问顺序是 dgbaechf，则其后序遍历的节点访问顺序是______。A．bdgcefhaB．gdbecfhaC．bdgechfaD．gdbehfca
找出所有满足下列条件的二叉树： （a）它们在先序遍历和中序遍历时，得到的节点访问序列相同； （b）它们在后序遍历和中序遍历时，得到的结点访问序列相同； （c）它们在先序遍历和后序遍历时，得到的节点访问序列相同。
问答题找出所有满足下列条件的二叉树： （a）它们在先序遍历和中序遍历时，得到的节点访问序列相同； （b）它们在后序遍历和中序遍历时，得到的结点访问序列相同； （c）它们在先序遍历和后序遍历时，得到的节点访问序列相同。
单选题某二叉树为单枝树（即非叶子节点只有一个孩子节点）且具有n个节点（n1）则该二叉树（）。A共有n层，每层有一个节点B共有log2n层，相邻两层的节点数正好相差一倍C先序遍历序列与中序遍历序列相同D后序遍历序列与中序遍历序列相同
判断题线索二叉树的优点是便于在中序下查找前趋结点和后继结点。A对B错