题解 | #二叉排序树#

#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;
    }
};

/**
 * 前序遍历
 */
void preOrder(TreeNode* root);

/**
 * 中序遍历
 * @param root
 */
void inOrder(TreeNode* root);

/**
 * 后序遍历
 * @param root
 */
void postOrder(TreeNode* root);

/**
 * 层序遍历
 * @param root
 */
void levelOrder(TreeNode* root);

/**
 * 访问结点
 * @param node
 */
void visit(TreeNode* node);

/**
 * 插入结点
 * @param root
 * @param x
 * @return
 */
TreeNode* insert(TreeNode* root, ElementType x);

/**
 * 二叉排序树--华中科技大学
 * @return
 */
int main() {
    int n;
    while (cin >> n) {
        TreeNode* root = nullptr;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            root = insert(root, x);
        }
        preOrder(root);
        cout << endl;
        inOrder(root);
        cout << endl;
        postOrder(root);
        cout << endl;
    }

    return 0;
}

void preOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    /*
     * 根、左子树、右子树
     */
    visit(root);
    preOrder(root->leftChild);
    preOrder(root->rightChild);
}

void inOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    /*
     * 左子树、根、右子树
     */
    inOrder(root->leftChild);
    visit(root);
    inOrder(root->rightChild);
}

void postOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    /*
     * 左子树、右子树、根
     */
    postOrder(root->leftChild);
    postOrder(root->rightChild);
    visit(root);
}

void visit(TreeNode* node) {
    cout << node->data << " ";
}

TreeNode* insert(TreeNode* root, ElementType x) {
    if (root == nullptr) {
        /*
         * 创建新结点
         */
        root = new TreeNode(x);
    } else if (x < root->data) {
        /*
         * 插入到左子树
         */
        root->leftChild = insert(root->leftChild, x);
    } else if (x > root->data) {
        /*
         * 插入到右子树
         */
        root->rightChild = insert(root->rightChild, x);
    } else {
        /*
         * 题目说重复的元素无需输出，因此重复元素我们不进行插入
         */
    }
    return root;
}