题解 | #二叉排序树#

#include using namespace std;

typedef struct BiNode{ int data; BiNode *left; BiNode *right; int dad; }BiNode, *BiTree;

void Insert(BiTree t, BiTree node) { //给二叉排序树加入一个节点 bool i = 0; BiTree temp = t; while (t != NULL) { if (node->data < t->data) { temp = t; t = t->left; i = 0; } else { temp = t; t = t->right; i = 1; } } if (i == 0){ temp->left = node; node->dad = temp->data; } else{ temp->right = node; node->dad = temp->data; } node->left = NULL; node->right = NULL; }

BiTree InitBiTree(int val) { //初始化一个二叉树 BiTree node = (BiTree)malloc(sizeof(BiNode)); if (node == NULL) cout << "失败了"; else { node->data = val; node->left = NULL; node->right = NULL; node->dad = -1; } return node; }

int main(){ int num, first; scanf("%d", &num); scanf("%d", &first); BiTree t = InitBiTree(first); cout << t->dad << endl; for(int i = 0; i < num - 1; i++){ int a; scanf("%d", &a); BiTree node = (BiTree)malloc(sizeof(BiNode)); node->data = a; Insert(t, node); cout << node->dad << endl; } free(t); }