2.createdectree ( decnode x &b,ongn)建立判定树b;
时间: 2024-02-27 22:52:00 浏览: 54
函数createdectree(decnode x, int n)可以用于创建一个包含n个元素的折半查找判定树。具体实现步骤如下:
1. 定义一个结构体类型decnode,用于表示判定树的节点。该结构体包含了该节点代表的子问题的左右边界,以及指向左右子树的指针。结构体定义如下:
```c
typedef struct decnode {
int left; // 左边界
int right; // 右边界
decnode* leftChild; // 左子树
decnode* rightChild; // 右子树
} decnode;
```
2. 编写递归函数createdectree(decnode x, int n),该函数接收一个decnode类型的参数x和一个整数n,用于创建包含n个元素的折半查找判定树。具体实现步骤如下:
- 如果n等于0,则返回空指针。
- 否则,创建一个新的decnode节点,并将该节点的左右边界设置为x结构体的左右边界。然后,计算出该节点代表的子问题的中间位置mid,并将该位置的元素作为该节点的值。
- 递归调用createdectree()函数,将x结构体的左边界和mid-1作为参数,生成该节点的左子树。
- 递归调用createdectree()函数,将mid+1和x结构体的右边界作为参数,生成该节点的右子树。
- 返回该节点的指针。
具体代码实现如下:
```c
decnode* createdectree(decnode x, int n) {
if (n == 0) {
return NULL;
}
decnode* node = new decnode;
node->left = x.left;
node->right = x.right;
int mid = (x.left + x.right) / 2;
node->value = arr[mid];
node->leftChild = createdectree(x, mid - x.left);
node->rightChild = createdectree(decnode{mid + 1, x.right}, x.right - mid - 1);
return node;
}
```
在上述代码中,我们假设arr是一个全局定义的有序数组,它包含了要进行查找的元素集合。x是一个decnode类型的参数,表示该节点代表的子问题的左右边界。n是要创建的子树中元素个数。
在实际使用时,我们可以调用createdectree()函数来创建折半查找判定树,如下所示:
```c
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
int n = sizeof(arr) / sizeof(int);
decnode root = {0, n - 1, NULL, NULL};
decnode* tree = createdectree(root, n);
```
在上述代码中,我们首先定义了一个长度为11的有序数组arr,然后定义一个decnode类型的结构体root,表示整个数组的左右边界。最后,我们调用createdectree()函数生成折半查找判定树,并将其存储在指针tree中。