已经有定义typedef struct node{ ElemType data; struct nodelchild; struct node rchild;}binode;帮我建立由有序序列进行二分查找产生的判定树,不要用递归
时间: 2023-07-30 17:10:19 浏览: 38
好的,根据您提供的定义,以下是由有序序列进行二分查找产生的判定树的建立过程:
1. 确定根节点:将有序序列的中间元素作为根节点。
2. 确定分支条件:对于每个节点,将序列分成两个部分,左侧是小于中间元素的部分,右侧是大于中间元素的部分。
3. 确定叶节点:当无法再分割时,将节点设为叶节点,并给出最终的判断结果。
4. 确定分支顺序:按照左子树、右子树的顺序进行分支。
5. 验证判断树:验证判断树是否正确,可以通过实际数据进行验证。
以下是由有序序列进行二分查找产生的判定树的建立示例代码:
```c
binode* create_tree(ElemType* arr, int len) {
if (len == 0) {
return NULL;
}
binode* root = (binode*)malloc(sizeof(binode));
int left = 0, right = len - 1;
root->data = arr[(left + right) / 2];
root->lchild = NULL;
root->rchild = NULL;
binode* p = root;
int stack[len], top = -1;
stack[++top] = left;
stack[++top] = right;
while (top >= 0) {
right = stack[top--];
left = stack[top--];
int mid = (left + right) / 2;
p = (binode*)malloc(sizeof(binode));
p->data = arr[mid];
p->lchild = NULL;
p->rchild = NULL;
if (left <= mid - 1) {
stack[++top] = left;
stack[++top] = mid - 1;
root->lchild = p;
root = root->lchild;
}
if (right >= mid + 1) {
stack[++top] = mid + 1;
stack[++top] = right;
root->rchild = p;
root = root->rchild;
}
}
return p;
}
```
调用该函数,可以将有序序列转化为判定树:
```c
ElemType arr[] = {1, 2, 3, 4, 5, 6, 7};
int len = sizeof(arr) / sizeof(ElemType);
binode* root = create_tree(arr, len);
```
这样,我们就成功地将有序序列转化为了判定树。对于任意一个元素,都可以通过判定树进行二分查找。