假设二叉树采用链接存储结构进行存储，t指向根结点，p所指结点和q所指结点为二叉树中的两个结点，编

高树，画出构造过程和进行平衡转换的类型。 (2)若均高树中有n个结点，其高度为h，指出在最坏情况下，对该树的插入、删除和依次输出操作的时间复杂性。

? (3)二叉树的深度为多少?

data： //数据域 struct node*left； //左孩子 struct node * right； //右孩子 } 请在(1)、(2)两题的_________处进行填空，完成题目要求的功能。注意：每空只能填一个语句。 (1)求出以T为根的二叉树或子树的结点个数。 int size(struct node*T){ if( ① ) return 0； else ② } (2)求出以T为根的二叉树或子树的高度。注：高度定义为树的总层次数。 int height(struct node*T){ if(T==NULL) ③ else ④ //此空可填多条语句 }

空指针)。 typedef struct node{ struct node * firstchild．* nextbrother； }JD； int numberofleaf(JD * r){ int num； if(r==NULL) num=0； else if(r->firstchild==NULL){ num= (1) +numberofleaf(r->nextbrother)； } else{ (2) ； } return(num)； }

在完全二叉树中，若一个结点是叶结点，则它没有( )。

A．左子结点

B．右子结点

C．左子结点和右子结点

D．左子结点，右子结点和兄弟结点

③二叉树的左右子树可任意交换； ④深度为忌的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③

B．②③④

C．②④

D．①④

利用二叉链表存储树，则根结点的右指针是( )。

A．指向最左孩子

B．指向最右孩子

C．空

D．非空

)。

A．在树T中，X是其双亲的第一个孩子

B．在树T中，X一定无右兄弟

C．在树T中，X是一定是叶结点

D．在树T中，X一定有左兄弟