数据结构考研分类复习真题 第六章 树和二叉树 (三)[11]

数据结构考研分类复习真题 第六章 树和二叉树 (三)[11]  

　　 ．二叉树以链方式存储 有三个域 数据域data 左右孩子域lchild rchild 树根由tree指向 现要求按层次从上到下 同层次从左到右遍历树 下面算法中用到addx(p) 将指针p进队 delx( )将队头元素返回并退队 notempty在队不空时返回true 否则为false 将算法补充完整:

　　PROC  processnode(p);　　IF( )_______THEN [write(p＾ data); ( )_______ ]　　ENDP;　　PROC   trave(tree);　　write(tree＾ data); ( )_______;　　WHILE  notempty()  DO　　[ r:=delx( ); processnode(r＾ lchild); processnode(( )_______)]　　ENDP;【南京理工大学 三 ( 分)】

　　 阅读下列程序说明和程序 填充程序中的______

　　【程序说明】本程序完成将二叉树中左 右孩子交换的操作 交换的结果如下所示(编者略)

　　本程序采用非递归的方法 设立一个堆栈stack存放还没有转换过的结点 它的栈顶指针为tp 交换左 右子树的算法为

　　( )把根结点放入堆栈

　　( )当堆栈不空时 取出栈顶元素 交换它的左 右子树 并把它的左 右子树分别入栈

　　( )重复( )直到堆栈为空时为止

　　typedef  struct  node  *tree;　　struct node{int data; tree lchild rchild;}　　exchange(tree t)　　{tree  r p; tree  stack [ ]; int  tp= ;　　( )_______　　while (tp>= )　　{( )_______　　if(( )_______)　　{r=p >lchild; p >lchild=p >rchild; p >rchild=r　　stack[( )_______]=p >lchild; stack[++tp]=p >rchild;　　}　　}　　} 【中科院自动化研究所 二 ( 分)】