怎样提交网站地图,心理咨询网站php后台一般需要哪些模块,wordpress素材网主题,知名广告公司有哪些题目链接#xff1a;
二叉排序树_牛客题霸_牛客网二叉排序树#xff0c;也称为二叉查找树。可以是一颗空树#xff0c;也可以是一颗具有如下特性的非空二叉树#xff1a; 1。题目来自【牛客题霸】https://www.nowcoder.com/share/jump/437195121692721757794
描述#x…题目链接
二叉排序树_牛客题霸_牛客网二叉排序树也称为二叉查找树。可以是一颗空树也可以是一颗具有如下特性的非空二叉树 1。题目来自【牛客题霸】https://www.nowcoder.com/share/jump/437195121692721757794
描述
二叉排序树也称为二叉查找树。可以是一颗空树也可以是一颗具有如下特性的非空二叉树 1. 若左子树非空则左子树上所有节点关键字值均不大于根节点的关键字值 2. 若右子树非空则右子树上所有节点关键字值均不小于根节点的关键字值 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个关键字值各不相同的节点要求你按顺序插入一个初始为空树的二叉排序树中每次插入后成功后求相应的父亲节点的关键字值如果没有父亲节点则输出-1。
输入描述
输入包含多组测试数据每组测试数据两行。 第一行一个数字NN100表示待插入的节点数。 第二行N个互不相同的正整数表示要顺序插入节点的关键字值这些值不超过10^8。
输出描述
输出共N行每次插入节点后该节点对应的父亲节点的关键字值。
示例1:
输入
5
2 5 1 3 4输出
-1
2
2
5
3思路
定义了二叉树节点结构 TreeNode包含数据域 data左子节点指针 leftChild右子节点指针 rightChild。Insert 函数用于将元素插入到二叉排序树中并在插入的过程中输出每个节点的父节点。根据比较大小关系元素被插入到左子树或右子树中并在插入位置为根节点时输出父节点的值。在 main 函数中首先读取一个整数 n表示要插入的节点个数。然后使用循环读取 n 个节点值并调用 Insert 函数将节点插入到二叉排序树中。整个过程中二叉排序树会逐渐构建起来并且在插入每个节点时都会输出相应的父节点值。
该代码主要用于构建一个二叉排序树并在构建过程中输出每个节点的父节点值。每个节点的值较小的节点会插入到左子树较大的节点会插入到右子树。同时根节点没有父节点所以输出 -1 表示根节点没有父节点。
源代码
#includeiostream
using namespace std;// 定义二叉树节点结构
struct TreeNode {int data; // 节点数据TreeNode* leftChild; // 左子节点指针TreeNode* rightChild; // 右子节点指针TreeNode(int x): data(x), leftChild(NULL), rightChild(NULL) {} // 构造函数
};// 插入元素到二叉排序树中同时输出父节点的值
TreeNode* Insert(TreeNode* root, int x, int father) {if (root NULL) {root new TreeNode(x); // 创建新节点cout father endl; // 输出父节点值}else if (x root-data) {root-leftChild Insert(root-leftChild, x, root-data); // 向左子树插入}else {root-rightChild Insert(root-rightChild, x, root-data); // 向右子树插入}return root;
}int main() {int n;while (cin n) {TreeNode* root NULL; // 树的根节点for (int i 0; i n; i) {int temp;cin temp; // 读取输入的节点值root Insert(root, temp, -1); // 插入节点到二叉排序树中-1表示根节点没有父节点}}return 0;
}提交结果
