编一个函数CreateBST(BiTree &T, const char *chars),要求根据给定的字符序列(字符不重复),生成一棵二叉树。在二叉树中,左子树所有结点的字符小于根结点的字符,右子树所有结点的字符大于根结点。左右子树也满足这个条件
时间: 2024-04-30 11:24:36 浏览: 116
创建二叉树
下面是一个用C++实现的CreateBST函数的示例代码:
```c++
typedef struct BiTreeNode {
char data;
BiTreeNode* left;
BiTreeNode* right;
} BiTreeNode, *BiTree;
void CreateBST(BiTree &T, const char *chars) {
T = NULL;
const char* p = chars;
while (*p != '\0') {
if (T == NULL) {
T = new BiTreeNode;
T->data = *p;
T->left = T->right = NULL;
} else {
BiTreeNode* node = T;
while (node != NULL) {
if (*p < node->data) {
if (node->left == NULL) {
node->left = new BiTreeNode;
node->left->data = *p;
node->left->left = node->left->right = NULL;
break;
} else {
node = node->left;
}
} else {
if (node->right == NULL) {
node->right = new BiTreeNode;
node->right->data = *p;
node->right->left = node->right->right = NULL;
break;
} else {
node = node->right;
}
}
}
}
p++;
}
}
```
该函数使用了循环和指针操作来构建二叉搜索树。在循环中,首先判断树是否为空,如果为空,则创建根节点。如果树不为空,则从根节点开始寻找插入位置。如果插入的字符比当前节点的字符小,则进入当前节点的左子树进行寻找;如果插入的字符比当前节点的字符大,则进入当前节点的右子树进行寻找。如果找到了合适的插入位置,则创建新的节点并插入到树中。最后,返回构建好的二叉搜索树。
阅读全文