华中科技大学复试 二叉排序树

题目描述

二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1. 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值； 2. 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值； 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。

输入描述

输入包含多组测试数据，每组测试数据两行。
第一行，一个数字N（N<=100），表示待插入的节点数。
第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10^8。

输出描述

输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值。

示例

输入

5
2 5 1 3 4

输出

-1
2
2
5
3

原题链接

总结

二叉树的操作，先定义结点，在定义二叉树数据结构。关键在insert函数的实现。直接将-1当作根节点，可以使事情变得简单许多。Node 和 binaryTree 这两个类的构造函数写得巧妙。

Code

#include<iostream>
#include<cstdio>
using namespace std;
class Node
{
   
public:
	Node* left;
	Node* right;
	int value;
	Node(int val) {
   
		value = val;
		left = nullptr;
		right = nullptr;
	}
};
class binaryTree
{
   
public:
	binaryTree() {
   
		root = new Node(-1);
	};
	void insertNode(int value);
private:
	Node* root;
};
void binaryTree::insertNode(int value)
{
   
	Node* temp = new Node(value);
	Node* p = root;
	Node* p1=p;//用于指向空结点的上一个结点
	while (p)//使p定位到最终将要插入的位置
	{
   
		p1 = p;
		if (value > p->value)
			p = p->right;
		else p = p->left;
	}
	if (p1 != nullptr)
	{
   
		cout << p1->value << endl;//输出待插入结点的父结点的值
	//实行插入
		if (temp->value > p1->value)
			p1->right = temp;
		else	p1->left = temp;
	}
	
}
int main()
{
   
	int n,temp;
	cin >> n; getchar();
	binaryTree binTree;
	for (int i = 0; i < n; i++)
	{
   
		cin >> temp;
		binTree.insertNode(temp);
	}
	return 0;
}