3、将(45,24,55,12,37,53,60,28,40,70)中关键字依次插入初态为空的二叉排序树中,给出树的先序序列。
时间: 2024-05-11 21:20:21 浏览: 16
首先,将根节点设置为 45。依次将其他数插入二叉排序树中,得到如下的树:
```
45
/ \
24 55
/ / \
12 37 60
/ / \
28 53 70
\
40
```
树的先序序列为:45 24 12 37 28 55 53 60 40 70。
相关问题
将(45,24,55,12,37,53,60,28,40,70)中关键字依次插入初态为空的二叉排序树中,给出树的先序序列。代码
二叉排序树的插入过程实际上就是不断地比较大小并往左或右子树递归插入的过程。先序遍历二叉树的顺序是:根节点 -> 左子树 -> 右子树。因此,我们在插入完所有关键字之后,对二叉排序树进行先序遍历即可得到先序序列。
以下是使用 Python 语言实现二叉排序树插入和先序遍历的代码:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 定义二叉排序树类
class BST:
def __init__(self):
self.root = None
# 向二叉排序树中插入关键字
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
cur = self.root
while cur:
if val < cur.val:
if not cur.left:
cur.left = TreeNode(val)
return
cur = cur.left
else:
if not cur.right:
cur.right = TreeNode(val)
return
cur = cur.right
# 先序遍历二叉排序树
def preorder(self, node):
if not node:
return []
res = [node.val]
res += self.preorder(node.left)
res += self.preorder(node.right)
return res
# 创建一个空的二叉排序树
bst = BST()
# 将关键字依次插入二叉排序树中
lst = [45, 24, 55, 12, 37, 53, 60, 28, 40, 70]
for val in lst:
bst.insert(val)
# 输出二叉排序树的先序序列
print(bst.preorder(bst.root))
```
输出结果为:`[45, 24, 12, 37, 28, 40, 55, 53, 60, 70]`。
c++实现 3、将(45,24,55,12,37,53,60,28,40,70)中关键字依次插入初态为空的二叉排序树中,给出树的先序序列。
二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它的每个节点都满足以下性质:
1. 节点的左子树中所有节点的值都小于该节点的值;
2. 节点的右子树中所有节点的值都大于该节点的值;
3. 左右子树本身也是二叉排序树。
根据题目要求,我们可以按照以下步骤来构建二叉排序树:
1. 将第一个数字 45 作为根节点,插入到空树中;
2. 依次将其他数字插入到树中,插入时从根节点开始比较大小,如果小于当前节点,则往左子树插入,否则往右子树插入;
3. 插入完成后,按照先序遍历的方式输出树的节点值。
下面是完整的 C++ 代码实现:
```c++
#include <iostream>
using namespace std;
// 定义二叉排序树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 插入节点到二叉排序树
void insert(TreeNode*& root, int val) {
if (!root) {
root = new TreeNode(val);
} else if (val < root->val) {
insert(root->left, val);
} else {
insert(root->right, val);
}
}
// 先序遍历输出节点值
void preorder(TreeNode* root) {
if (!root) {
return;
}
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
int main() {
int arr[] = {45, 24, 55, 12, 37, 53, 60, 28, 40, 70};
int n = sizeof(arr) / sizeof(arr[0]);
TreeNode* root = NULL;
for (int i = 0; i < n; i++) {
insert(root, arr[i]);
}
preorder(root);
return 0;
}
```
运行结果为:45 24 12 37 28 40 55 53 60 70。