题解 | #二叉排序树#

#include <iostream>
#include <cstdio>

using namespace std;

typedef int ElementType;

struct TreeNode {
    ElementType data;
    TreeNode *leftChild;
    TreeNode *rightChild;

    TreeNode(ElementType c) {
        this->data = c;
        this->leftChild = nullptr;
        this->rightChild = nullptr;
    }
};

/**
 * 插入结点，并输出结点对应的父节点的数据域
 * @param root
 * @param x
 * @return
 */
TreeNode *insert(TreeNode *root, ElementType x, ElementType fatherData);

/**
 * 二叉排序树--华中科技大学
 * @return
 */
int main() {
    int n;
    while (cin >> n) {
        TreeNode *root = nullptr;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            /*
             * 根节点没有父节点，所以起始传入-1
             */
            root = insert(root, x, -1);
        }
    }
    return 0;
}

TreeNode *insert(TreeNode *root, ElementType x, ElementType fatherData) {
    if (root == nullptr) {
        /*
         * 创建新结点
         */
        root = new TreeNode(x);
        cout << fatherData << endl;
    } else if (x < root->data) {
        /*
         * 插入到左子树，fatherData即是root的data
         */
        root->leftChild = insert(root->leftChild, x, root->data);
    } else if (x > root->data) {
        /*
         * 插入到右子树，fatherData即是root的data
         */
        root->rightChild = insert(root->rightChild, x, root->data);
    }
    return root;
}