2) 用二叉链表作为存储结构,输入键值序列建立一棵二叉排序树,然后中序遍历这棵二叉树。
时间: 2024-05-06 10:17:33 浏览: 138
二叉排序树(Binary Search Tree,简称BST)是一种特殊的二叉树,对于每个节点,它的左子树上所有节点的键值都小于它的键值,右子树上所有节点的键值都大于它的键值。因此,在BST中,对于任意一个节点,它的左子树上的所有节点都小于它,右子树上的所有节点都大于它。在本题中,我们使用二叉链表作为存储结构来实现BST,并对其进行中序遍历。
首先,定义二叉树的节点结构体:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
其中,val表示节点的键值,left和right分别指向左子树和右子树的根节点。
接下来,我们定义一个BST类,并实现插入节点的方法:
```c++
class BST {
public:
BST() : root(nullptr) {}
void insert(int val) {
if (!root) {
root = new TreeNode(val);
return;
}
TreeNode* cur = root;
while (cur) {
if (cur->val > val) {
if (!cur->left) {
cur->left = new TreeNode(val);
break;
} else {
cur = cur->left;
}
} else {
if (!cur->right) {
cur->right = new TreeNode(val);
break;
} else {
cur = cur->right;
}
}
}
}
void inorderTraversal() {
inorderTraversalHelper(root);
}
private:
TreeNode* root;
void inorderTraversalHelper(TreeNode* node) {
if (!node)
return;
inorderTraversalHelper(node->left);
cout << node->val << " ";
inorderTraversalHelper(node->right);
}
};
```
在insert方法中,我们从根节点开始遍历BST,如果当前节点的键值比插入值大,则继续遍历它的左子树;否则,继续遍历它的右子树。如果遇到一个空节点,就在这里插入新节点。插入完成后,我们就可以调用inorderTraversal方法对BST进行中序遍历了。
最后,我们可以编写主函数来测试BST的功能:
```c++
int main() {
BST bst;
vector<int> nums = {5, 2, 8, 1, 3, 7, 9};
for (int num : nums) {
bst.insert(num);
}
bst.inorderTraversal(); // 1 2 3 5 7 8 9
return 0;
}
```
运行结果为:1 2 3 5 7 8 9,符合中序遍历的顺序。
阅读全文