如何构建二叉排序树?
时间: 2024-06-18 20:04:00 浏览: 44
构建二叉排序树的基本思路是:首先将第一个节点作为根节点,然后依次插入其他节点,每个节点的插入都要从根节点开始,与当前节点进行比较,若小于当前节点则将其作为当前节点的左子节点,若大于当前节点则将其作为当前节点的右子节点。插入完成后,二叉排序树的特点是,对于任何一个节点,它的左子树的所有节点的值都小于它自身的值,而它的右子树的所有节点的值都大于它自身的值。
具体步骤如下:
1. 将第一个节点作为根节点。
2. 依次插入其他节点,每个节点的插入都要从根节点开始,与当前节点进行比较。
3. 若小于当前节点,则将其作为当前节点的左子节点;若大于当前节点,则将其作为当前节点的右子节点。
4. 插入完成后,二叉排序树的特点是,对于任何一个节点,它的左子树的所有节点的值都小于它自身的值,而它的右子树的所有节点的值都大于它自身的值。
相关问题
13. 已知二叉排序树的指针,数组,构建二叉排序树
给定二叉排序树的指针数组,可以通过以下步骤构建二叉排序树:
1. 初始化一个空的二叉排序树。
2. 遍历指针数组,对于每个指针:
a. 如果指针为空,跳过该元素。
b. 找到当前节点在二叉排序树中的位置,插入该节点。
3. 完成遍历后,得到的二叉排序树即为所求。
以下是一个简单的Python实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def insert(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
def construct_bst(pointers, start, end):
if start > end:
return None
mid = (start + end) // 2
node = TreeNode(pointers[mid])
node.left = construct_bst(pointers, start, mid - 1)
node.right = construct_bst(pointers, mid + 1, end)
return node
# 示例
pointers = [4, 2, 7, 1, 3, 6, 9]
root = construct_bst(pointers, 0, len(pointers) - 1)
```
用c语言写如何构建二叉排序树
以下是用C语言实现构建二叉排序树的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
struct Node* insert(struct Node* node, int data) {
if (node == NULL) {
return newNode(data);
} else if (data < node->data) {
node->left = insert(node->left, data);
} else if (data > node->data) {
node->right = insert(node->right, data);
}
return node;
}
void inorderTraversal(struct Node* node) {
if (node != NULL) {
inorderTraversal(node->left);
printf("%d ", node->data);
inorderTraversal(node->right);
}
}
int main() {
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("Inorder traversal of the BST: ");
inorderTraversal(root);
return 0;
}
```
在上述代码中,我们首先定义了一个 `Node` 结构体,包含了一个整数类型的数据成员 `data`,以及左右子节点的指针。然后,我们实现了一个 `newNode` 函数,用于创建一个新的节点,并返回该节点的指针。
接着,我们实现了一个 `insert` 函数,用于向二叉排序树中插入一个新的元素。在该函数中,我们首先判断当前节点是否为空,如果是,则创建一个新节点并返回;如果不是,则向左或右子树插入该元素。
最后,我们实现了一个 `inorderTraversal` 函数,用于中序遍历二叉排序树,并打印出遍历结果。在 `main` 函数中,我们首先创建了一个空的二叉排序树 `root`,然后向其中插入了一些元素,并调用 `inorderTraversal` 函数进行中序遍历。