题解 | #二叉排序树#

//土尔逊Torson 编写于2023/06/10
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>

using namespace std;

struct TreeNode {
	int data;
	TreeNode * leftChild;
	TreeNode * rightChild;
};

void insertBST(TreeNode * &root, int data) {
	TreeNode *pNewNode = new TreeNode;
	pNewNode->data = data;
	pNewNode->leftChild = NULL;
	pNewNode->rightChild = NULL;
	if (root == NULL) {
		root = pNewNode;
		printf("-1\n");
	}
	else {
		TreeNode *pPre = root;
		TreeNode *pCur;
		while (true) {
			if (data < pPre->data) {
				pCur = pPre->leftChild;
				if (pCur == NULL) {
					pPre->leftChild = pNewNode;
					printf("%d\n", pPre->data);
					break;
				}
				else {
					pPre = pCur;
				}
			}
			else {
				pCur = pPre->rightChild;
				if (pCur == NULL) {
					pPre->rightChild = pNewNode;
					printf("%d\n", pPre->data);
					break;
				}
				else {
					pPre = pCur;
				}
			}
		}
	}
}

int main() {
	int n;
	scanf("%d", &n);
	TreeNode * root = NULL;
	for (int i = 0; i < n; ++i) {
		int num;
		scanf("%d", &num);
		insertBST(root, num);
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")