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

．二叉树以链方式存储有三个域数据域data左右孩子域lchildrchild树根由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 lchildrchild;}

exchange(tree t)

{tree rp; tree stack []; int tp=;

()_______

while (tp>=)

{()_______

if(()_______)

{r=p>lchild; p>lchild=p>rchild; p>rchild=r

stack[()_______]=p>lchild; stack[++tp]=p>rchild;

}

}

} 【中科院自动化研究所 二 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []