若某二叉树中的所有结点值均大于其左子树上的所有结点值，且小于右子树上的所有结点值，则该二叉树若某二叉树中的所有结点值均大于其左子树上的所有结点值，且小于右子树上的所有结点值，则该二叉树遍历序列中有序的是（）

若某二叉树中的所有结点值均大于其左子树上的所有结点值，且小于右子树上的所有结点值，则该二叉树遍历序列中有序的是（ ）。

A.前序序列

B.中序序列

C.后序序列

D.以上说法均可以

某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1,2…,n，且有如下性质：T中任一结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于v左子树上的结点的最大编号加1。此二叉树是按( )顺序编号的。

A．前序遍历

B．中序遍历

C．后序遍历

D．按层次遍历

某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1，2，…，n，且有如下性质：T中任一结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于 v左子树上的结点的最大编号加1。此二叉树是按( )顺序编号的。

A．前序遍历

B．中序遍历

C．后序遍历

D．按层次遍历

某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1、2、…、n，且有如下性质：T中任一结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于 v左子树上的最大编号加1。此二叉树是按( )顺序编号的。

A．前序遍历

B．中序遍历

C．后序遍历

D．按层次遍历

某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1、2、…、n，且有如下性质：T中任一结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于 v左子树上的最大编号加1。此二叉树是按( )顺序编号的。

A．前序遍历

B．中序遍历

C．后序遍历

D．按层次遍历

阅读以下说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

一棵非空二叉树中“最左下”结点定义为：若树根的左子树为空，则树根为“最左下”结点；否则，从树根的左子树根出发，沿结点的左

子树分支向下查找，直到某个结点不存在左子树时为止，该结点即为此二叉树的“最左下”结点。例如，下图所示的以 A为根的二叉树的“最

左下”结点为D，以C为根的子二叉树中的“最左下”结点为C。

二叉树的结点类型定义如下：

typedef stmct BSTNode{

int data；

struct BSTNode*lch,*rch；//结点的左、右子树指针

}*BSTree；

函数BSTree Find Del(BSTree root)的功能是：若root指向一棵二叉树的根结点，则找出该结点的右子树上的“最左下”结点*p，并从

树于删除以*p为根的子树，函数返回被删除子树的根结点指针；若该树根的右子树上不存在“最左下”结点，则返回空指针。

【函数】

BSTrce Find_Del(BSTreeroot)

{ BSTreep,pre；

if ( !root ) return NULL； /*root指向的二叉树为空树*/

(1)； /*令p指向根结点的右子树*/

if ( !p ) return NULL；

(2)； /*设置pre的初值*/

while(p-＞lch){ /*查找“最左下”结点*/

pre=p；p=(3)；

}

if ((4)==root) /*root的右子树根为“最左下”结点*/

pre-＞rch=NULL；

else

(5)=NULL； /*删除以“最左下”结点为根的子树*/

reurn p；

}

阅读下列程序说明和C程序，把应填入其中(n)处的字句，写在对应栏内。

【程序说明】

已知某二叉树的前序遍历和中序遍历序列，可以得到该二叉树的结构。本程序实现了根据这两个遍历序列生成一棵链接表示的二叉树。

构造二叉树的算法要点是：由前序遍历序列，该序列的第一个元素是根结点元素。该元素将中序遍历序列分成左、右两部分，那些位于该元素之前的元素是它的左子树上的元素，位于该元素之后的元素是它的右子树上的元素。对于左、右子树，由它们的前序遍历序列的第一个元素可确定左、右子树的根结点，参照中序遍历序列又可进一步确定子树的左、右子树元素。如此递归地参照两个遍历序列，最终构造出二叉树。

两个遍历序列作为主函数main()的参数。为简单起见，程序假定两个遍历序列是相容的。主函数调用函数restore()建立二叉树。函数restore()以树(子树)的前序遍历和中序遍历两序列及序列长为参数，采用递归方法建立树(子树)。函数postorder()实现二叉树的后序遍历序列输出，用来验证函数restore()建立的二叉树。

【程序】

include(stdio．h＞

include＜stdlib．h＞

define MAX 100

typedef struct node{

char data；

struet node * llink，*rlink；

}TNODE；

charpred[MAX]，inod[MAX]；

TNODE * restore (Char*，char*，int)；

main(int argc，Char* *argv)

{

TNODE * root；

if(argc＜3)exit(0)；

strcpy(pred，argv[1])；

strcpy(inod，argv[2])；

root=restore(pred，inod，strlen(pred))postorder(root)；

printf("\n\n")；

}

TNODE * restore(Char * ppos，char * ipos，int n)

{ /*参数包括前序遍历序列数组和中序遍历数组*/

TNODE * ptr；

Char * rpos；

int k；

if(n ＜=0)return NULL；

ptr= (TNODE *)malloc(sizeof(TNODE))；

ptr→data=(1)；

for (2) rpos=ipos；rpos ＜ipos+n；rpos++ )

if(*rpos== * ppos)break；

k =(3)；

ptr→llink = restore(ppos+1， (4)，k)；

ptr→rlink = restore (5) + k，rpos + 1，n-1-k)；

return ptr；

}

postorder(TNODE *ptr)

{ if(ptr==NULL)return；

postorder(ptr→llink)；

postorder(ptr→rlink)；

prinft("%c"，ptr→data)；

}

考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上的一切结点的值。

现把9个数1,2,3,4…8,9填入图8-18所示的二叉树的9个结点中，并使之具有上述性质，此时N1的值是(1)，N2的值是(2)，N9的值是(3)。现欲把放入此树并使该树保持前述性质，增加的一个结点可以放在(4)。

A．1

B．2

C．3

D．4

E．7

二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值，且小于其右非空子树(若存在的话)所有结点的关键字值。（）

如果二叉树中任何一个结点的值都大于它的左子树上所有结点的值而小于右子树上所有结点的值,要得到各结点值的递增序列,应按下列哪种次序排列结点?

A．先根

B．中根

C．后根

D．层次