試題二

　　閱讀下列說明和流程圖，將應填入(n)的語句寫在答題紙的對應欄內。

　　【流程圖說明】

　　下面的流程(如圖1所示)用N-S盒圖形式描述了在一棵二叉樹排序中查找元素的過程，節點有3個成員：data，left和right。其查找的方法是：首先與樹的根節點的元素值進行比較：若相等則找到，返回此結點的地址;若要查找的元素小于根節點的元素值，則指針指向此結點的左子樹，繼續查找;若要查找的元素大于根節點的元素值，則指針指向此結點的右子樹，繼續查找。直到指針為空，表示此樹中不存在所要查找的元素。

　　【算法說明】

　　【流程圖】

　　將上題的排序二叉樹中查找元素的過程用遞歸的方法實現。其中NODE是自定義類型：

　　typedef struct node{

　　int data;

　　struct node*left;

　　struct node*right;

　　}NODE;

　　【算法】

　　NODE*SearchSortTree(NODE*tree，int e)

　　{

　　if(tree!=NULL)

　　{

　　if(tree->data　　(4) ;∥小于查找左子樹

　　else if(tree->data　　(5) ;∥大于查找左子樹

　　else return tree;

　　}

　　return tree;

　　}

　　【答案】

　　(1)p=p->left

　　(2)p=p->right

　　(3)return P

　　(4)return SearchSortTree(tree->left)

　　(5)return SearchSortTree(tree->right)