DS二叉排序树之创建和插入
题目描述
给出一个数据序列，建立二叉排序树，并实现插入功能。
在建立和插入操作后，都输出二叉树的先序遍历结果i
输入
第1行输入n，表示序列包含n个数据
第2行输入n个数据，都是自然数且互不相同，数据之间用空格隔开
第3行输入m，表示要插入m个数据
输入m行，每行一个要插入的数据，都是自然数且和前面的数据不等
输出
第一行输出一开始构建的二叉排序树的先序遍历结果
从第二行起，输出m行，每行输出插入一个数据到二叉排序树后的先序遍历结果
每行输出的遍历结果中，每个数据后面都带一个空格，最后一个数据也带。
IO模式
本题IO模式为标准输入/输出(Standard IO)，你需要从标准输入流中读入数据，并将答案输出至标准输出流中。
输入样例：
6 22 33 55 66 11 44 3 77 50 10输出样例：
22 11 33 55 44 66 22 11 33 55 44 66 77 22 11 33 55 44 50 66 77 22 11 10 33 55 44 50 66 77代码实现：
#include <format> #include<iostream> using namespace std; class BST { private: struct TreeNode { int val; TreeNode *left,*right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; TreeNode* root; TreeNode* insertNode(TreeNode* node,int val) { if (node==nullptr)return new TreeNode(val); if (val<node->val)node->left=insertNode(node->left,val); else node->right=insertNode(node->right,val); return node; } void preOrder(TreeNode* node) { if (node==nullptr)return; cout<<node->val<<" "; preOrder(node->left); preOrder(node->right); } public: BST() : root(nullptr) {} void insert(int val) { root=insertNode(root,val); } void preOrderTraversal() { preOrder(root); } }; int main() { int n;cin>>n; BST bst; for (int i=0;i<n;i++) { int val;cin>>val; bst.insert(val); } bst.preOrderTraversal(); cout<<endl; int m;cin>>m; for (int i=0;i<m;i++) { int val;cin>>val; bst.insert(val); bst.preOrderTraversal(); cout<<endl; } }